Ldu DecompositionEdit
LDU decomposition is a factorization of a square matrix that expresses A as the product A = L D U, where L is a lower triangular matrix with ones on its diagonal, D is a diagonal matrix, and U is an upper triangular matrix with ones on its diagonal. This arrangement mirrors the familiar LU decomposition but isolates the scale information in D, providing a clean separation between the triangular structure and the pivot magnitudes. In practice, LDU can be viewed as a refined lens on solving linear systems, computing determinants, and constructing inverses, especially in contexts where keeping a diagonal pivot structure explicit is advantageous for stability and interpretation.
Like its cousins in matrix factorization, LDU sits alongside LU decomposition and LDL^T decomposition as a foundational tool in numerical linear algebra. It is particularly useful when one wants to track the effect of pivots separately from the triangular factors, or when dealing with algorithms that benefit from a diagonal containing the scaling factors. For many problems, LDU can be obtained from LU factorization with additional bookkeeping to separate the diagonal of the upper factor into D, yielding a pair of triangular factors whose units on the diagonal simplify certain backward/forward substitution steps. See LU decomposition for a broader context on how these factorizations relate and how pivoting can be used to ensure numerical robustness.
Definition and basic properties
In the LDU form, A = L D U, where
- L is strictly lower triangular with ones on its diagonal (a unit lower triangular matrix),
- D is diagonal,
- U is strictly upper triangular with ones on its diagonal (a unit upper triangular matrix).
The factorization separates scale from shape: the diagonals of D carry the pivot magnitudes, while L and U carry the triangular structure with unit diagonals.
Uniqueness: When L is constrained to have a unit diagonal and U also to have a unit diagonal, D is uniquely determined (assuming the factorization exists for the given A, or after appropriate row/column permutations are applied).
Existence and permutation: Not every matrix A admits an LDU factorization without row/column rearrangement. In general, one may need permutation matrices P (on the left) and Q (on the right) to obtain P A Q = L D U. A standard condition for the existence of such a factorization without zero pivots is that certain leading principal minors of the permuted matrix are nonzero. See permutation matrix and pivoting for how these reorderings are implemented in practice.
Relation to other decompositions:
- If you have an A that admits an LU decomposition with L and U (not necessarily with unit diagonals), you can often rearrange factors to express A as L D U in a way that mirrors the pivoting strategy, providing a bridge to LU decomposition.
- If A is symmetric and positive definite, you may favor an LDL^T decomposition, which is a symmetric cousin of the LDU idea, often written as A = L D L^T; see LDL^T decomposition for contrast and context.
- In some contexts, the L and U factors in LDU can be interpreted as normalized triangular bases, with D acting as a diagonal scaling between them.
Existence, pivoting, and computation
Pivoting and zero pivots: In practice, zero or near-zero pivots can prevent a straightforward LDU factorization. Pivoting strategies—such as partial pivoting (reordering rows) or complete pivoting (reordering rows and columns)—are standard remedies that allow the factorization to proceed and improve numerical stability. See Partial pivoting and Pivoting for the general ideas.
Direct Crout-/Doolittle-style approaches: Classical algorithms for obtaining LDU use Crout-like or Doolittle-like recurrences adapted to a middle diagonal D. In a Crout-style approach, you build L with unit diagonals and incorporate the pivot information into D and U. In a Doolittle-style approach, you build U with unit diagonals and similarly place pivot information into L and D. The method chosen often depends on the desired storage pattern and the conditioning of the matrix. See Crout's method and Doolittle's method for the standard variants.
A practical workflow: one common practical route is to compute an LU decomposition with pivoting, then extract D as the diagonal of the pivoted upper (or lower) factor and adjust the corresponding triangular factors to carry the unit-diagonal structure. In high-performance libraries such as LAPACK, the underlying routines focus on LU factorizations with pivoting, and the LDU form can be recovered through careful extraction and normalization steps.
Complexity: The core factoring step typically runs in O(n^3) arithmetic for an n-by-n matrix, with the exact cost depending on the pivot strategy, storage format, and sparsity pattern. See general discussions of Gaussian elimination and its cost.
Numerical considerations and practical use
Stability and robustness: Pivoting remains the standard guardrail against numerical instability in most practical implementations. Partial pivoting offers a good balance between stability and performance for a wide class of problems, while complete pivoting provides the strongest stability at extra cost. The choice influences how often a true LDU form can be realized without resorting to additional permutations.
Sparsity and structure: For sparse matrices, maintaining sparsity during factorization is often a dominant concern. Specialized sparse LU/LDU routines exploit structure to minimize fill-in, with particular attention to column and row permutations. See sparse matrix techniques and sparse LU methods for related topics.
Applications in solving systems and determinants: Once A = L D U is obtained, solving A x = b proceeds by forward substitution to solve L y = b, then diagonal scaling y by D, and finally backward substitution to solve U x = y. This yields an efficient path to x without forming A^{-1}. The determinant det(A) can be read off as det(D) times the sign of any row/column permutations used, since det(L) and det(U) are unity when L and U have unit diagonals. See solving linear systems and determinant.
Relationship to hardware and libraries: Many numerical linear algebra packages emphasize LU with pivoting as the workhorse, and LDU is often used conceptually or as a post-processing view to separate scaling factors from the triangular structure. In libraries such as LAPACK and related software, the focus is typically on robust LU factorization with pivoting, from which LDU-like interpretations can be constructed as needed.
Applications and implications
Solving linear systems: A x = b becomes a sequence of straightforward substitutions once L, D, and U are in place, enabling efficient repeated solves with the same A but different right-hand sides, a common need in simulations, optimization, and data analysis.
Determinants and condition numbers: The product of the diagonal entries of D provides a direct handle on det(A) (modulo any permutation signs), and the conditioning information carried by D reflects how pivot magnitudes influence the stability of the solution.
Inverse and sensitivity analyses: Once A is factored, one can compute A^{-1} or study how small changes in b influence x with a predictable substitution pattern, which is valuable in stability analysis and in certain optimization routines.
Comparisons with related factorizations: LDL^T and other symmetric variants offer insight when A has structure that makes symmetry or positive definiteness advantageous. See LDL^T decomposition for a closely related framework, and LU decomposition for the broader family of triangular-solver techniques.