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.