A Brief Survey of Direct Linear Solvers

Many of the most effective methods in this book,
in particular those using shift-and-invert,
require the solution of linear systems of the form
or
, where
is a *shift*, usually chosen to be an
approximate eigenvalue of . Much of the time in
these methods can be spent solving these systems, so
it is important to use the best methods available.

There are two basic approaches to solving : direct and iterative. Direct methods typically use variations on Gaussian elimination. They are effective even when is close to an eigenvalue and is nearly singular, which is when iterative methods have most trouble converging. Section 10.4 discusses iterative solvers and when they can be effectively used in some eigenvalue algorithms, such as the Jacobi-Davidson method. This section considers only direct methods.

A direct method for solving will consist of two steps:

- Compute a
*factorization*of . This is the most expensive part. - Use the factorization to solve or .

The choice of algorithm for steps 1 and 2
depends on both the *mathematical structure*
of and the *storage structure* of . By mathematical
structure we most often mean whether is
Hermitian or non-Hermitian, and definite or indefinite.

*Hermitian and definite:*- In this case we compute the
*Cholesky factorization*

, where is a lower triangular matrix. The choice of sign depends on whether is positive definite () or negative definite (). In the sparse case, we may instead compute , where is a permutation matrix. *Hermitian and indefinite:*- In this case we compute the
*Hermitian indefinite factorization*, where is lower triangular, is a permutation matrix, and is block diagonal with 1 by 1 or 2 by 2 blocks, or perhaps tridiagonal. *Non-Hermitian:*- In this case we compute the
*triangular factorization*, where is lower triangular, is upper triangular, and and are permutations (sometimes one is omitted).

By storage structure we mean being dense, banded, sparse (in one of the formats described in §10.1), or structured (such as storing the first row and column of a Toeplitz matrix, which determines the other entries). A sparse non-Hermitian matrix may also be stored in a sparse Hermitian data structure, as in § 10.1.

There are specialized algorithms and software for many combinations of these mathematical and storage structures, and choosing the right algorithm can make orders of magnitude difference in solution time for large matrices. In this section we summarize the best algorithms and software available for these problems. It is often the case that the best algorithm in a research paper is not available as well designed and easily accessible software, and we shall concentrate on available software. We recommend software that is well maintained and in the public domain, or available at low cost, unless none is available.

We consider four cases: methods for dense matrices, methods for band matrices, methods for sparse matrices, and methods for structured matrices, such as Toeplitz matrices.

- Direct Solvers for Dense Matrices
- Direct Solvers for Band Matrices
- Direct Solvers for Sparse Matrices
- Direct Solvers for Structured Matrices