3
$\begingroup$

It is a commonly known fact that the Rayleigh Quotient converges cubically (1), while the Power Iteration may converge slowly if the difference between the dominant and second-dominant eigenvalue is small.

Knowing this, when would it ever be beneficial to use the Power Iteration over the Rayleigh Quotient Iteration? The only possible upside that I can see with the Power Iteration is that it consists of a matrix-vector multiplication $O(n^2)$, while the Rayleigh Quotient iteration requires the solving a system of equations $O(n^{3})$.

Is there a specific size threshold that needs to be reached before the Power Iteration becomes superior? What about for matrices with a specific structure?

References

  1. Parlett, Beresford N. "The Rayleigh quotient iteration and some generalizations for nonnormal matrices." Mathematics of Computation 28.127 (1974): 679-693.
$\endgroup$
  • $\begingroup$ If that is a well known fact you would not mind giving a reference. $\endgroup$ – nicoguaro Mar 11 '16 at 21:17
  • 1
    $\begingroup$ ams.org/journals/mcom/1974-28-127/S0025-5718-1974-0405823-3/… $\endgroup$ – ddddDDDD Mar 11 '16 at 21:33
  • $\begingroup$ For some matrices (e.g., the original google page rank method) you're only after the Perron-Frobenius eigenvector and ignore the rest completely, and the matrix is large enough that you can't easily (or at all) solve linear systems with it. In the page rank case the number of nonzero entries would be something like the number of links that you've crawled, so my impression was that you could multiply but couldn't divide. I'm not sure how realistic that is, but I think it's described in one the papers. $\endgroup$ – Kirill Mar 12 '16 at 2:28
  • $\begingroup$ If you have an $O(n)$ method for matrix-vector multiplication, you should publish it! ;-) $\endgroup$ – David Ketcheson Mar 14 '16 at 5:05
  • $\begingroup$ Oh, my bad, I will fix my error at once. $\endgroup$ – ddddDDDD Mar 14 '16 at 12:20
5
$\begingroup$

Power and Rayleigh iterations are fundamentally different beasts, because the former uses only matrix-vector products with $A$, while the latter uses matrix-vector products with $(A+zI)^{-1}$. This is a very important point -- neither algorithms require explicit access to the matrix itself, but only certain actions of the matrix.

The choice to chose one over the other is heavily weighted by the application-specific complexity of each operation, which does not always scale according to the figures you have quoted.

Consider the case where $A$ is actually dense, but matrix-vector products can be efficiently computed. For example, gravity is a dense interaction, meaning that every body interacts with every other body. If the strengths of the interactions between $n$ bodies are tabulated as the $n\times n$ matrix $A$, then it will contain $n^2$ nonzero elements. For very large $n$, these $n^2$ elements might not even fit in memory. However, the matrix-vector product $Ax$ can be computed in just $O(n)$ complexity using the fast multipole method, without ever having to form the matrix. Accordingly, it is possible to compute $\lambda_\max(A)$ using power iterations, even as $n$ scales into the billions.

On the other hand, when $A$ is a sparse matrix, there often exist a reordering of the columns of the matrix such that $(A+zI)^{-1}x$ can be computed in near-linear or linear complexity. After an initial symbolic factorization step, only $\approx O(n)$ work is required to compute each Rayleigh iteration. In this case, there is very little reason to even consider power iterations.

Finally, I should note that power iterations is a suboptimal Krylov subspace method. Wherever power iterations can be used, the Lanczos iterations can do better. In fact, using exact arithmetic, Lanczos is guaranteed to converge after $n$ iterations.

$\endgroup$
  • $\begingroup$ Thanks, this is the type of answer I was looking for. The only real exposure I've had to these algorithms is in an introductory numerical linear algebra class, and I appreciate you mentioning the Krylov subspace method. $\endgroup$ – ddddDDDD Mar 14 '16 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.