3.4 Computational Complexity of Linear Systems

As was mentioned in Section 3.1, the decomposition algorithm for solving linear equations is motivated by the computational inefficiency of matrix inversion. Inverting a dense matrix A requires


floating point operations. Computing the LU decomposition of A requires




floating point operations. Computing x from the factorization requires




floating point operations (which is equivalent to computing the product A-1b). Therefore, solving a linear system of equations by matrix inversion requires approximately three times the amount of work as a solution via LU decomposition.

When A is a sparse matrix, the computational discrepancy between the two methods becomes even more overwhelming. The reason is straightforward. In general,

  • Inversion destroys the sparsity of A, whereas

  • LU decomposition preserves the sparsity of A.

Much work can be avoided by taking advantage of the sparsity of a matrix and its triangular factors. Algorithms for solving sparse systems of equations are are described in detail in Section 8 of this document.