From: Michael Weitzel <michael.weitzel@uni-siegen.de>

Date: Thu, 31 May 2007 10:53:57 +0200

Message-ID: <465E8D25.8090303@uni-siegen.de>

To: www-math@w3.org

Date: Thu, 31 May 2007 10:53:57 +0200

Message-ID: <465E8D25.8090303@uni-siegen.de>

To: www-math@w3.org

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 GMT

*
This archive was generated by hypermail 2.2.0+W3C-0.50
: Saturday, 20 February 2010 06:12:59 GMT
*