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

- Band 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.

Wed Jun 21 02:35:11 EDT 1995