ABSTRACT
Let A be an n by n nonsingular matrix and b be an n-vector. As discussed in Chapter 38, Matrix Factorizations and Direct Solution of Linear Systems, the solution of the system of linear equations A x = b using Gaussian elimination requires O(n 3) operations, which typically include additions, subtractions, multiplications, and divisions. The solution also requires O(n 2) 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 be large. It is not uncommon for n to be over hundreds of thousands or even millions. Fortunately, for these linear systems, it is often the case that most of the elements in the matrix A will be zero.
