Assuming A is a NxN non-singular symmetric matrix, what is the time complexity of getting k number of largest (or smallest) eigenvalues and vectors? Simply, what is time complexity of eigs(A,k) function in matlab?
- updated -
Dear Professor Hyuntae Na
Complexity for Nby N symmetric matrix is O(N^3), since at first by orthogonality of transformation the symmetric matrix by Householder or Givens transformation reduce to the tridiagonal symmetric matrix (O(2/3N^3) and bye Coquer and divided algorithm and O(N^3) we can find all of eigenvalues and for finding eigenvector we need also O(N^3).
Thank you for answers.
My question was not clear.
* size of matrix A is N x N (N is the size of column and row);
* A is symmetric matrix so its eigenvalues are real numbers;
* A is not singular;
* k
Dear Professor Hyuntae Na
I think your guess is correct.
With best regards
I disagree with Peter Breuer. You can get just the largest or he smallest eigenvalues and corresponding vectors by iterations. This is critical for very large matrices and extremely important in structural dynamic response of structures. There are many other applications.
Peter, I dint not mean to question your ego! Read your won statement
"The reason I say that is that (a) all the practical methods used get all the eigenvalues and eigenvectors at once, not one at a time"
Your claim that "all" practical methods. Isn't true.
Peter- Check your facts! There is something called matrix deflation. However, my initial comments are leading to a diversion from the main question which I think is a good one!
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms