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:

- Mathematical Properties of the Problem,
- Desired Spectral Information,
- Problem Representation,
- Available Transformations, and
- 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
- Desired Spectral Information
- Problem Representation
- Available Operations
- Basic Iterative Algorithms
- Cost Issues
- Accuracy Issues
- Format of Results

Wed Jun 21 02:35:11 EDT 1995