Re: sparse matrix support in MathML

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 08:54:40 UTC