New Features in Maple 15: Sparse Matrix Formats	Differential Geometry

Maple supports a variety of sparse matrix formats. A sparse matrix data structure avoids storing some or all zero entries. The result is a more compact structure that uses less memory. In some cases, without a sparse format the given matrix would be impossible to create on your computer -- it would require more memory than anyone has.

For example, consider the following:



In a dense format, given each double precision float takes 8 bytes, this matrix would be infeasible to store in real memory. It goes beyond gigabytes, terabytes, and even petabytes.



General Sparse Arrays




After creating the matrix, you can browse it by double-clicking on the output summary. Viewing the matrix entries using a magnitude map, you can see the locations in the matrix where the entries are zero (shown in white)



Since there is no apparent structure in this matrix, except for the fact that 90% of the entries are zero, a general sparse matrix is appropriate. There are two general formats for Array, Matrix, and Vector creation in Maple that are specified with the option storage=sparse. One format, for Arrays, Matrices, and Vectors with a non-hardware datatype, uses a hash table to store index/value pairs. Insertion and lookup are very fast, as is unordered data traversal. The other, for hardware datatypes, matches the format used by the Numerical Algorithms Group (NAG) libraries. In this format, vectors are used to store the index and column coordinates, lined up with a value vector.

In Maple 15, several algorithms were improved when working with NAG sparse matrices.



Sparse copy operation:



Matrix muliplication:



Transpose:



Concatenation:





Block selection:




Conversion to dense:



Comparing .3% sparse 1000x1000 matrices using the operations above, with larger 1000x500 sub-block selections, the following chart compares execution time of Maple 14 and Maple 15.

Operation Maple 14 Maple 15 copy .200 seconds .012 seconds multiplication .032 .004 transpose 5.104 .000 concatenation (stack) 10.148 .000 concatenation (side) 10.096 .000 subblock (range) 2.528 .000 subblock (specified columns) 2.624 .060 convert to dense .052 .008

Specialized Sparse Arrays


Maple also supports a number of semi-sparse formats. These formats store all values in a particular region of a matrix, such as all elements above the diagonal. The remaining elements are implicitly zero as in the case of an upper triangular matrix, or a reflection of the stored elements, as in the case of a symmetric matrix. The various semi-sparse formats are designated by the storage option to the Array, Matrix, and Vector constructors. These work in conjunction with a shape, or indexing function that defines how non-stored elements should behave. The various storages are:

For Vectors, the shapes (built-in indexing functions) are:

For Matrices, the shapes (built-in indexing functions) are:

In Maple 15, the properties of diagonal-shaped matrices are leveraged for efficient matrix multiplication.

Differential Geometry