How expensive is it to compute the eigenvalues of

Question

How expensive is it to compute the eigenvalues of a matrix?

What is the complexity of the best algorithms?

How long might it take in practice if I have a 1000 x 1000 matrix? I assume it helps if the matrix is sparse?

Are there any cases where the eigenvalue computation would not terminate?

In R, I can compute the eigenvalues as in the following toy example:

m<-matrix( c(13,2, 5,4), ncol=2, nrow=2 )
eigen(m, only.values=1)
$values
[1] 14  3

Does anyone know what algorithm it uses?

Are there any other (open-source) packages that compute the eigenvalue?

Answer 1

Apache Mahout is an open-source framework built on map-reduce (i.e. it works for really really big matrices). Note that for a lot of matrix stuff the question isn't "whats the big-o runtime" but rather "how parallelizable is it?" Mahout says they use Lanczos, which can essentially be run in parallel on as many processors as you care to give it.

Answer 2

With big matrices you usually don't want all the eigenvalues. You just want the top few to do (say) a dimension reduction.

The canonical algorithm is the Arnoldi-Lanczos iterative algorithm implemented in ARPACK:

www.caam.rice.edu/software/ARPACK/

There is a matlab interface in eigs:

http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/eigs.html

eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues.

And there is now an R interface as well:

http://igraph.sourceforge.net/doc-0.5/R/arpack.html

Answer 3

I would take a look at Eigenvalue algorithms, which link to a number of different methods. They'll all have different characteristics, and hopefully one will be suitable for your purposes.

Answer 4

How long might it take in practice if I have a 1000x1000 matrix?

MATLAB (based on LAPACK) computes on a dual-core 1.83 GHz machine all eigenvalues of a 1000x1000 random in roughly 5 seconds. When the matrix is symmetric, the computation can be done significantly faster and requires only about 1 second.

Answer 5

I assume it helps if the matrix is sparse?

Yes, there are algorithms, that perform well on sparse matrices.

See for example: http://www.cise.ufl.edu/research/sparse/

Answer 6

It uses the QR algo. See Wilkinson, J. H. (1965) The Algebraic Eigenvalue Problem. Clarendon Press, Oxford. It does not exploit sparsity.