 ...Methods

This work was supported in part by
DARPA and ARO under contract number DAAL0391C0047,
the National Science Foundation Science and Technology Center Cooperative
Agreement No. CCR8809615,
the Applied Mathematical Sciences subprogram of the Office of
Energy Research, U.S. Department of Energy, under Contract
DEAC0584OR21400,
and
the Stichting Nationale Computer Faciliteit (NCF) by Grant CRG 92.03.
 ...Barrett
 Department of Computer Science, University of
Tennessee, Knoxville, TN 379961301.
 ...Chan
 Applied Mathematics Department,
University of California, Los Angeles, CA 900241555.
 ...Demmel
 Computer Science Division and Mathematics
Department, University of California, Berkeley, CA 94720.
 ...Donato
 Mathematical Sciences Section,
Oak Ridge National Laboratory, Oak Ridge, TN 378316367.
 ...Vorst
 Department of Mathematics, Utrecht University, Utrecht, the
Netherlands.
 ...BLAS
 For a discussion of BLAS as building
blocks, see [141][68][67][66] and
LAPACK routines [3]. Also, see
Appendix .
 ...methods
 For a more detailed account of the early
history of CG methods, we refer the reader to Golub and
O'Leary [107] and
Hestenes [122].
 ...improvement.
 Under certain conditions, one can show
that the point Jacobi algorithm is optimal, or close to optimal, in
the sense of reducing the condition number, among all
preconditioners of diagonal form. This was shown by Forsythe and
Strauss for matrices with Property A [96], and by van der
Sluis [193] for general sparse matrices. For
extensions to block Jacobi preconditioners, see
Demmel [63] and Elsner [91].
 ...preconditioner
 The SOR and GaussSeidel matrices are never used as preconditioners,
for a rather technical reason.
SORpreconditioning with optimal maps the eigenvalues of the
coefficient matrix to a circle in the complex plane;
see Hageman and Young [.3]HaYo:applied. In this case no
polynomial acceleration is possible, i.e., the accelerating polynomial
reduces to the trivial polynomial , and the resulting
method is simply the stationary SOR method.
Recent research by Eiermann and Varga [81] has shown
that polynomial
acceleration of SOR with suboptimal will yield no improvement
over simple SOR with optimal .
 ...zero
 The zero refers to the fact that only ``level zero'' fill is
permitted, that is, nonzero elements of the original matrix. Fill
levels are defined by calling an element of level if it is
caused by elements at least one of which is of level .
The first fill level is that caused by the original matrix elements.
 ...blocks.
 Writing is equally valid, but in practice
is harder to implement.
 ....
 On a machine with IEEE Standard
Floating Point Arithmetic,
in single precision, and
in double precision.
 ...finite
 IEEE standard
floating point arithmetic permits computations with and
NaN, or NotaNumber, symbols.