University of Maryland College Park
Institute for Advanced Computer Studies TR{2001{90
Department of Computer Science TR{4316
Addendum to \A Krylov{Schur Algorithm for
Large Eigenproblems"

G. W. Stewart
y
December 2001
ABSTRACT
In this addendum to an earlier paper by the author, it is shown how to
compute a Krylov decomposition corresponding to an arbitrary Rayleigh-
Quotient. This decomposition can be used to restart an Arnoldi process,
with a selection of the Ritz vectors corresponding to the Rayleigh quotient.

This report is available by anonymous ftp from thales.cs.umd.edu in the directory pub/reports
or on the web at http://www.cs.umd.edu/stewart/.
y
Department of Computer Science and Institute for Advanced Computer Studies, University of Mary-
land, College Park, MD 20742 (stewart@cs.umd.edu).
Addendum to \A Krylov{Schur Algorithm for
Large Eigenproblems"
G. W. Stewart
ABSTRACT
In this addendum to an earlier paper by the author, it is shown how to
compute a Krylov decomposition corresponding to an arbitrary Rayleigh-
Quotient. This decomposition can be used to restart an Arnoldi process,
with a selection of the Ritz vectors corresponding to the Rayleigh quotient.
In [3] the author introduced a decomposition of the form
AU = UB +ub
H
; (1)
where A is a matrix of order n and (U u) has full column rank. It was shown that the
column space of(U u) (called the subspace of the decomposition)is a (possibly restarted)
Krylov subspace of A and conversely that every Krylov subspace has such a represen-
tation, so that the Krylov decomposition (1) is a characterization of Krylov subspaces.
Arnoldi and Lanczos decompositions are special cases of Krylov decompositions.
The advantage ofworking with Krylov decompositions is that their subspaces remain
invariant under two classes of transformations. The rst, called a similarity, transforms
the decomposition into
A(UW
BnZr1
) = (UW
BnZr1
)(WBW
BnZr1
)+u(b
H
W)  A
~
U =
~
B + u
~
b
H
;
where W is any nonsingular matrix. The second, called a translation, transforms the
decomposition to the form
AU = U
~
B + ~ub
H
;
where
~
B = B + gb
H
; ~u =
uBnZrUg

; and
~
b
H
= 
b
H
;
for any vector g and any scalar 
 6= 0.
The computational algorithms in [3] were based on similarities. Translations were
used primarily in the derivation of theproperties ofKrylovdecompositions. The purpose
of this note is toshowthattranslations havea computational role toplay in restarting an
Arnoldi process withaselection ofRayleigh{Ritz approximationstoasetofeigenvectors.
1
2 Krylov{Schur Addendum
The Rayleigh{Ritz method for producing these approximations does not depend on
whether the subspace in question is a Krylov subspace. It can be presented in dierent
ways. The one we give here leads most directly to the main result of this note. Let U
be a basis for the subspace U in question and let V be such that V
H
U is nonsingular.
Then the matrix
B = (V
H
U)
BnZr1
V
H
AU (2)
has the property that (;Uw) is an eigenpair of A, then (;w) is an eigenpair of B.
Specically,
Bw = (V
H
U)
BnZr1
V
H
AUw = (V
H
U)
BnZr1
V
H
Uw = w:
By continuity one might expect that if U contains an approximate eigenvector of A,
then it can be found by computing an appropriate eigenpair (;w) of B and forming
Uw. This is the essence of the Rayleigh{Ritz method (for an analysis of the method see
[1]). The matrix B is called a Rayleigh quotient (with respect to U and V) because (2)
is a generalization of the ordinary Rayleigh quotient v
H
Au=v
H
u.
It wasobservedin [3]thatthe matrixB in the Krylov decomposition (1)is aRayleigh
quotient. Specically, let (V v)
H
be a left inverse of (U u). Then V
H
U = I and
V
H
u = 0. It follows from (1) that B = V
H
AU is a Rayleigh quotient, which can be
used in the Rayleigh{Ritz procedure.
In some cases, however, we may not have the freedom to choose V. For example, in
the harmonic Rayleigh{Ritz method, which has superior properties for approximating
interior eigenvalues [2], [4, pp.292{294], we must take V = (ABnZrI)U, where  is near
the eigenvalues of interest. The following theorem shows that although B in (1) need not
be the Rayleigh quotient with respect to V there is a translated Krylov decomposition
whose Rayleigh quotient is.
Theorem 1. In the Krylov decomposition (1) let V
H
U be nonsingular. Then with
g = (V
H
U)
BnZr1
V
H
u, we have
B +gb
H
= (V
H
U)
BnZr1
V
H
AU: (3)
Proof. By translation,
AU = U(B + gb
H
)+(uBnZrUg)b
H
(4)
is a Krylov decomposition. Moreover, by the denition of g, we have V
H
(uBnZrUg) = 0.
Hence (3) follows on multiplying (4) by (V
H
U)
BnZr1
V
H
.
We have shown in eect that if B is the Rayleigh quotient of a Krylov decomposition,
all other Rayleigh quotients with respect to U are rank-one modications of B. For
harmonic Ritz vectors the formulas simplify, since from (1)
V = (ABnZrI)U = U(B BnZrI)+ub
H
:
Krylov{Schur Addendum 3
In practical implementations of Krylov method, (U u) will be orthogonal, so that
V
H
U = (BBnZrI)
H
and V
H
u = b:
Hence, g = (B BnZrI)
BnZrH
b and the Rayleigh quotient is
B +(B BnZrI)
BnZrH
bb
H
:
Thus there is no need to form V explicitly. For the symmetric case this formula is due
to Morgan [2].
The importance of this result, however, is not in the fact that it provides formulas
for Rayleigh quotients. That could be done from the original decomposition. Instead
the key fact is that Rayleigh quotient is part of the Krylov decomposition (4). This
means that we can use the decomposition to restartthe an Arnoldi process with selected
Ritz vectors via the Krylov{Schur method described in the original paper.
Specically, suppose that in the decomposition (1) the matrix (Uu) is orthonormal.
We compute the partitioned Schur decomposition

T
11
T
12
0 T
22

=

W
H
1
W
H
2

(B + gb
H
)(W
1
W
2
);
where T
11
contains the Ritz values corresponding to the Ritz vectors we wish to retain.
It then follows that the Krylov decomposition
A(UW
1
) = (UW
1
)T
11
+ (uBnZrUg)b
H
W
1
is a Krylov decomposition containing those Ritz vectors. The matrix UW
1
is orthonor-
mal, but the the vector uBnZrUg is not orthogonal to the columns of UW
1
. However, by
a second translation we can orthogonalize it. The resulting decomposition is an orthog-
onal Krylov decomposition, which can be extended by the Arnoldi process in the usual
way.
Acknowledgement
I am indebted to the Mathematical and Computational Sciences Division of the National
Institute of Standards and Technology for the use of their research facilities.
References
[1] Z. Jia and G. W. Stewart. An analysis of the Rayleigh{Ritz method for approxi-
mating eigenspaces. Mathematics of Computation, 70:637{647, 2001.
4 Krylov{Schur Addendum
[2] R. B. Morgan. Computing interior eigenvalues of large matrices. Linear Algebra and
Its Applications, 154{156:289{309, 1991.
[3] G. W.Stewart. A Krylov{Schur algorithm for large eigenproblems. Technical Report
TR{4127, Department of Computer Science, University of Maryland, College Park,
2000. To appear in the SIAM Journal on Matrix Analysis and Applications.
[4] G. W. Stewart. Matrix Algorithms II: Eigensystems. SIAM, Philadelphia, 2001.