## Documentation Center |

LU-decomposition of a matrix

This functionality does not run in MATLAB.

`linalg::factorLU(``A`)

`linalg::factorLU(A)` computes an LU-decomposition
of an *m*×*n* matrix *A*,
i.e., a decomposition of the *A* into
an *m*×*m* lower
triangular matrix *L* and
an *m*×*n* upper
triangular matrix *U* such
that *P* *A* = *L* *U*,
where *P* is
a permutation matrix.

The diagonal entries of the lower triangular matrix *L* are
equal to one (*Doolittle*-decomposition). The diagonal
entries of *U* are
the pivot elements used during the computation.

The matrices *L* and *U* are
unique.

`pivindex` is a list `[ r _{1},
r_{2}, ...]` representing the row exchanges
of

A floating-point approximation of the decomposition is computed
using `numeric::factorLU`,
if the matrix `A` is defined over the component ring `Dom::Float`. In this case
it is recommended to call `numeric::factorLU` directly
for a better efficiency.

The algorithm also works for singular *A*.
In this case either *L* or *U* is
singular.

*L* and *U* are
nonsingular if and only if *A* is
nonsingular.

The component ring of the matrix `A` must be
a field, i.e., a domain of category `Cat::Field`.

We compute an LU-decomposition of the real matrix:

A := Dom::Matrix(Dom::Real)( [[2, -3, -1], [1, 1, -1], [0, 1, -1]] )

[L, U, pivlist] := linalg::factorLU(A)

The lower triangular matrix *L* is
the first element und the upper triangular matrix *U* is
the second element of the list `LU`. The product
of these two matrices is equal to the input matrix `A`:

L * U

An LU-decomposition of the 3×2 matrix:

A := Dom::Matrix(Dom::Real)([[2, -3], [1, 2], [2, 3]])

gives a 3×3 lower triangular matrix and a 3×2 upper triangular matrix:

[L, U, pivlist] := linalg::factorLU(A)

L * U

To compute the LU-decomposition of the matrix:

A := matrix([[1, 2, -1], [0, 0, 3], [0, 2, -1]])

one row interchange is needed, and we therefore get a non-trivial permutation list:

[L, U, pivlist] := linalg::factorLU(A)

The corresponding permutation matrix is the following:

P := linalg::swapRow(matrix::identity(3), 3, 2)

Hence, we have a decomposition of *A* into
the product of the three matrices
, *L* and *U* as
follows:

P^(-1) * L * U

You may compute an LU-decomposition of a matrix with symbolic components, such as:

delete a, b, c, d: A := matrix([[a, b], [c, d]])

The diagonal entries of the matrix *U* are
the pivot elements used during the computation. They must be non-zero,
if the inverse of *U* is
needed:

[L, U, pivlist] := linalg::factorLU(A)

For example, if we use this decomposition to solve the linear
system
for
arbitrary vectors
,
then the following result is only correct for *a* ≠
0 and
:

delete b1, b2: linalg::matlinsolveLU(L, U, matrix([b1, b2]))

List `[L, U, pivindex]` with the two matrices *L* and *U* of
the domain `Dom::Matrix``(R)` and
a list `pivindex` of positive integers. `R` is
the component ring of `A`.

The following algorithm for solving the system
with
a nonsingular matrix *A* uses
LU-decomposition:

Compute a LU-decomposition of

*A*:*A*=*L**U*.Solve by forward substitution.

Solve by backward substitution.

The LU-decomposition of a matrix *A* is
useful for solving several systems of linear equations
with
the same coefficient matrix *A* and
several right-hand side vectors
,
because then step one of the algorithm above needs to be done only
once.

`linalg::factorCholesky`|`linalg::factorQR`|`linalg::inverseLU`|`linalg::matlinsolveLU`|`lllint`|`numeric::factorLU`

Was this topic helpful?