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

2n3+O(n2)2{n}^{3}+O\left({n}^{2}\right)

floating point operations. Computing the LU decomposition of A requires

23n3+12n2+16n\frac{2}{3}{n}^{3}+\frac{1}{2}{n}^{2}+\frac{1}{6}n

or

23n3+O(n2)\frac{2}{3}{n}^{3}+O\left({n}^{2}\right)

floating point operations. Computing x from the factorization requires

2n2+n2{n}^{2}+n

or

2n2+O(n)2{n}^{2}+O\left(n\right)

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.