For a presentation of relevant theory for NHEPs,
as well as pointers to literature, we refer to
§2.5.
In particular, we mention that the perturbation theory for these
problems is delicate. One should keep in mind that a small norm of
the residual
for a computed
eigenpair
does not necessarily imply
small errors
in the computed values. For more information, see §2.5
and §7.13.
Here we will give a brief introduction to those aspects that play a
role in the selection of the algorithms. This will be followed by
short characterizations of the different classes of methods, covered
in this chapter.
In contrast to a Hermitian matrix, a non-Hermitian matrix does
not have an orthogonal set of eigenvectors; in other words,
a non-Hermitian matrix can in
general not be transformed by an orthogonal matrix
to diagonal form
. Most non-Hermitian matrices can be transformed by
a nonorthogonal
to diagonal form
, but there exist matrices for which even
this is not possible. Such matrices can be viewed as limit cases for which
converges to a singular operator, and these matrices do not have a
complete set of eigenvectors; they are called defective. This reveals
a source for numerical instability: if
is in some sense close to a
singular operator, then the transformation may be expected to be sensitive
to perturbations in
. Such perturbations are introduced by the process
for the computation of
and
. Therefore, it is of great importance to
work with orthogonal, or close to orthogonal, transformations as often as
possible. It is well known that for any non-Hermitian matrix
there exists
a unitary matrix
that transforms it to upper triangular form
Reduction to Schur form can be done but it has its price. Let be
the order of a non-Hermitian matrix
. For
, there is in
general no finite algorithm that reduces
to Schur form (if we exclude
trivial cases, such as where
is already upper triangular). The usual
approach for matrices of modest order, say
, is to reduce it
first to upper Hessenberg form which can be done in a finite number of
steps. Subsequently this upper Hessenberg matrix is reduced in an iterative
manner (QR iterations) to Schur form. See §7.3
for more details and for pointers to software.
The main problem with this standard approach is that the computational
costs are proportional to (hence the limitation to matrices of
order of a few thousands at most) and it requires storage proportional
to
elements. In general it is not possible to exploit sparsity of
the matrix
in order to reduce the storage requirements. For these reasons
alternatives have been proposed. These alternatives are all completely
iterative, that is, there is no finite direct reduction step. They are
usually only suitable for the computation of a handful of interesting
eigenpairs. We will now briefly summarize the iterative methods, to be
presented in this chapter.
The orthonormalization process leads to an by
upper Hessenberg matrix
(the approach is only practical for
) and this matrix can be
interpreted as a suitably reduced form of the matrix
restricted to the
Krylov subspace. The eigenvalues of
are approximations for some of the
eigenvalues of
and they can be computed by reducing
to Schur form
by the same standard method as discussed above for small dense matrices.
An introduction to the Arnoldi method is given in §7.5.
Clever restart
techniques have been designed to keep memory requirements and computational
overhead as low as possible: these techniques are known as implicitly
restarted Arnoldi methods (IRAMs) and are discussed
in §7.6.
The computational overhead in the Arnoldi methods is not very suitable
for parallelism, in particular not for some distributed memory computers.
In order to create a larger ratio between computation and memory references
block variants have been suggested. These block Arnoldi variants are
discussed in §7.7.
A block version of the Lanczos method, and an implementation of it called ABLE, are presented in §7.9. ABLE is an adaptively blocked method designed to cure breakdown, and it attempts to eliminate the causes of slow convergence (such as a loss of biorthogonality, and clusters of nearby eigenvalues). Deflation within Krylov subspaces is nicely incorporated in yet another variant, the band Lanczos method, presented in §7.10. This is specially tailored for the reduced-order modeling of multiple-input and multiple-output linear dynamical systems of high dimensions.
A variant of the two-sided Lanczos method for complex symmetric systems is discussed in §7.11. With respect to the unsymmetric case, this variant reduces CPU time and computer storage by a factor of 2.
In Table 7.1 we present a summary of the various classes of methods. The table is not intended to replace further reading; it serves only as an indication of where to start and it may help the reader to follow a certain path in discovering which method serves which need best. The actual performance of each method depends, often critically, on many parameters, and one method that is best for one class of problems may encounter convergence problems for some particular matrices.
Algorithm | Mode | FL-![]() |
![]() |
![]() |
Memory/overhead |
Power | ![]() |
Slow | No | No | Low |
![]() |
Yes | No | No | Low | |
Subspace | ![]() |
Yes | Yes | No | Modest |
![]() |
Yes | Yes | Yes | Modest | |
Arnoldi | ![]() |
Yes | Yes | No | Modest |
(IRAM) |
![]() |
Yes | Yes | Yes | Modest |
Lanczos | ![]() |
Yes | Yes | No | Low |
![]() |
Yes | Yes | Yes | Low | |
Block Lan. | ![]() |
Yes | Yes | No | Modest |
![]() |
Yes | Yes | Yes | Modest | |
Jac.-Dav. | ![]() |
Yes | Yes | Slow | Modest |
![]() |
Yes | Yes | Yes | Modest | |
Precond | Yes | Yes | Yes | Modest |
Explanation of Table 7.1