I want to obtain eigenvalues of symmetric matrix in Julia in O(nmr)

Question

I am a beginner at Julia. I want to obtain r eigenvalues and eigenvectors of input symmetric n times n matrix X in increasing order. I heard the computational complexity is O(n^2 r).

n is around 1000-20000, r is around 100-1000. How can I obtain the eigenvalue and eigenvectors within O(nmr)?

Answer 1

I'm not an expert on this, but I would start out trying the methods in the LinearAlgebra stdlib. The LinearAlgebra.eigen function is specialized on the input matrix types SymTridiagonal, Hermitian, Symmetric, and lets you specify how many vectors/values you want:

If you have a dense matrix, A, and want the largest r eigenvalues and vectors:

(evals, evecs) = eigen(Symmetric(A), 1:r)

You can also use eigvals and eigvecs if you just need eigenvalues or eigenvectors. Also check out eigen! if you want to save some memory.

BTW, using Symmetric(A) doesn't create a new matrix, it is just a wrapper around A that tells the compiler that A is symmetrical and only accesses the part of A that is above the diagonal.

If the version in LinearAlgebra is not the fastest in this quite general case, then it should probably be reported on Julia's github. There may be faster implementations for more specialized cases, but for general symmetric dense matrices, the implementation in the stdlib should be expected to be near optimal.