Templates for Solution of Eigenvalue Problems

To guide our eigenvalue template design, we need to have a model of what the reader wants. We expect that a non-expert user confronted with an eigenvalue problem would be willing to supply

• as few facts as necessary about the operator or operators whose spectral information is desired,
• the kind of spectral information desired (including accuracy), and
• the kind of computer available to solve it (perhaps).

• the software to solve the problem,
• an estimate of how long it will take to solve, and
• a way to assess the accuracy (perhaps).

In the (likely) case that no single best algorithm exists, we expect the user would want a list of reasonable alternatives and a discussion of the tradeoffs in time, space and accuracy among them. For example, it might be reasonable to use a dense algorithm on a sparse problem if high accuracy is desired, the problem is not too large, and/or the problem is to be solved just once. Much of our effort will center on educating the user as to which facts must be supplied to make a decision. To this end we have decided to categorize available methods along five (mostly independent) axes:

1. Mathematical Properties of the Problem,
2. Desired Spectral Information,
3. Problem Representation,
4. Available Transformations, and
5. Costs (including dependence on accuracy, computer type).

Realistically, only a few regions of this five-dimensional space are populated with interesting or useful algorithms, and we expect to have a more decision-tree like approach to guide the user's expectations. The next five section of this paper are organized corresponding to one possible decision tree. The first ``level'' of the tree distinguishes problems according to their mathematical properties. The second level asks for desired spectral information, and so on.

This is not the only way to organize the decision tree. For example, a different user may wish to specify the desired spectral information later, in order to get a list of all possible algorithms relevant to her problem. Indeed, the actual internal organization of the tree may more resemble a lattice, since the some basic algorithms will be used many times in slightly different ways. Nonetheless, we believe these five axes are a good organizational tool for us to make sure we have covered all interesting cases, or at least limit the scope of what we want in an organized way. At this point, we invite suggestions as to the scope of our proposed project, whether we have left anything important out, or included something of lesser importance. Briefly, we only want to include a problem type if there is significant demand, and exploiting its special features confers significant performance or accuracy advantages over using a more general purpose algorithm. We want to keep the project small enough to come out with a reference book of at most two hundred pages (or the equivalent in html) within 2 years.

• Notation
• Mathematical Properties
  • What we plan to include
  • What we plan not to include
• Desired Spectral Information
  • Self-adjoint Eigenproblems
  • Non-self-adjoint Eigenproblems
• Problem Representation
• Available Operations
• Basic Iterative Algorithms
• Cost Issues
• Accuracy Issues
• Format of Results