A Sampler of Useful Computational Tools for Applied Geometry, Computer Graphics, and Image Processing

Solution of Linear Systems 91

where V

k

is an n-by-k matrix with orthonormal columns that

form the basis for the Krylov subspace, and H

k+1,k

is an up-

per Hessenberg matrix (a matrix that looks like an upper

triangular matrix plus one additional subdiagonal immedi-

ately below the main diagonal) that contains coordinates of

the basis vectors with respect to the matrix A. When the

matrix is symmetric, the upper Hessenberg reduces to a tridi-

agonal matrix and the procedure simplifies; this is known as

the Lanczos algorithm. The Arnoldi process is given in Al-

gorithm 4.

• We then seek an approximate solution within the subspace

that satisfies an optimality