TABLE OF CONTENTS As described in the previous chapter, standard discretizations of partial differential equations (PDEs) typically lead to large and sparse matrices. A sparse matrix is defined, somewhat vaguely, as a matrix with very few nonzero elements. But, in fact, a matrix can be termed sparse whenever special techniques can be utilized to take advantage of the large number of zero elements and their locations. These sparse matrix techniques begin with the idea that the zero elements need not be stored. One of the key issues is to define data structures for these matrices that are well suited for efficient implementation of standard solution methods, whether direct or iterative. This chapter gives an overview of sparse matrices, their properties, their representations, and the data structures used to store them.
The natural idea to take advantage of the zeros of a matrix and their location was initiated by engineers in various disciplines. In the simplest case involving banded matrices, special techniques are straightforward to develop. Electrical engineers dealing with electrical networks in the 1960s were the first to exploit sparsity to solve general sparse linear system for matrices with irregular structure. The main issue, and the first addressed by sparse matrix technology, was to devise direct solution methods for linear systems. These had to be economical in terms of both storage and computational effort. Sparse direct solvers can handle very large problems that cannot be tackled by the usual "dense" solvers.
Essentially, there are two broad types of sparse matrices:
