Re: sparce matrices

[Edwin Robert Tisdale <E.Robert.Tisdale@jpl.nasa.gov>]

Matthew J. Doller wrote:

> I am about to begin a project at my school using gsl
> and my advising professor seems to be very interested in gsl.
> one question he did have was,
> "Are there any constructs to store sparces matrices?"
> It might be beneficial to have such a way to store them
> especially when dealing with matrices that are 10e8 x 10e8 in size.

First, let me point out that a matrix -- even a sparse matrix --
of that size has no physical relevance.
Even a matrix of size 10,000 by 10,000 is on shaky numerical ground.
More typically, large sparse matrices are on the order of 1,000 by
1,000.
If they are much larger than that,
the user is probably doing something very, very wrong.

There are two distinct considerations in sparse matrix libraries.
The primary consideration is to save time by avoiding algorithms
that move zeros in and out of memory.
The secondary consideration is to save memory
by storing only the non zero entries of the sparse matrix.
Modern computer architectures have fast floating-point pipelines
and large, fast and cheap memory so neither of these considerations
is worth pursuing unless the matrix is very large and very sparse
(i.e., less than 10% of the entries are non zero).
It is especially important to keep this in mind
when considering triangular and symmetric matrix representations.

There doesn't appear to be any suitable abstraction for sparse matrices.
Sparse matrix libraries are all about the specific data representation.
Take a look at Survey of Sparse Matrix Storage Formats

http://www.netlib.org/linalg/old_html_templates/subsection2.8.3.1.html

Low level vector and matrix arithmetic libraries like the GSL and
the Vector, Signal and Image Processing Library (VSIPL)

	http://www.vsipl.org/

don't support sparse matrix data types directly but the VSIPL API
specifies a gather operation which can be used to collect
the non zero elements of a sparse matrix into a dense vector
and a scatter operation which can be used to insert
the elements of a dense vector into a sparse matrix.
Otherwise, the only other truly useful operation
is sparse matrix - dense vector multiplication
which can be used to solve a system of equations iteratively --
see IML++ (Iterative Methods Library) v. 1.2a

	http://math.nist.gov/iml++/

for example.