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

r matrix linear-algebra sparse-matrix eigenvalue
Frank picture Frank · Apr 3, 2009 · Viewed 27.7k times · Source

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

amit-agrawal picture amit-agrawal · Apr 3, 2009

Most of the algorithms for eigen value computations scale to big-Oh(n^3), where n is the row/col dimension of the (symmetric and square) matrix.

For knowing the time complexity of the best algorithm till date you would have to refer to the latest research papers in Scientific Computing/Numerical Methods.

But even if you assume the worse case, you would still need at least 1000^3 operations for a 1000x1000 matrix.

R uses the LAPACK routine's (DSYEVR, DGEEV, ZHEEV and ZGEEV) implementation by default. However you could specify the EISPACK=TRUE as a parameter to use a EISPACK's RS, RG, CH and CG routines.

The most popular and good open source packages for eigenvalue computation are LAPACK and EISPACK.

Related questions

Matrix power in R

Trying to compute the power of a matrix in R, I found that package expm implements the operator %^%. So x %^% k computes the k-th power of a matrix. > A<-matrix(c(1,3,0,2,8,4,1,1,1),nrow=3) > A %^% 5 [,1] [,2] [,3] [1,] 6469 18038 2929 [2,] 21837 60902 9889 [3,] 10440 29116 4729 but, to my surprise: &…

Read More
R memory management / cannot allocate vector of size n Mb

I am running into issues trying to use large objects in R. For example: > memory.limit(4000) > a = matrix(NA, 1500000, 60) > a = matrix(NA, 2500000, 60) > a = matrix(NA, 3500000, 60) Error: cannot allocate vector of size 801.1 Mb > a = matrix(NA, 2500000, 60) …

Read More
Subscript out of bounds - general definition and solution?

When working with R I frequently get the error message "subscript out of bounds". For example: # Load necessary libraries and data library(igraph) library(NetData) data(kracknets, package = "NetData") # Reduce dataset to nonzero edges krack_full_nonzero_edges <- …

Read More