Arnoldi iteration is an iterative method to approximately find the eigenvalues and eigenvectors of matrices by generating an orthogonal basis of Krylov subspace.
Given a matrix A which is m x m, and an initial vector b, which is m x 1, we can construct the n-th order Krylov subspace:
.
The advantage of constructing the Krylov subspace is that we can compute the matrix-vector product instead of cope with matrix A directly, which is particularly useful when A is large, since the cost of matrix-vector product is relatively cheaper.
Suppose 
, where H and Q are m x m matrices, H is an upper Hessenberg matrix, which has zero entries below the first subdiagonal, and Q is a unitary matrix with 
. With the aid of Krylov subspace, we can reduce the matrix A to an upper Hessenberg matrix.
First, we can rewritten the expression of matrix A as AQ = QH, shown as follows:
,
where n is the dimention of Krylov subspace as mentioned. Then we write a new expression of matrix A, which is part of the above equation, as 
, where 
and
.
Calculated the n-th columns of both sides, we have 
. Therefore, we can express 
as
,
which can be regarded as a iterative process.
The algorithm is shown as follow, which is from wiki:
.
Note that 
, which can be computed using the above algorithm. By removing the last row of matrix 
, we have the n x n matrix 
, which has the same eigenvalues as matrix A. That is how we reduce the matrix A to an upper Hessenberg matrix.