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.

$\endgroup$

2 Answers 2

10
$\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.

$\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$ Dec 14, 2009 at 13:22
4
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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