# LU

## Purpose:

Computes the LU decomposition of a square matrix.

## Syntax:

(l, u) = LU(a, "opt")

(l, u, p) = LU(a, "opt")

 a - A square matrix. "opt" - Optional. A string, if "vector", return the permutation matrix as a 1xN series, else return the full permutation matrix (default).

## Alternate Syntax:

LU(a, type, permute)

a

-

A square matrix.

type

-

Optional. An integer, the type of matrix to return:

 0: Lower LU decomposition matrix. 1: Upper LU decomposition matrix. 2: Complete LU decomposition matrix (default).

permute

-

Optional. An integer, the permutation flag:

 0: No permutation 1: Permute the lower triangular matrix (default).

## Returns:

(l, u) = LU(a) returns the permuted lower triangle matrix and the upper triangular matrix such that l *^ u == a.

(l, u, p) = LU(a) returns the lower and upper triangular matrices and the permutation matrix such that l *^ u == p *^ a.

(l, u, p) = LU(a, "vector") returns the permutation matrix as a single column series.

LU(a, type, permute) returns the lower, upper or complete LU decomposition matrix.

## Example:

A = {{1, 2, 3},

{4, 5, 6},

{7, 8, 10}}

(l, u) = lu(A)

l == {{0.143, 1.000, 0.000},

{0.571, 0.500, 1.000},

{1.000, 0.000, 0.000}}

u == {{7.000, 8.000, 10.000},

{0.000, 0.857,  1.571},

{0.000, 0.000, -0.500}}

l *^ u == {{1, 2, 3},

{4, 5, 6},

{7, 8, 10}}

Matrix A is decomposed into two matrices, l and u such that l *^ u == A. Matrix l is a permuted lower triangular matrix and u is a true upper triangular matrix.

## Example:

A = {{1, 2, 3},

{4, 5, 6},

{7, 8, 10}}

(ll, uu, p) = lu(A)

ll == {{1.000, 0.000, 0.000},

{0.143, 1.000, 0.000},

{0.571, 0.500, 1.000}}

uu == {{7.000, 8.000, 10.000},

{0.000, 0.857,  1.571},

{0.000, 0.000, -0.500}}

p  == {{0, 0, 1},

{1, 0, 0},

{0, 1, 0}}

ll *^ uu == {{7, 8, 10},

{1, 2, 3},

{4, 5, 6}}

p *^ A   == {{7, 8, 10},

{1, 2, 3},

{4, 5, 6}}

Matrix A is decomposed into two matrices, ll and uu such that ll *^ uu == p *^ A. Matrix ll is a true lower triangular matrix and uu is a true upper triangular matrix. The permuted lower triangle matrix from the previous example, l, is related to ll by the following:

p *^ l == ll

## Example:

A = {{1, 2, 3},

{4, 5, 6},

{7, 8, 10}}

(ll, uu, pp) = lu(A, "vector")

ll == {{1.000, 0.000, 0.000},

{0.143, 1.000, 0.000},

{0.571, 0.500, 1.000}}

uu == {{7.000, 8.000, 10.000},

{0.000, 0.857,  1.571},

{0.000, 0.000, -0.500}}

pp  == {3, 1, 2}

The permutation matrix pp is a single column series. This form can significantly reduce memory usage for large input matrices.

## Example:

A = {{1, 2, 3},

{4, 5, 6},

{7, 8, 10}}

b = {14, 32, 53}

(l, u) = lu(A)

v = l \^ b

w = u \^ v

x = A \^ b

w == x == {1, 2, 3}

A *^ w == A *^ x == {14, 32, 53}

Using LU decomposition, the solution x to A *^ x = b can be computed with the triangular system  v = l \^ b and x = u \^ v.

## Example:

A = {{1, 2, 3},

{4, 5, 6},

{7, 8, 10}}

lu(A, 0, 0) = {{1.000, 0.000, 0.000},

{0.143, 1.000, 0.000},

{0.571, 0.500, 1.000}}

## Remarks:

For the LU decomposition of a matrix, A:

(l, u) = lu(A)

A == l *^ u

or:

A == lu(A, 0, 1) *^ lu(A, 1, 1))

or:

A == llu(A) *^ ulu(A)

For matrices A, b and x, where A *^ x = b, and A is square, the built in \^ operator uses LU decomposition such that A \^ b produces matrix x.

See DADiSP/MatrixXL to significantly optimize LU.