A system of linear equations is called sparse if only a relatively small number of its matrix elements aij are nonzero. It is wasteful to use general methods of linear algebra on such problems, because most of the O(N 3 ) arithmetic operations devoted to solving the set of equations or inverting the matrix involve zero operands. Furthermore, you might wish to work problems so large as to tax your available memory space, and it is wasteful to reserve storage for unfruitful zero elements. | Sparse Linear Systems 71 Sparse Linear Systems A system of linear equations is called sparse if only a relatively small number of its matrix elements ai j are nonzero. It is wasteful to use general methods of linear algebra on such problems because most of the O N3 arithmetic operations devoted to solving the set of equations or inverting the matrix involve zero operands. Furthermore you might wish to work problems so large as to tax your available memory space and it is wasteful to reserve storage for unfruitful zero elements. Note that there are two distinct and not always compatible goals for any sparse matrix method saving time and or saving space. We have already considered one archetypal sparse form in the band diagonal matrix. In the tridiagonal case . we saw that it was possible to save both time order N instead of N3 and space order N instead of N2 . The method of solution was not different in principle from the general method of LU decomposition it was just applied cleverly and with due attentionto the bookkeeping of zero elements. Many practical schemes for dealing with sparse problems have this same character. They are fundamentally decomposition schemes or else elimination schemes akin to Gauss-Jordan but carefully optimized so as to minimize the number of so-called fill-ins initially zero elements which must become nonzero during the solution process and for which storage must be reserved. Direct methods for solving sparse equations then depend crucially on the precise pattern of sparsity of the matrix. Patterns that occur frequently or that are useful as way-stations in the reduction of more general forms already have special names and special methods of solution. We do not have space here for any detailed review of these. References listed at the end of this section will furnish you with an in to the specialized literature and the following list of buzz words and Figure will at least let you hold your own at cocktail parties .
