Sparse Matrix Methods
Esmond G. Ng
Lawrence Berkeley National Laboratory
Let A be an n by n nonsingular matrix and b be an n-vector. Assume that A and b are given. As discussed in Chapter 51, the solution of the system of linear equations Ax = b using Gaussian elimination, where x is an unknown n-vector to be computed, requires O(n3) operations, which typically include additions, subtractions, multiplications, and divisions. Computing the solution also requires O(n2) words of storage. The computational complexity is based on the assumption that every element of the matrix has to be stored and operated on. However, linear systems that arise in many scientific and engineering applications can be large; that is, n can ...