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.

See Also:

*^ (Matrix Multiply)

\^ (Matrix Solve)

CHOLESKY

DADiSP/MatrixXL

INVERSE

LLU

MMULT

QR

SVD

ULU