Problem Representation

First we discuss the type of individual matrix or operator entries. The simplest distinction is between real and complex data. The issues are speed (real arithmetic is faster than complex), storage (real numbers require half the storage of complex numbers), code complexity (some algorithms simplify greatly if we can do complex arithmetic), and stability (real arithmetic can guarantee complex conjugate eigenvalues of real matrices). The distinction between single and double precision, which clearly affects space, will be discussed again as an accuracy issue.

Given the type of individual operator entries, we must distinguish the overall structure of the operator. Here is our list. Two letter abbreviations (like GE) refer to matrix types supported by LAPACK [Table 2.1]lapackmanual2.

• Dense matrices
  • General (GE)
  • Hermitian, with only upper or lower half defined (SY or HE)
  • Hermitian, packed into half the space (SP or HP)
• Matrices depending systematically on data.
  • Band matrices
    • Bidiagonal matrices, stored as two arrays (BD)
    • Tridiagonal matrices, stored as two or three arrays (ST, GT)
    • Wider band matrices (GB, SB, HB)
    • Band matrices with bulges (``look ahead'' matrices)
  • Arrow, Toeplitz, Hankel, Circulant, and Companion matrices
  • Diagonal + rank-1 matrices, band + low rank matrices
• Sparse matrices, or those depending less systematically on data. It turns out that the relevant classification is by the operations that can be performed on the operators represented, not the details of the representation. This will be clearer in Section 4.5.
  • can solve the linear system
  • Matrix-vector multiplication possible (and ) (this includes, for example, ``dense'' integral operators which have fast algorithms for performing .)
  • under SVD or GSVD, possible to factor or , or , perhaps shifted

There are many more special structures, often arising from control theory, such as unitary orthogonal matrices represented by their Schur parameters. Until we hear of a large demand for such problems, we do not plan to include them, other than as literature references. For the same reason we also do not plan to include algorithms for quaternion matrices, or matrices with rational entries, which are more properly included in the domain of symbolic computation.