
Boost : 
From: David Abrahams (abrahams_at_[hidden])
Date: 20010313 17:57:26
 Original Message 
From: <walter_at_[hidden]>
> I have got another problem with sparse matrices also, which I would
> like to mention here: IMHO dense matrices and classical linear
> equation solvers together form a pair, for example. Sparse matrices
> are normally used in the context of iterative solvers, which are
> quite subtle to handle AFAIK.
Certainly sparse matrices are useful in iterative problems, but I think you
have the motivation backward... my understanding is that we try to produce
sparse matrices because, in part, they cause iterative solvers to converge
sooner. On the other hand, it would be foolish to overlook the presence of
sparse matrices in classical linear algebra problems. I have recently been
prototyping some simple LU factorization and solving code in Python, just to
get a feel for the domain, and the utility of sparse matrices is already
hugely apparent. For one simple example, a permutation matrix is a kind of
sparse matrix. It is possible to represent a permutation matrix in far less
space than a dense matrix of the same dimensions. If you encode this
property in the type of the matrix, you can get huge savings in the cost of
a matrix multiplication, especially if the other matrix happens to have a
twolevel pointer representation. You can also think of the upper and
lower triangular matrices which result from factorization as sparse
matrices
Dave.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk