I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now we're interested in finding $d$ largest eigenpairs, but for a "symmetric" matrix. What is the time complexity of this algorithm and what is the name of the algorithm? My guess is this would take $O(dn^2)$ just because we need to perform the original method $d$ times. But, I think it's be faster if we assume the matrix is symmetric. Thanks in advance!
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The power method takes $O(n^2)$ time per step. It is an iterative algorithm, and convergence is geometric. The absolute speed of convergence depends on the ratio between the two largest eigenvalues.
The usual generalisation of the power method to the top $d$ eigenpairs is the Lancosz algorithm, if the matrix is positive definite. There are also algorithms with similar convergence properties that find an eigenpair whose eigenvalue is close to a desired value, such as LOBPCG.
