Why Eigenvalue Templates?

In many large scale scientific or engineering computations, ranging from computing the frequency response of a circuit to the earthquake response of a building to the energy levels of a molecule, one needs to find eigenvalues and eigenvectors of a matrix. There are many mathematical ways to formulate eigenvalue problems, and even more ways have been proposed to solve them numerically. This book is intended to be a guide to finding the best numerical method for an eigenvalue problem.

The current state of the art is such that excellent methods
exist for many eigenproblems, especially for small- to
medium-sized dense matrices. These algorithms have been made
available in programming environments like
MATLAB [319],^{}
libraries
like LAPACK [12], and many other commercial and public packages.
But for very large and (typically) sparse eigenvalue problems
no single best method exists. The sheer number of methods
and the complicated ways they depend on mathematical properties
of the matrix and trade off efficiency and accuracy make
it difficult for experts, let alone general users, to find
the best method for a given problem. Good online search
facilities and software repositories exist, notably
GAMS (Guide to Available Mathematical
Software)^{}and
NETLIB.^{}
These
facilities permit searches based on library names, subroutines names,
key words, and a taxonomy of topics in numerical computing.
But they will not give advice as to which method
is best to use for a particular problem.
As a result, the authors of this book
and other experts are frequently asked for advice
in choosing an algorithm. This situation has motivated us
to distill our knowledge into this book to make it as widely
available as possible.

Here is how we have structured the book.
First, we have developed a *decision tree* to
guide the user to the best method. Each node
in the tree poses questions about the problem
regarding its mathematical structure, the quantities
to be computed, and the cost of applying certain
operations to the matrix.
Second, at the leaves of the decision tree we
present *templates* of recommended algorithms,
as well as pointers to available software.
A template is a high-level description of an
algorithm, suitable for understanding how it
works, what parameters the user can tune
to control efficiency and accuracy, and how
to interpret the output.
We discuss this structure in more detail below.

The original model for this book was *Templates for the Solution of Linear
Systems: Building Blocks for Iterative Methods* [41].
This earlier book (which has some authors in common with this one)
provided a decision tree and templates for iterative methods for
the simpler problem of solving a linear system.
Eigenvalue problems are inherently more difficult than linear systems,
and this means that our level of understanding varies significantly,
depending on the eigenvalue problem at hand. Furthermore, the
algorithms are much more complicated. So in contrast to this earlier
*Templates* book, we have not attempted to provide complete implementations
of each template in a common style and in common programming languages.
Instead, we provide a high-level template of each algorithm and
point to good public domain implementations in whatever language they
are available. All these implementations
may be accessed through a Web site we call ETHOME in the text, which
refers to
`http://www.netlib.org/etemplates/.`
This Web site will be updated as new and better
algorithms become available.

The variety of eigenproblems covered in this book is very wide. Some algorithms are well known and have been thoroughly investigated, whereas other areas are still subject to intensive research. This has led to differences in the style of presentation. Well-understood areas with good ``black box'' solutions have been kept brief and are written primarily for nonexpert readers, whereas at the other extreme there are contributions that review current research.

In most sections we explicitly name the contributing authors. This is not only for credit reasons, but also reflects personal responsibility for the text. All sections provide sufficient references to serve as windows to a richer world of detail and expertise on eigenproblems.