2
$\begingroup$

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 leading candidate for this task seems to be Lanczos algorithm.

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ In particular, if you use a routine for multiplying sparse matrices with vectors then you will get the savings you're after. $\endgroup$
    – Steve Flammia
    Commented Dec 14, 2009 at 13:22
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .