next up previous contents index
Next: Subspace Dimension. Up: Single- and Multiple-Vector Iterations Previous: Rayleigh Quotient Iteration   Contents   Index


Subspace Iteration

Another important improvement over the power method permits us to compute a $(p > 1)$-dimensional invariant subspace, rather than one eigenvector at a time. It is called orthogonal iteration (and sometimes subspace iteration or simultaneous iteration).


\begin{algorithm}{Simple Subspace Iteration for HEP}
{
\begin{tabbing}
(nr)ss\...
...ize $V R = Y$\ \\
{\rm (7)} \> \> {\bf end for}
\end{tabbing}}
\end{algorithm}

This algorithm is a straightforward generalization of the power method. The QR factorization is a normalization process that is similar to the normalization used in the power method. The eigenvalues of the Hermitian $p \times p$ matrix $H=V^{\ast}AV$ will approach the $p$ eigenvalues of $A$ that are largest in absolute value.

Several modifications are needed to make the simple subspace iteration an efficient and practically applicable code. First, it is natural to orthonormalize as infrequently as possible, i.e., to perform several iterations before performing an orthogonalization. Second, we may choose to operate on a subspace whose dimension $p$ is larger than $\nev$, the number of eigenvalues wanted, and use a Rayleigh-Ritz process to get eigenvalue approximations. Third, some eigenvalues will converge faster than others, and if this happens it is a good idea to lock these and let the matrix operate only on those vectors that have not yet converged.

In addition, the method is rarely used without some form of acceleration; we describe some of those techniques at the end of this section.



Subsections
next up previous contents index
Next: Subspace Dimension. Up: Single- and Multiple-Vector Iterations Previous: Rayleigh Quotient Iteration   Contents   Index
Susan Blackford 2000-11-20