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.