Large scale problems of engineering and scientific computing often require solutions of linear algebra problems, such as systems of linear equations, least squares problems, or eigenvalue problems. There is a vast amount of material available on solving such problems, in books, in journal articles, and as software. This software consists of well-maintained libraries available commercially or electronically in the public-domain, other libraries distributed with texts or other books, individual subroutines tested and published by organizations like the ACM, and yet more software available from individuals or electronic sources like Netlib [21], which may be hard to find or come without support. So although many challenging numerical linear algebra problems still await satisfactory solutions, many excellent methods exist from a plethora of sources.
But the sheer number of algorithms and their implementations makes it hard even for experts, let alone general users, to find the best solution for a given problem. This has led to the development of various on-line search facilities for numerical software. One has been developed by NIST (National Institute of Standards and Technology), and is called GAMS (Guide to Available Mathematical Software) [7]; another is part of Netlib [21]. These facilities permit search based on library names, subroutines names, keywords, and a taxonomy of topics in numerical computing. But for the general user in search of advice as to which algorithm or which subroutine to use for her particular problem, they offer relatively little advice.
Furthermore, many challenging problems cannot be solved with existing ``black-box'' software packages in a reasonable time or space. This means that more special purpose methods must be used, and tuned for the problem at hand. This tuning is the greatest challenge, since there are a large number of tuning options available, and for many problems it is a challenge to get any acceptable answer at all, or have confidence in what is computed. The expertise regarding which options, or combinations of options, is likely to work in a specific application area, is widely distributed.
Thus, there is a need for tools to help users pick the best algorithm and implementation for their numerical problems, as well as expert advice on how to tune them. In fact, we see three potential user communities for such tools:
A template for an algorithm includes
Our goal in this paper is to outline such a set of templates for systems of linear equations and eigenvalue problems. The main theme is to explain how to use iterative methods.
The rest of this paper is organized as follows. Section 2 discusses related work. Section 3 describes the work we have done on templates for sparse linear systems. Section 4 described our taxonomy of eigenvalue problems and algorithms, which we will use to organize the templates and design a decision tree. Section 4.1 discusses notation and terminology. Sections 4.2 through 4.7 below describe the decision tree in more detail. Section 4.8 outlines a chapter on accuracy issues, which is meant to describe what accuracy one can expect to achieve, since eigenproblems can be very ill-conditioned, as well as tools for measuring accuracy. Section 4.9 describes the formats in which we expect to deliver both software and documentation.
This paper is a design document, and we encourage feedback, especially from potential users.