 LinearAlgebra - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Solvers : LinearAlgebra/LUDecomposition

LinearAlgebra

 LUDecomposition
 compute the Cholesky, PLU or PLU1R decomposition of a Matrix

 Calling Sequence LUDecomposition(A, m, out, c, ip, options, outopts)

Parameters

 A - Matrix m - (optional) equation of the form method = name where name is one of 'GaussianElimination', 'RREF', 'FractionFree', 'Cholesky', or 'none'; method used to factorize A out - (optional) equation of the form output = obj where obj is one of 'P', 'L', 'U', 'U1', 'R', 'NAG', 'determinant', or 'rank', or a list consisting of one or more of these names; selects result objects to compute c - (optional) equation of the form conjugate=true or false; specifies whether to use the Hermitian transpose in the case of Cholesky decomposition ip - (optional) equation of the form inplace=true or false; specifies if output overwrites input when U or NAG is in the output list options - (optional); constructor options for the result object(s) outopts - (optional) equation(s) of the form outputoptions[o] = list where o is one of 'P', 'L', 'U', 'U1', 'R', or 'NAG'; constructor options for the specified result object

Description

 • 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, 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  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.
 • 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.

 P permutation Matrix L lower triangular factor U upper triangular factor U1 square upper triangular factor R reduced row echelon form NAG compact (NAG-style) form

 • The inplace and constructor options are mutually exclusive.
 • 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](..).

Examples

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\right):$
 > $A≔⟨⟨0,-2,0,3⟩|⟨1,3,0,1⟩|⟨1,1,0,0⟩|⟨-3,4,1,0⟩⟩$
 ${A}{≔}\left[\begin{array}{cccc}{0}& {1}& {1}& {-3}\\ {-2}& {3}& {1}& {4}\\ {0}& {0}& {0}& {1}\\ {3}& {1}& {0}& {0}\end{array}\right]$ (1)
 > $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}{-2}& {3}& {1}& {4}\\ {0}& {1}& {1}& {-3}\\ {0}& {0}& {-4}& \frac{{45}}{{2}}\\ {0}& {0}& {0}& {1}\end{array}\right]$ (2)
 > $p·l·u$
 $\left[\begin{array}{cccc}{0}& {1}& {1}& {-3}\\ {-2}& {3}& {1}& {4}\\ {0}& {0}& {0}& {1}\\ {3}& {1}& {0}& {0}\end{array}\right]$ (3)
 > $B≔⟨⟨1,0,2⟩|⟨3,1,4⟩|⟨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}& {-2}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {3}& {6}\\ {0}& {1}& {1}\\ {0}& {0}& {-6}\end{array}\right]{,}\left[\begin{array}{cccc}{1}& {0}& {0}& {-1}\\ {0}& {1}& {0}& \frac{{4}}{{3}}\\ {0}& {0}& {1}& {-}\frac{{1}}{{3}}\end{array}\right]$ (4)
 > $C≔\mathrm{Matrix}\left(4,4,\left[\left[64.+0.I,-3.-41.I,19.-8.I,-14.+19.I\right],\left[33.+0.I,13.-1.I,-10.-5.I\right],\left[93.+0.I,-61.-0.I\right],\left[66.+0.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.}{}{I}& {-3.}{-}{41.}{}{I}& {19.}{-}{8.}{}{I}& {-14.}{+}{19.}{}{I}\\ {-3.}{+}{41.}{}{I}& {33.}{+}{0.}{}{I}& {13.}{-}{I}& {-10.}{-}{5.}{}{I}\\ {19.}{+}{8.}{}{I}& {13.}{+}{I}& {93.}{+}{0.}{}{I}& {-61.}{+}{-0.}{}{I}\\ {-14.}{-}{19.}{}{I}& {-10.}{+}{5.}{}{I}& {-61.}{+}{0.}{}{I}& {66.}{+}{0.}{}{I}\end{array}\right]$ (5)
 > $\mathrm{LUDecomposition}\left(C,\mathrm{method}='\mathrm{Cholesky}'\right)$
 $\left[\begin{array}{cccc}{8.}{+}{0.}{}{I}& {0.}{}{I}& {0.}{}{I}& {0.}{}{I}\\ {-0.375000000000000}{+}{5.12500000000000}{}{I}& {2.56782982302177}{+}{0.}{}{I}& {0.}{}{I}& {0.}{}{I}\\ {2.37500000000000}{+}{I}& {3.41363158937254}{+}{5.27561245630301}{}{I}& {6.84648870465280}{+}{0.}{}{I}& {0.}{}{I}\\ {-1.75000000000000}{-}{2.37500000000000}{}{I}& {0.590235765007373}{-}{1.89240539089993}{}{I}& {-6.79180263138375}{+}{1.96662195135924}{}{I}& {1.83605928416264}{+}{0.}{}{I}\end{array}\right]$ (6)

To reduce a Matrix using Gaussian elimination, specify the 'U' object:

 > $\mathrm{LUDecomposition}\left(A,\mathrm{output}='U'\right)$
 $\left[\begin{array}{cccc}{-2}& {3}& {1}& {4}\\ {0}& {1}& {1}& {-3}\\ {0}& {0}& {-4}& \frac{{45}}{{2}}\\ {0}& {0}& {0}& {1}\end{array}\right]$ (7)

To reduce a Matrix using Gauss-Jordan elimination, specify the 'R' object:

 > $\mathrm{LUDecomposition}\left(B,\mathrm{output}='R'\right)$
 $\left[\begin{array}{cccc}{1}& {0}& {0}& {-1}\\ {0}& {1}& {0}& \frac{{4}}{{3}}\\ {0}& {0}& {1}& {-}\frac{{1}}{{3}}\end{array}\right]$ (8)