Footnotes
 ...\title

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.
 ...\author
 Los Alamos National Laboratory,
Los Alamos, NM 87544.
 ...\author
 Department of Computer Science, University of
Tennessee, Knoxville, TN 379961301.
 ...\author
 Applied Mathematics Department,
University of California, Los Angeles, CA 900241555.
 ...\author
 Computer Science Division and Mathematics
Department, University of California, Berkeley, CA 94720.
 ...\author
 Mathematical Sciences Section,
Oak Ridge National Laboratory, Oak Ridge, TN 378316367.
 ...\author
 National Institute of Standards and Technology,
Gaithersburg, MD, 20899
 ...\author
 Department of Mathematics, Utrecht University, Utrecht, the
Netherlands.
 ...
 For a discussion of BLAS as building
blocks, see [144][71][70][69] and
LAPACK routines [3]. Also, see
Appendix .
 ...
 For a more detailed account of the early
history of CG methods, we refer the reader to Golub and
O'Leary [108] and
Hestenes [123].
 ...
 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 [99], and by van der
Sluis [198] for general sparse matrices. For
extensions to block Jacobi preconditioners, see
Demmel [66] and Elsner [95].
 ...
 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 [84] has shown
that polynomial
acceleration of SOR with suboptimal will yield no improvement
over simple SOR with optimal .
 ...
 To be precise, if we make an incomplete factorization , we
refer to positions in and when we talk of positions in the
factorization. The matrix will have more nonzeros than and
combined.
 ...
 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.
 ...
 In graph theoretical terms, and 
coincide if the matrix graph contains no triangles.
 ...
 Writing is equally valid, but in practice
harder to implement.
 ...
 On a machine with IEEE Standard
Floating Point Arithmetic,
in single precision, and
in double precision.
 ...
 IEEE standard
floating point arithmetic permits computations with and
NaN, or NotaNumber, symbols.
 ...

Jack Dongarra
Mon Nov 20 08:52:54 EST 1995