The LUDecomposition command computes a PLU decomposition, a modified PLU1R decomposition, or a Cholesky decomposition of the Matrix A.

Depending on what is included in the output option (out), an expression sequence containing one or more of the factors P, L, U, U1, R, the compact NAG form, an abstract representation of the factored matrix as processed by the SparseDirectMKL method (called a handle), the determinant, and the rank can be returned. The objects are returned in the same order as specified in the output list.

Note:  Either U or the pair U1 and R may be returned, but not both.

The LUDecomposition(A) calling sequence is equivalent, by default, to LUDecomposition(A, method='GaussianElimination'). If A has both symmetric or $\mathrm{hermitian}$ shape and positive_definite attributes, then the LUDecomposition(A) calling sequence is equivalent to LUDecomposition(A, method='Cholesky').

The LUDecomposition(A, method='GaussianElimination') calling sequence is equivalent to LUDecomposition(A, method='GaussianElimination', output=['P','L','U']). This PLU decomposition generates a square unit lower triangular L factor and an upper triangular factor U with the same dimensions as A so that $A=P·L·U$.  The Matrix P is a permutation Matrix.

The selection of pivots in the $\mathrm{GaussianElimination}$ method differs according to the type of the Matrix entries. For Matrices with numeric entries and at least one floating-point entry, pivots are selected according to absolute magnitude. For Matrices with only exact rational or symbolic entries, pivots are selected as the first nonzero element in the current column, moving downwards from the current row.

The PLU1R decomposition is achieved by using LUDecomposition(A, method='RREF') or LUDecomposition(A, output=['P','L','U1','R']).  This further factors U into $\mathrm{U1}·R$ where U1 is square upper triangular factor and R is the unique reduced row echelon form of the Matrix A. In this case, $A=P·L·\mathrm{U1}·R$. The option $\mathrm{method}='\mathrm{Cholesky}'$ is incompatible with providing either $'\mathrm{U1}'$ or $'R'$ in the out list.

The PLU decomposition obtained by using method='FractionFree' generates a square non-unit lower triangular L factor and fraction-free upper triangular factor U with the same dimensions as A so that $A=P·L·U$. The Matrix P is a permutation Matrix.

The Cholesky decomposition of the positive definite Matrix A can be obtained by using LUDecomposition(A, method='Cholesky') which generates the square lower triangular factor L. If A is real symmetric, then $A=L·\mathrm{Transpose}\left(L\right)$; if A is complex hermitian, then $A=L·\mathrm{HermitianTranspose}\left(L\right)$. The factor $U=\mathrm{HermitianTranspose}\left(L\right)$ can be generated using the calling sequence LUDecomposition(A, method='Cholesky', output=['U']).

For the Cholesky decomposition, if A is neither real symmetric nor complex hermitian, then a library-level warning is generated. In such a case, A is treated as if it were hermitian or symmetric, with only one of the upper or lower triangles of A being accessed. For floating-point data, the upper triangle of A is used if the factor $U$ is requested; otherwise, the lower triangle of A is used. For exact data, the upper triangle of A is used.

If the SparseDirect or (equivalently) SparseDirectMKL method is selected, an abstract representation of the matrix factorization is returned. This representation can be used with the LinearSolve command. It is not possible to retrieve the individual factors from this abstract representation.

The SparseDirect and SparseDirectMKL methods use routines from the Intel oneAPI Math Kernel Library (software.intel.com/en-us/intel-mkl). This library is not available on Apple Silicon Macs when running native binaries.  In order to use the SparseDirect or SparseDirectMKL methods on such computers, start the Intel x86-64 version of Maple.  For more information, see Platform Specific Issues.

If  m is not specified in the calling sequence, method='none' is used. Note:  method='none' is equivalent to method='GaussianElimination'.

In the case of Cholesky decomposition, the Hermitian transpose is used by default. If conjugate=false is specified in the calling sequence, the ordinary transpose is used.

The output option (out) determines the content of the returned expression sequence.

If output='NAG' and method='Cholesky' are specified in the calling sequence, then the output  consists of a Matrix whose lower triangle contains the data of the lower triangular factorization. The entries above the diagonal may not be set to zero.

If output='NAG' is specified and the Cholesky factorization method is not used, then the output is an expression sequence consisting of a Vector followed by a Matrix. The upper triangle of the Matrix is the U factor and the strictly lower triangle is the L factor (with implicit ones along the diagonal). The Vector is the NAG-style pivot Vector.

If NAG is included in the output list, all other output entries are excluded with the exception of determinant and rank.

If handle is included in the output list, nothing else can be included. This output is only available with the SparseDirect and SparseDirectMKL methods, and conversely, when using the SparseDirect or SparseDirectMKL methods, only the handle output can be requested.

The inplace option (ip) determines where the result is returned. If given as inplace=true and either U or NAG is included in the output list, the result overwrites the first argument. If given as inplace=false, or if this option is not included in the calling sequence, the result is returned in a new Matrix.

The condition inplace=true can be abbreviated to inplace.

The inplace option must be used with caution since, if the operation fails, the original Matrix argument may be corrupted.

The constructor options provide additional information (readonly, shape, storage, order, datatype, and attributes) to the Matrix or Vector constructor that builds the result(s). These options may also be provided in the form outputoptions[o]=[...], where [...] represents a Maple list.  If a constructor option is provided in both the calling sequence directly and in an outputoptions[o] option, the latter takes precedence (regardless of the order).

The following list indicates permissible values for index [o] of outputoptions with their corresponding meaning.

The inplace and constructor options are mutually exclusive.

The SparseDirect and SparseDirectMKL methods are only available for matrices that are in (or can be converted to) NAG-sparse form. That is, the datatype as returned by rtable_options needs to be one of these values:

$\mathrm{sfloat},\mathrm{complex}\left(\mathrm{sfloat}\right),{\mathrm{integer}}_1,{\mathrm{integer}}_2,{\mathrm{integer}}_4,{\mathrm{integer}}_8,{\mathrm{float}}_4,{\mathrm{float}}_8,{\mathrm{complex}}_8$

The data type will internally be converted to ${\mathrm{float}}_8$ or ${\mathrm{complex}}_8$ if it isn't one of these types already. Note that this method is most useful for sparse matrices.

The SparseDirect and SparseDirectMKL methods are the only methods that accept A as being a list of 3 Vectors. These 3 Vectors should form the compressed sparse row form of the Matrix to be factored. If A is a Matrix and these methods are selected, the compressed sparse row form is computed with the CompressedSparseForm command, with the options form = row, includediagonal = true, and, if structural symmetry is selected, structuralsymmetry = true. If symmetry = symmetric or symmetry = hermitian is selected, the code ensures that A has upper triangular storage. If you want to construct or modify the compressed sparse row form of A manually, you need to ensure that similar precautions are taken.

The SparseDirect and SparseDirectMKL methods are the only methods that accept the mopts argument. These method-specific options can have this form:

domain = real or complex

This specifies whether a factorization over the real or complex domain is performed. By default, this is determined as follows: if the data type of A (or the third entry of A if A is a list of 3 Vectors) is ${\mathrm{float}}_8$ or ${\mathrm{complex}}_8$, then the domain is selected as real or complex, respectively. Otherwise, Maple attempts to convert the values in A to type ${\mathrm{float}}_8$. If this is successful, it selects the real domain. Otherwise, the values are converted to ${\mathrm{complex}}_8$ and the complex domain is selected.

symmetry = none or structural or symmetric or hermitian

This specifies what symmetry properties can be used for A:

With symmetry = none, no symmetry properties are assumed.

With symmetry = structural, the solver requires that there is an entry $A_{i,j}$ in the compressed sparse row representation of A whenever there is an entry $A_{j,i}$, but no relationship between the two is assumed.

With symmetry = symmetric, the solver requires that $A_{i,j}=A_{j,i}$ for all $i,j$. Only the upper diagonal entries of A are submitted to the solver.

With symmetry = hermitian, the solver requires that $A_{i,j}=\stackrel{\&conjugate0;}{A_{j,i}}$ for all $i,j$. Only the upper diagonal entries of A are submitted to the solver.

If A is a list of 3 Vectors, then by default, no symmetry is assumed. If A is a Matrix, then Maple uses the appropriate type of symmetry if the indexing function is symmetric or hermitian, and no symmetry otherwise.

definite = indefinite or positive

With certain combinations of symmetry and domain, the solver can use positive definiteness of A if it applies. You can specify whether A is positive definite using the option definite = positive or force Maple not to use definiteness by specifying definite = indefinite. By default, if A is a list of 3 Vectors, Maple assumes A is not positive definite. If A is a Matrix, then Maple assumes that A is positive definite only if A has the attribute positive_definite.

The LU decomposition of a Matrix can be used as input for the LinearSolve, MatrixInverse, and ConditionNumber commands. For more details on how to do this, see these help pages.

For more information on the P.L.U1.R decomposition see: Corless, Robert M, and Jeffrey, David J, "The Turing Factorization of a Rectangular Matrix," Sigsam Bulletin 31, no. 3 (September 1997): 20-28. This paper names the U1 factor U.

This function is part of the LinearAlgebra package, and so it can be used in the form LUDecomposition(..) only after executing the command with(LinearAlgebra). However, it can always be accessed through the long form of the command by using LinearAlgebra[LUDecomposition](..).

$\mathrm{with}\left(\mathrm{LinearAlgebra}\right)\:$

$A≔⟨⟨0\,-2\,0\,3⟩\left|⟨1\,3\,0\,1⟩\right|⟨1\,1\,0\,0⟩|⟨-3\,4\,1\,0⟩⟩$

$A≔\left[\begin{array}{cccc}0& 1& 1& \mathrm{-3}\\ \mathrm{-2}& 3& 1& 4\\ 0& 0& 0& 1\\ 3& 1& 0& 0\end{array}\right]$

$p,l,u≔\mathrm{LUDecomposition}\left(A\right)$

$p,l,u≔\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right],\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ -\frac{3}{2}& \frac{11}{2}& 1& 0\\ 0& 0& 0& 1\end{array}\right],\left[\begin{array}{cccc}\mathrm{-2}& 3& 1& 4\\ 0& 1& 1& \mathrm{-3}\\ 0& 0& \mathrm{-4}& \frac{45}{2}\\ 0& 0& 0& 1\end{array}\right]$

$p·l·u$

$\left[\begin{array}{cccc}0& 1& 1& \mathrm{-3}\\ \mathrm{-2}& 3& 1& 4\\ 0& 0& 0& 1\\ 3& 1& 0& 0\end{array}\right]$

$B≔⟨⟨1\,0\,2⟩\left|⟨3\,1\,4⟩\right|⟨6\,1\,4⟩|⟨1\,1\,2⟩⟩\:$

$\mathrm{LUDecomposition}\left(B\,\mathrm{method}='\mathrm{RREF}'\,\mathrm{outputoptions}\left['\mathrm{U1}'\right]=\left[\mathrm{datatype}=\mathrm{integer}\right]\right)$

$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right],\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 2& \mathrm{-2}& 1\end{array}\right],\left[\begin{array}{ccc}1& 3& 6\\ 0& 1& 1\\ 0& 0& \mathrm{-6}\end{array}\right],\left[\begin{array}{cccc}1& 0& 0& \mathrm{-1}\\ 0& 1& 0& \frac{4}{3}\\ 0& 0& 1& -\frac{1}{3}\end{array}\right]$

$C≔\mathrm{Matrix}\left(4\,4\,\left[\left[64.+0.\mathrm{I}\,-3.-41.\mathrm{I}\,19.-8.\mathrm{I}\,-14.+19.\mathrm{I}\right]\,\left[33.+0.\mathrm{I}\,13.-1.\mathrm{I}\,-10.-5.\mathrm{I}\right]\,\left[93.+0.\mathrm{I}\,-61.-0.\mathrm{I}\right]\,\left[66.+0.\mathrm{I}\right]\right]\,\mathrm{scan}=\mathrm{triangular}\left[\mathrm{upper}\right]\,\mathrm{datatype}=\mathrm{complex}\left[8\right]\,\mathrm{shape}=\mathrm{hermitian}\right)$

$C≔\left[\begin{array}{cccc}64.+0.\mathrm{I}& \mathrm{-3.}-41.\mathrm{I}& 19.-8.\mathrm{I}& \mathrm{-14.}+19.\mathrm{I}\\ \mathrm{-3.}+41.\mathrm{I}& 33.+0.\mathrm{I}& 13.-\mathrm{I}& \mathrm{-10.}-5.\mathrm{I}\\ 19.+8.\mathrm{I}& 13.+\mathrm{I}& 93.+0.\mathrm{I}& \mathrm{-61.}-0.\mathrm{I}\\ \mathrm{-14.}-19.\mathrm{I}& \mathrm{-10.}+5.\mathrm{I}& \mathrm{-61.}+0.\mathrm{I}& 66.+0.\mathrm{I}\end{array}\right]$

$\mathrm{LUDecomposition}\left(C\,\mathrm{method}='\mathrm{Cholesky}'\right)$

$\left[\begin{array}{cccc}8.+0.\mathrm{I}& 0.\mathrm{I}& 0.\mathrm{I}& 0.\mathrm{I}\\ \mathrm{-0.375000000000000}+5.12500000000000\mathrm{I}& 2.56782982302177+0.\mathrm{I}& 0.\mathrm{I}& 0.\mathrm{I}\\ 2.37500000000000+\mathrm{I}& 3.41363158937254+5.27561245630301\mathrm{I}& 6.84648870465280+0.\mathrm{I}& 0.\mathrm{I}\\ \mathrm{-1.75000000000000}-2.37500000000000\mathrm{I}& 0.590235765007373-1.89240539089993\mathrm{I}& \mathrm{-6.79180263138375}+1.96662195135924\mathrm{I}& 1.83605928416264+0.\mathrm{I}\end{array}\right]$

$\mathrm{LUDecomposition}\left(A\,\mathrm{output}='U'\right)$

$\left[\begin{array}{cccc}\mathrm{-2}& 3& 1& 4\\ 0& 1& 1& \mathrm{-3}\\ 0& 0& \mathrm{-4}& \frac{45}{2}\\ 0& 0& 0& 1\end{array}\right]$

$\mathrm{LUDecomposition}\left(B\,\mathrm{output}='R'\right)$

$\left[\begin{array}{cccc}1& 0& 0& \mathrm{-1}\\ 0& 1& 0& \frac{4}{3}\\ 0& 0& 1& -\frac{1}{3}\end{array}\right]$

$m≔\mathrm{Matrix}\left(⟨⟨1\left|0\right|1⟩\,⟨2\left|0\right|0⟩\,⟨2\left|0\right|3⟩⟩\,\mathrm{datatype}=\mathrm{float}\left[8\right]\right)$

$m≔\left[\begin{array}{ccc}1.& 0.& 1.\\ 2.& 0.& 0.\\ 2.& 0.& 3.\end{array}\right]$

$\mathrm{LUDecomposition}\left(m\,\mathrm{method}=\mathrm{SparseDirectMKL}\right)$

before P call
after P call

$''External/0x7f8685645ae0''$

The LinearAlgebra[LUDecomposition] command was updated in Maple 2023.

The domain, symmetry and definite options were introduced in Maple 2023.

For more information on Maple 2023 changes, see Updates in Maple 2023.