## The Application of Lanczos Algorithm on Sparse Matrix

I am looking for suitable algorithm to compute the eigenvalues and eigenvectors of a matrix. My matrix is sparse ( think of Finite Element Matrix), and it is very, very big ( think of hundreds of thousands or even million degrees of freedom).

The issue now is, how well Lanczos algorithm fare if the matrix is sparse? The reason I ask this is because I want to know if there are a lot of zero terms in a matrix, will Lanczos take advantage of this by storing only nonzero terms and operate on them? Since my matrix is big, I want to conserve as much memory space as possible.

-

Lanczos is independent of the representation of your matrix. It does not store or operate on the entries of your matrix. The input to the algorithm is not the matrix $A$ itself, but a black-box subroutine for matrix-vector multiplication: you provide a method to compute $Av$ given vectors $v$. That's the only way it needs to use your matrix. In other words, you can represent $A$ however you want.

-
In particular, if you use a routine for multiplying sparse matrices with vectors then you will get the savings you're after. – Steve Flammia Dec 14 2009 at 13:22

More generally, black-box linear algebra is an entire subfield of linear algebra, in which the matrix-vector multiplication is treated as an oracle. Generally if this oracle has subquadratic complexity (i.e., the matrix is either sparse or posesses structure, such as for a Toeplitz or circulant matrix), you can improve on classical algorithms. You can find out about this in von zur Gathen's book or in a 1986 IEEE article by Weidemann.

-