NCLDUDecomposition[aMatrix, Options]

Aliases: None.

Description: NCLDUDecomposition[$X$] yields the LDU decomposition for a square matrix $X$. It returns a list of four elements, namely $L,D,U$, and $P$ such that $P X P^T = L D U$. The first element is the lower triangular matrix $L$, the second element is the diagonal matrix $D$, the third element is the upper triangular matrix $U$, and the fourth is the permutation matrix $P$ (the identity is returned if no permutation is needed). As an option, it may also return a list of the permutations used at each step of the LDU factorization as a fifth element.

Suppose X is given by $X = \{ \{ a,b,0\} ,\{ 0,c,d\} ,\{ a,0,d\} \}$. The command

$$\{lo, di, up, P\} = {\tt NCLDUDecomposition} [X]$$

returns matrices, which in MatrixForm are:

As matrix $X$ is $3\times 3$, one can provide 2 permutation matrices. Let those permutations be given by $l_1 = \{3,2,1\}$ and $l_2 = \{ 1,3,2\}$, that means:

$$\begin{array}{cc} P1 = \left( \begin{array}{ccc} 0&0&1\ 0&1... ...ray}{ccc} 1&0&0\ 0&0&1\ 0&1&0\end{array} \right) \end{array}$$

just as in NCPermutationMatrix. The command

$$\{lo,di,up,P\}= \newline {\tt NCLDUDecomposition} [X, Permutation\rightarrow\{l1,l2\}]$$

returns matrices, which in MatrixForm are:

$$\begin{array}{ll} lo = \left( \begin{array}{ccc} 1&0&0\ 0&... ...0&1\ 1&0&0\ 0&1&0\end{array}\right) = P_2\: P_1 \end{array}$$

It can be checked that $P^T\; lo\; di\; up\; P = X$:

$$MatMult[Transpose[P], lo, di, up, P] = \{ \{ a,b,0\} ,\{ 0,c,d\} ,\{ a,0,d\} \}$$

Arguments: X is a square matrix n by n. The default Options are:
{Permutation $\rightarrow$ False, CheckDecomposition $\rightarrow$ False,
NCSimplifyPivots $\rightarrow$ False, StopAutoPermutation $\rightarrow$ False,
ReturnPermutation $\rightarrow$ False, Stop2by2Pivoting $\rightarrow$ False }. If permutation matrices are to be given, they should be provided as Permutation $\rightarrow$ $\{l_1$, $l_2$, $\cdots$, $l_n\}$, where each $l_i$ is a list of integers (see the command NCPermutationMatrix[]). If CheckDecomposition is set to True, the function checks if $P X P^T$ is identical to $L D U$. Where $P=P_1 P_2 \cdots P_n$, and each $P_i$ is the permutation matrix associated with each $l_i$.

Often a prospective pivot will appear to be nonzero in Mathematica even though it reduces to zero. To ensure we are not pivoting with a convoluted form of zero, we simplify the pivot at each step. By default, NCLDUDecomposition converts the pivot from non-commutative to commutative and then simplifies the expression. If the commutative form of the pivot simplifies to zero, Mathematica scrolls down the diagonal looking for a pivot which does not simplify to zero. If all the diagonal entries simplify to zero utilizing the CommuteEverything[] command, the process is repeated using NCSimplifyRational.
This strategy is incorporated for two main reasons. One is that for large matrices it is much faster. Secondly, NCSimplifyRational does not always completely simplify complicated expressions. Setting NCSimplifyPivots $\rightarrow$ True bypasses CommuteEverything and immediately applies
NCSimplifyRational to each pivot. NCLDUDecomposition will automatically pivot if the current pivot at a particular iteration is zero. If the user utilized the Permutation option, then the permutation designated will be temporarily disregarded. However, NCLDUDecomposition will try and use the given permutation list for the next step. In this way,
NCLDUDecomposition follows the user permutation as closely as possible. If StopAutoPermutation $\rightarrow$ True, then NCLDUDecomposition will not automatically pivot and will strictly adhere to the user's permutation, attempting to divide by zero if need be. This will allow the user to determine which permutations are not possible. Because NCLDUDecomposition will automatically pivot when necessary by default, the ReturnPermutation was created so that the permutation used in the decomposition can be returned to the user for further analysis if set to True.
To explain the last option it is somewhat necessary for the user to have an idea of how the pivoting strategy works. The permutations used are always symmetrically applied. Because of this, we can only place other diagonal elements in the (1,1) position. However, it is possible to place any off diagonal element in the (2,1) position. Thus our strategy is to pivot only with diagonal elements if possible. If all the diagonal elements are zero, then a permutation matrix is used to place a nonzero entry in the (2,1) position which will automaticaly place a nonzero entry in the (1,2) position if the matrix is symmetric. Then, instead of using the (1,1) entry as a pivot, the 2$\times$2 submatrix starting in the (1,1) position is used as a block pivot. This has the effect of creating an $L D U$ decomposition where $D$ is a block diagonal matrix with 1$\times$1 and 2$\times$2 blocks along the diagonal. (Note: The pivots are precisely the diagonal entries of $D$.) Setting Stop2by2Pivoting $\rightarrow$ True will halt $2\times 2$ block pivoting, returning instead, the remaining undecomposed block with zeros along the diagonal as a final block diagonal entry.

Comments / Limitations: NCLDUDecomposition automatically assumes invertible any expressions (pivot) it needs to be invertible. Also, the $2\times 2$ pivoting strategy assumes that the matrix is symmetric in that it only ensures that the (2,1) entry is nonzero (assuming by symmetry that the (1,2) is also zero). The pivoting strategy chooses its pivots based upon the smallest leaf count invoking the Mathematica command LeafCount[]. It will choose the smallest nonzero diagonal element basing size upon the leaf count. This strategy is incorporated in an attempt to find the simplest $L D U$ factorization possible. If a $2\times 2$ pivot is used and ReturnPermutation is set to True then at the end of the permutation list returned will be the string 2by2 permutation.