# Using the Arnoldi Iteration to find the k largest eigenvalues of a matrix

I'm trying to obtain a general understanding of this algorithm which determines the k-largest eigenvalues of a matrix $A\in \mathbb{R}^{n\times n}$. How I see it:

power iteration:

• take random starting vector $b \in \mathbb{R}^{1\times n}$
• find $K_{n} = \begin{bmatrix}b & Ab & A^{2}b & \cdots & A^{n-1}b \end{bmatrix}.$
• find orthogonal basis $Q_n$ of $K_{n}$ using Gramm-Schmidt (Numerically unstable)
• n-th column vector of $Q_n$ is an approximation of n-th eigenvector of $A$ and corresponds to n-th largest eigenvalue $\lambda_n$ of $A$

Arnoldi Iteration:

Is a numerically stable implementation of power iteration.

• take random starting vector $b \in \mathbb{R}^{1\times n}$

• find first $q_1..q_n$ arnoldi vectors to form $Q_n$

• $Q_n$ is an orthonormal basis of $K_n$
• numerically stable Gramm-schmidt process is used
• determine Hessenberg Matrix $H_n=Q_n^*AQ_n$
• solve eig($H_n$) which is now simple because $H_n$ is a Hessenberg matrix, upper triangular, we can use the QR algorithm

Is this the general gist of it? A good, reliable link would already be great.

Any help would be greatly appreciated. Thank you.

• You've seen this, haven't you? Dec 23 '11 at 23:59