CODEWITHSUNDEEP
sparse-matrixeigenvalueeigenvector
bemma
bemma

Reputation: 95

Finding k-smallest eigen values and its corresponding eigen vector for large matrix

For a symmetric sparse square matrix of size 300,000*300,000, what is best way to find 10 smallest Eigenvalues and its corresponding Eigenvectors within an hours or so in any language or packages.

Upvotes: 2

Views: 1644

Answers (1)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 520908

The Lanczos algorithm, which operates on a Hermitian matrix, is one good way to find the lowest and greatest eigenvalues and corresponding eigenvectors. Note that a real symmetric matrix is by definition Hermitian. Lanczos requires O(N) storage and also roughly O(N) time to evaluate the extreme eigenvalues/eigenvectors. This contrasts with brute force diagonalization which requires O(N^2) storage and O(N^3) running time. For this reason, the Lanczos algorithm made possible approximate solutions to many problems which previously were not computationally feasible.

Here is a useful link to a UC Davis site, which lists implementations of Lanczos in a number of languages/packages, including FORTRAN, C/C++, and MATLAB.

Upvotes: 2

Related Questions