W3C home > Mailing lists > Public > www-math@w3.org > June 2007

Re: sparse matrix support in MathML

From: Jason Davis <jasonkarldavis@gmail.com>
Date: Fri, 1 Jun 2007 09:15:47 -0400
Message-Id: <AFE00B19-740E-4408-A8B5-58E26752D53E@gmail.com>
To: www-math@w3.org

What about abusing/extending the existing <matrix> element?

<matrix> has two optional attributes: "rows" and "cols" which accept  
positive integer values.

If they are not specified, then it would be in error to utilize  
sparse matrix functionality.

There are 4 templates for the children of <matrix> with rows/cols  
specified.

1. The traditional dense notation
2. <matrixrow>, but with a required "index" attribute.
3. <matrixcolumn>, but with a required "index" attribute.
4. <matrixelement>, with required "row" and "col" attributes.

In the case of 3 or 4, children of those elements can only be  
<matrixelement>, but with

Children of <matrix> can be <matrixrow> (already in the spec),  
<matrixcolumn>. These must contain a "row" attribute (in the case of  
3) or a "col" attribute (in the case of 2).

This way allows either dimension to be dense, or neither, without too  
much confusion I feel. (Essentially "index" attributes inherit to the  
matrixelement children along that dimension).

It might even be worthwhile to loosen up the spec a bit to just the  
following:


<matrix>			Optional rows/cols attributes.
If not specified, must be dense matrix. Otherwise, a DTD for matrix  
children:

<!ELEMENT matrix (matrixrow|matrixcolumn|matrixelement)+>
<!ELEMENT matrixrow (matrixelement+)>
<!ELEMENT matrixrcolumn (matrixelement+)>

<matrixelement> has required "row" and "col" attributes; however, the  
value of "index" on a parent <matrixrow> would imply a value for the  
element's "row", and the value of "index" on a parent <matrixcolumn>  
would imply a value for the element's "col". (In a dense matrix, the  
implementor would have to imply the values based on the elements  
offset). Ultimately, you could mix matrixrows, matrixcolumns, and  
matrixelements all at the same level in the document. It's a trivial  
XSLT transform to convert that into just all <matrixelement>'s with  
row and col specified, which generally reflects the internal storage  
mechanism of a sparse matrix. It also allows authors to take  
advantage of dense rows, dense columns, or neither all with the same  
notation.

-Jason






On Jun 1, 2007, at 5:28 AM, W Naylor wrote:

> On Thu, 31 May 2007, Jason Davis wrote:
>
>>
>> How wise is it to require specifying every row? You get the  
>> benefit of having
>> sparse columns, but the markup is still dense in the rows. I would  
>> suggest:
>>
>> <smatrix rows="m" cols="n">
>> <smatrixdefault><cn>0</cn></smatrixdefault>
>> <smatrixelement row="i" col="j"><cn>5</cn></smatrixelement>
>> ...
>> </smatrix>
>
> Jason does have a point here, however there are situations where the
> matrix will be dense in the number of rows (or columns). The  
> situation I
> was dealing with in my project was factorisation by the quadratic  
> sieve
> method, here the matrices were dense in the rows, but sparse in the
> columns. To address this I made two symbols in the CD at:
> http://www.cs.bath.ac.uk/~wn/OpenMath/GENSS/html/cd/linalg6.html
> nonZeroRowSparseMatrix and sparseMatrix
> the first being for row dense matrices whlst the second for the  
> general
> case.
>
> Of course for 'MathML style' markup it wouldn't be necessary to have
> separate elements for the different cases, we could just have  an  
> optional
> attribute on the enclosing 'smatrix' element which specifies the
> sparsity of the matrix.
> e.g.
> optional attribute:
> name = sparsity		permissable values = rowdense/columndense/
> this attribute would then determine the admissable content,
>
> thoughts?
>
> Bill
>
>>
>> As far as I know, programs like Matlab simply uses a list of (i,j)-
>>> value tuples in their sparse matrix implementation (or at least
>> makes it appear that way to the user), and this is a direct  
>> reflection of it.
>>
>> -Jason Davis
>>
>>
>> On May 31, 2007, at 9:16 AM, Max Berger wrote:
>>
>>> Dear David,
>>>
>>> David Carlisle schrieb:
>>>>> - Reuse mtable, mrow, mcolumn (otherwise functionality is
>>>>> duplicated).
>>>>
>>>> wouldn't you want to use content markup rather than presentation  
>>>> for
>>>> this?
>>>
>>> You are right. Assuming display math is for displaying only, and
>>> therefore it wouldn't matter to insert numerous extra <mtd>, the
>>> original idea of introducing a <smatrix> for content markup seems  
>>> fine
>>> to me. However, I think the ideas of attribute handling are still  
>>> valid.
>>>
>>> Here is an idea for the "rest" of the matrix:
>>>
>>> <smatrix columns="4">
>>> <smatrixdefalut><cn>0</cn><smatrixdefault>
>>> <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>
>>>
>>> the "smatrixdefault" element would give the "default" value for all
>>> unspecified elements. If not given, I believe <cn>0</cn> seems  
>>> like a
>>> good default value. However, one would have to use <smatrixdefault/
>>>> to
>>> empty the default element.
>>>
>>>
>>>> David
>>>
>>>
>>> mfG
>>>
>>> Max Berger
>>> e-mail: max@berger.name
>>>
>>> -- 
>>> OpenPG ID: E81592BC   Print: F489F8759D4132923EC4  
>>> BC7E072AB73AE81592BC
>>> For information about me and my work please see http:// 
>>> max.berger.name
>>>
>>
>>
>>
>>
>>
>>
>>
>
> -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*- 
> *-*-*
> -
> -                  Dr. W.A. Naylor
> -
> -                  http://www.cs.bath.ac.uk/~wn
> -
> -                  work tel: +44 1225 386183
> -
> -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*- 
> *-*-*
Received on Friday, 1 June 2007 13:16:05 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Saturday, 20 February 2010 06:13:00 GMT