[SciPy-user] Re: linalg.eig on sparse matrices

[José Fonseca]

Nils,

On Wed, 21 Jan 2004 10:44:54 +0100, Nils Wagner wrote:
> Hi all,
>
> AFAIK, scipy cannot handle sparse matrices in linalg.eig.
> A first step might be the conversion from sparse to full format. 
> I am wondering if there is any tool for this task available ?

If scipy had support for sparse matrix multiplication (scipy has some
sparse matrix support, but on CVS only AFAIK) then it would be quite
straightforward using the ARPACK bindings in
http://jrfonseca.dyndns.org/work/phd/#arpack . Almost a literal
translation of MATLAB's 'eigs' M-file into Numeric Python would do.

> Moreover, It would be great, to have eigs (an interface to ARPACK ) in
> scipy..

The most import bit is the availability of a generic sparse matrix and
the implementation of the basic operations (such as matrix
multiplication, and matrix factorization). 

ARPACK is doesn't care about the actual sparse matrix format - it only
wants a matrix-vector multiplication callback (and in some cases the
vector mutliplication by the matrix inverse). For all purposes the
matrix may not even exists fully in memory at any time (I actually used
this once to determine the eigenvalues of a _full_ covariance matrix of
a random field with millions of elements since it was cheaper to compute
the matrix elements every time than to store it fully in memory).

> Any hint would be appreciated.

You can see at http://mefriss1.swan.ac.uk/svn/python/Sparse.py a real
usage example. It implements a _very_ basic sparse matrix class (with
addition, subtraction, and matrix-vector multiplication), and then the
linear system solver, and a eigenvalue solver. It uses UMFPACK for
matrix factorization and another C module - spblastk - for matrix-vector
multiplication which can be a bottleneck.

And in case you ask about integrating these ARPACK bindings with scipy:
I don't see much point until scipy provides sparse matrices support, and
I already have too much on my plate to take such an endeavor (and not
much immediate interest either). Perhaps you could take this mater in
your hands instead...

I hope this helps.

Jose Fonseca