LU Decomposition¶
A square-matrix factorization into lower- and upper-triangular factors, with permutations when needed.
Core Idea¶
LU decomposition, in this entry's strict square-matrix sense, expresses an \(n\times n\) matrix using same-shape lower-triangular \(L\) and upper-triangular \(U\) factors, with row or column permutations when needed. An unpivoted form is \(A=LU\). LAPACK's row-pivoted convention writes \(A=P_LLU\); a square sparse solver may instead use \(P_S A Q_S^T=LU\). Rectangular LAPACK routines have trapezoidal factors and are a qualified extension outside this strict triangular scope.[ref-10dd120cf4bb][ref-862311c85821]
Scope of Application¶
For a fixed nonsingular coefficient matrix, the factors support repeated \(Ax=b\) solves: transform \(b\) according to the permutation, solve the lower and upper triangular systems, and undo any variable permutation. LAPACK separates factorization from solves with multiple right-hand sides. Sparse solvers add fill-reducing ordering and symbolic analysis, while preserving the lower/upper product idea. If \(A\) changes, its numeric factors generally need recomputation.[ref-19b5ea624c12][ref-3d429d354482]
Clarity¶
LU is the recorded product, not merely Gaussian elimination's transient row operations. Pivoting may be needed even for nonsingular \(A\): the matrix \(\begin{bmatrix}0&2\\1&3\end{bmatrix}\) has a zero first pivot in its given order, but swapping rows yields an upper-triangular matrix. A singular matrix may still have LU factors with a zero diagonal of \(U\); that does not provide a unique solution or inverse.[^ref-10dd120cf4bb]
Manages Complexity¶
Factoring once makes repeated right-hand sides cheaper than re-eliminating the same dense matrix. For sparse matrices, ordering can reduce fill, but numerical pivot needs may change the order and cost. The method keeps these choices separate from the central question: do the stated lower/upper factors and permutations multiply back to the original matrix?[ref-3d429d354482][ref-862311c85821]
Abstract Reasoning¶
In Li's sparse convention, check \(P_S A Q_S^T=LU\). For \(Ax=b\), solve \(Ly=P_Sb\) and \(Uz=y\), then recover \(x=Q_S^Tz\). This demonstrates why a row/column permutation is not cosmetic: using the wrong convention gives the wrong system even when both triangular solves are performed accurately.[^ref-862311c85821]
Knowledge Transfer¶
The same factor–solve split works for dense and sparse linear systems, but a dense row-only pivot record and a sparse row-and-column ordering cannot be interchanged blindly. Block LU and Crout-style normalization are narrower realizations of the lower/upper identity. The fact that a singular matrix can be factored must remain separate from the stronger claim that it can be inverted.[ref-10dd120cf4bb][ref-862311c85821]
[^ref-10dd120cf4bb]: LAPACK DGETRF documentation, directly checked.
[^ref-19b5ea624c12]: LAPACK DGETRS documentation, directly checked.
[^ref-3d429d354482]: Netlib Templates, “Direct Solvers for Sparse Matrices”, directly checked.
[^ref-862311c85821]: Xiaoye S. Li, Sparse Gaussian Elimination on High Performance Computers, University of California, Berkeley dissertation (1996), ch. 3 §3.1, directly checked.
Relationships to Other Abstractions¶
Current abstraction LU Decomposition Domain-specific
Parents (1) — more general patterns this builds on
-
LU Decomposition is a kind of Factorization Prime
Square-matrix LU expresses a matrix as a product of same-shape lower- and upper-triangular factors.
Hierarchy path (1) — routes to 1 parentless root
- LU Decomposition → Factorization → Decomposition
Neighborhood in Abstraction Space¶
LU Decomposition sits in a sparse region of the domain-specific corpus (81st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Matrix Structures & Matroids (10 abstractions)
Nearest neighbors
- QR Decomposition — 0.85
- Schur decomposition — 0.83
- Gram Matrix — 0.82
- L-Matrix — 0.81
- Zero-Divisor Graph — 0.81
Computed from structural-signature embeddings · 2026-10-08