most recent 30 from http://mathoverflow.net 2013-05-23T00:07:40Z http://mathoverflow.net/feeds/question/8863 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8863/the-application-of-lanczos-algorithm-on-sparse-matrix Graviton 2009-12-14T09:56:44Z 2010-02-04T19:08:53Z

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

http://mathoverflow.net/questions/8863/the-application-of-lanczos-algorithm-on-sparse-matrix/8867#8867 Darsh Ranjan 2009-12-14T11:31:00Z 2009-12-14T11:31:00Z

<p>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. </p>

http://mathoverflow.net/questions/8863/the-application-of-lanczos-algorithm-on-sparse-matrix/8925#8925 Steve Huntsman 2009-12-15T00:35:46Z 2009-12-15T00:35:46Z

<p>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.</p>