The power method: compute only the largest eigenvalue of a matrix

Abstraction: Iterative algorithm to compute only the largest matrix eigenvalue efficiently

Key points:

• Power iteration repeatedly multiplies a candidate vector by the matrix and renormalizes; converges to the dominant eigenvector for almost any initial vector
• Requires: dominant eigenvalue is real and distinct; initial vector not orthogonal to dominant eigendirection
• Convergence rate equals the ratio of the two largest eigenvalues; slow if eigenvalues are close
• Benchmarked in SAS/IML: power method is virtually instantaneous vs. EIGEN subroutine (which scales polynomially); 2500x2500 matrix shows dramatic speedup
• If dominant eigenvalue is negative, apply method to A*A to find |lambda|, then recover sign separately
• Dominant eigenvalue of a random symmetric matrix is approximately n/2 where n is matrix size

Connections: Sas · Power Iteration · Eigenvalues · Numerical Linear Algebra

Source: http://blogs.sas.com/content/iml/2012/05/09/the-power-method/