Re: sparse matrix support in MathML

If one or other format is chosen for this, I think it would
also be necessary to have a slot to describe the default value, 
which I guess is <mn>0</mn> or <cn>0</cn> or something like 
this normally.  It may need to be changed if the author prefers 
to display a blank here, or to display the zero in a different 
style, or if the author is working in some mathematical context 
where "zero" is something other than "0".

Richard


On Thu, 2007-05-31 at 10:53 +0200, Michael Weitzel wrote:
> Hi,
> 
> from my point of view (as implementor of a MathML parser and a user of
> Content-MathML and sparse matrix algorithms) a sparse matrix
> representation should be as general and simple as possible. I personally
> don't like implementing logic for many different variants of sparse
> matrices (sparse, banded, upper hessenberg, ...).
> 
> Probably the most common storage scheme is the compressed row or column
> scheme. Here, a sparse matrix is stored without wasting extra memory
> using three arrays: cidx[], ridx[] and data[]
> 
> for example (taken from Octave; a compressed column scheme):
> 
> 1 2 0 0
> 0 0 0 3
> 0 0 0 4
> 
> int cidx[] = {0,1,2,2,4};
> int ridx[] = {0,0,1,2};
> double data[] = {1,2,3,4};
> 
> a left-right, top-down enumeration of all non-zero elements works as
> follows:
> 
> int i,j;
> int nc = 4;
> for (j=0; j<nc; j++)
> 	for (i=cidx[j]; i<cidx[j+1]; i++)
> 		printf("(%i,%i) = %i\n", ridx[i],j,data[i]);
> 
> An overview of other common storage schemes can be found here:
> http://www.cs.utk.edu/~dongarra/etemplates/node372.html
> 
> The above example is taken from:
> http://www.sce.carleton.ca/faculty/adler/publications/2006/bateman-adler-octave2006-sparse-matrix.pdf
> 
> This compressed format represents a reasonable tradeoff between memory
> consumption and the overhead for randomly accessing the elements. As a
> drawback it is rather hard to read. Since random access performance is
> unimportant for a serialized representation MathML should just provide a
> representation with minimal storage requirements.
> 
> The OpenMath approaches suggested by Bill and David are surely
> reasonable. IMO a scheme which lists rows and within rows non-zero
> columns would be favorable (similar to the existing matrix-element),
> i.e. something that looks like:
> 
> <smatrix columns="4">
>   <smatrixrow>
>     <smatrixelem col="1"><cn>1</cn></smatrixelem>
>     <smatrixelem col="2"><cn>2</cn></smatrixelem>
>   </smatrixrow>
>   <smatrixrow>
>     <smatrixelem col="4"><cn>3</cn></smatrixelem>
>   </smatrixrow>
>   <smatrixrow>
>     <smatrixelem col="4"><cn>4</cn></smatrixelem>
>   </smatrixrow>
> </smatrix>
> 
> again, for the above example:
> 1 2 0 0
> 0 0 0 3
> 0 0 0 4
> 
> An empty <smatrixrow/> elements corresponds to a row with zeros. Since
> the information about the number of columns is missing it should be
> added to the smatrix-Element.
> 
> regards,
> 
> Michael
> 
> Robert Miner wrote:
> > Michael,
> > 
> > I'm not knowledgeable about sparse matrix representations.  Are there a
> > couple "standard" ones that are widely supported, and if so, what are
> > they like?  If not, what is your view to the "pure OpenMath" approach
> > using csymbol that David Carlisle and Bill Naylor are talking about.
> > 
> > --Robert
> > 
> > Robert Miner
> > Director, New Product Development
> > 
> > Design Science, Inc.
> > 140 Pine Avenue, 4th Floor
> > Long Beach, California  90802
> > USA
> > Tel:  (651) 223-2883
> > Fax:  (651) 292-0014
> > robertm@dessci.com
> > www.dessci.com
> > ~ Makers of MathType, MathFlow, MathPlayer, WebEQ, Equation Editor,
> > TexAide ~
> > 
> > 
> >> -----Original Message-----
> >> From: www-math-request@w3.org [mailto:www-math-request@w3.org] On
> > Behalf
> >> Of Michael Weitzel
> >> Sent: Wednesday, May 30, 2007 5:25 AM
> >> To: www-math@w3.org
> >> Subject: sparse matrix support in MathML
> >>
> >>
> >> Hi,
> >>
> >> I definitely miss support for sparse matrices in Content-MathML.
> > Loading
> >> and saving tons of zeros involves ugly delays for large sparse
> > matrices
> >> and unnecessarily bloats the XML files. Sadly, MathML version 3 does
> > not
> >> introduce such a type. Programming environments like Matlab/Octave and
> >> Maple support sparse matrices -- MathML should likewise.
> >>
> >> regards,
> >> --
> >> Michael Weitzel

Received on Thursday, 31 May 2007 12:24:50 UTC