LU Decomposition

The LU decomposition of a matrix is frequently used as part of a Gaussian elimination process for solving a matrix equation. In Mathematica there is no need to use an LU decomposition to solve a matrix equation, because the function LinearSolve does this for you, as discussed in the section Solving Linear Systems. Note that if you want to save the factorization of a matrix, so that it can be used to solve the same left-hand side, you can use the one argument form of LinearSolve, as demonstrated in the section Saving the Factorization.

The LU decomposition with partial pivoting of a square non-singular matrix involves the computation of the unique matrices , , and such that

where is lower triangular with ones on the diagonal, is upper triangular, and is a permutation matrix. Once it is found, it can be used to solve the matrix equation by finding the solution to the following equivalent system.

This can be done by first solving for in the following.

Then solve for to get the desired solution.

Because both and are triangular matrices it is particularly easy to solve these systems.

Despite the fact that in Mathematica you do not need to use the LU decomposition for solving matrix equations, Mathematica provides the function LUDecomposition for computing the LU decomposition.

LUDecomposition returns a list of three elements. The first element is a combination of upper and lower triangular matrices, the second element is a vector specifying rows used for pivoting (a permutation vector which is equivalent to the permutation matrix), and the third element is an estimate of the condition number.

In this example, the three results of the LUDecomposition computation are shown.

In[1]:=

Out[2]=

One of the features of the LU decomposition is that the lower and upper matrices are stored in the same matrix. The individual and factors can be obtained as follows. Note how they use a vectorized operation for element by element multiplication with a sparse matrix. This makes the process more efficient; these techniques are discussed further in the section Programming Efficiency.

This generates the matrix.

In[3]:=

Out[7]//MatrixForm=

This generates the matrix.

In[8]:=

Out[11]//MatrixForm=

The original matrix was non-singular and so this is a factorization. Therefore multiplying and recreates the original matrix permuted with the row pivot vector.

In[12]:=

Out[12]=

The following subtracts the product of the and matrices from the permuted original matrix. The difference is very close to zero.

In[13]:=

Out[13]=

The diagonal elements in the matrix are known as the pivots. If any zero pivots emerge during a computation of the LU factorization this means that the matrix is singular. In such a case LUDecomposition produces a warning.

In[14]:=

Out[15]=