Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

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.

share|improve this answer
2  
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 '09 at 13:22
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.