## `numeric::factorLU` -- LU factorization of a matrix

#### Introduction

`numeric::factorLU``(A, ..)` returns a LU factorization PA=LU of the matrix A.

#### Call(s)

`numeric::factorLU(A <, Symbolic>)`

#### Parameters

`A` | - | an m x n matrix of domain type `DOM_ARRAY` or of category `Cat::Matrix`

#### Options

`Symbolic` | - | prevents `numeric::factorLU` from using floating point arithmetic

#### Returns

A list `[L,U,p]` is returned. The matrices `L` and `U` are of domain type `DOM_ARRAY`, `p` is a list of integer numbers 1,..,m representing the row exchanges in pivoting steps. The components of `L` and `U` are real or complex floats, unless the option Symbolic is used.

#### Side Effects

Without the optional argument Symbolic the function is sensitive to the environment variable `DIGITS`, which determines the numerical working precision.

#### Related Functions

`linalg::factorLU`, `numeric::factorCholesky`, `numeric::factorQR`

#### Details

- The LU factorization of a real or complex m x n matrix is PA=LU. The m x m matrix L is lower triangular normalized to 1 along the diagonal. The m x n matrix U is upper triangular, i.e., U[i,j]=0 for j<i. The list `p=[p[1],..,p[m]]` returned by `numeric::factorLU` is a permutation of the numbers 1,..,m corresponding to row exchanges of A. It represents the m x m permutation matrix P:

                    P[i,j] = 1, if j=p[i],
                    P[i,j] = 0, if j<>p[i].

  Multiplication of P with matrices and vectors is performed easily using the permutation list `p`:

  `Y[i,j]:=X[p[i],j]` defines the permutation Y=PX of a matrix X,

  `y[i]:=x[p[i]]` defines the permutation y=Px of a vector x.

- By default a numerical factorization with partial pivoting is computed. If the option Symbolic is not used, then all components of the matrix are converted to floating point numbers. In this case the matrix must not contain symbolic objects that cannot be converted to floats. Numerical symbolic expressions such as `PI`, `sqrt(2)`, `exp(-1)` etc. are accepted.
- The factorization depends on the pivoting strategy. The results obtained with/without the option Symbolic may differ. Cf. example 2.

#### Option: Symbolic

- This option prevents conversion of the matrix entries to floats. The usual arithmetic for MuPAD expressions is used. With this option the matrix A may contain symbolic objects.
- With this option no row exchanges are performed in the internal Gaussian elimination unless necessary.

#### Example 1

We consider the matrix

    >> A := array(1..3, 1..3, [[1, 2, 3], [2, 4, 6], [4, 8, 9]]):

    >> [L, U, p] := numeric::factorLU(A)

              -- +-            -+  +-                -+            --
              |  |    1,  0, 0  |  |  4.0, 8.0,  9.0  |             |
              |  |              |  |                  |             |
              |  |   0.5, 1, 0  |, |   0,   0,   1.5  |, [3, 2, 1]  |
              |  |              |  |                  |             |
              |  |  0.25, 0, 1  |  |   0,   0,  0.75  |             |
              -- +-            -+  +-                -+            --

The factors (of domain type `DOM_ARRAY`) are converted to elements of the matrix domain `Dom::Matrix()` for further processing:

    >> M := Dom::Matrix(): L := M(L): U := M(U):

Now the overloaded arithmetical operators `+`, `*`, `^` etc. can be used for further computations:

    >> L*U

                                +-               -+
                                |  4.0, 8.0, 9.0  |
                                |                 |
                                |  2.0, 4.0, 6.0  |
                                |                 |
                                |  1.0, 2.0, 3.0  |
                                +-               -+

The product LU coincides with A after exchanging the rows according to the permutation `p`:

    >> PA := array(1..3, 1..3, [[A[p[i], j] $ j=1..3] $ i=1..3])

                                   +-         -+
                                   |  4, 8, 9  |
                                   |           |
                                   |  2, 4, 6  |
                                   |           |
                                   |  1, 2, 3  |
                                   +-         -+

    >> delete A, L, U, p, M, PA:

#### Example 2

We consider a non-square matrix:

    >> A := array(1..3, 1..2, [[3*I, 10], [I, 1], [I, 1]]):

    >> numeric::factorLU(A)

                -- +-           -+  +-            -+            --
                |  |   1,  0, 0  |  |  1.0 I, 1.0  |             |
                |  |             |  |              |             |
                |  |  3.0, 1, 0  |, |    0,   7.0  |, [2, 1, 3]  |
                |  |             |  |              |             |
                |  |  1.0, 0, 1  |  |    0,    0   |             |
                -- +-           -+  +-            -+            --

Note that the symbolic factorization is different, because a different pivoting strategy is used:

    >> numeric::factorLU(A, Symbolic)

                 -- +-           -+  +-           -+            --
                 |  |   1,  0, 0  |  |  3 I,  10   |             |
                 |  |             |  |             |             |
                 |  |  1/3, 1, 0  |, |   0,  -7/3  |, [1, 2, 3]  |
                 |  |             |  |             |             |
                 |  |  1/3, 1, 1  |  |   0,    0   |             |
                 -- +-           -+  +-           -+            --

    >> delete A:

#### Changes

- Factorization was extended to non-square matrices.
- The type of the returned matrix factors was changed to `DOM_ARRAY`.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000