Problem formulation
If the potential gains of sparse matrix computation indicated in this chapter are to be realized, it is necessary to consider both efficient implementation and basic problem formulation. For the dense matrix problem, the order n of the matrix controls the requirements for both the storage and solution time to solve a linear system. In fact, quite precise predictions of solution time (O(n3)) and storage (O(n2)) may be made for a properly formulated algorithm (see Section 3.11).
This type of dependence on n becomes totally invalid for sparse problems. This point was demonstrated for the example in Section 1.3, but it should be emphasized that it is true in general. The number of entries in the matrix, т, is a more reliable indicator of work and storage requirements, but even using т, precise predictions similar to those of the dense case are not possible.
For much of the book, we will be concerned with the implementation of the solution to the set of sparse linear equations
where A is an nxn, nonsingular matrix.
However, equation (1.6.1) arises from the formulation of the solution to a mathematical model. How that model is formulated can result in varying amounts of sparsity. Equations like (1.6.1) come from linear least squares problems, circuit simulation problems, control systems problems, and many other sources. In each case, seemingly innocent ‘simplifications’, which may be very helpful in the dense case, can destroy sparsity and make the solution of (1.6.1) either much more costly or infeasible.
It is the authors’ belief that most very complicated physical systems have a mathematical model with a sparse representation. Thus, anyone concerned with the solution of such models must pay careful attention to the way the model is formulated. We will illustrate, though certainly not exhaustively, some examples from diverse applications in Chapter 15. The real benefits of sparsity have depended upon the formulation of the model as well as the choice of solution algorithm.
