Introduction and Motivation

next up previous
Next: Related Work Up: Templates for Linear Algebra Previous: Templates for Linear Algebra

Introduction and Motivation

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:

It may seem difficult to address the needs of such diverse communities with a single document. Nevertheless, we believe this is possible in the form of templates.

A template for an algorithm includes

  1. A high-level description of the algorithm.
  2. A description of when it is effective, including conditions on the input, and estimates of the time, space or other resources required. If there are natural competitors, they will be referenced.
  3. A description of available refinements and user-tunable parameters, as well as advice on when to use them.
  4. Pointers to complete or partial implementations, perhaps in several languages or for several architectures (each parallel architecture). These implementation expose those details suitable for user-tuning, and hide the others.
  5. Numerical examples, on a common set of examples, illustrating both easy cases and difficult cases.
  6. Trouble shooting advice.
  7. Pointers to texts or journal articles for further information.
In addition to individual templates, there will be a decision tree to help steer the user to the right algorithm, or subset of possible algorithms, based on a sequence of questions about the nature of the problem to be solved.

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.

next up previous
Next: Related Work Up: Templates for Linear Algebra Previous: Templates for Linear Algebra

Jack Dongarra
Wed Jun 21 02:35:11 EDT 1995