LU Decomposition Calculator

What is LU Decomposition?

LU decomposition (also known as LU factorization) is a method of decomposing a square matrix A into the product of a lower triangular matrix L and an upper triangular matrix U, such that A = LU. When partial pivoting is used, the decomposition takes the form PA = LU, where P is a permutation matrix that records row swaps.

The "L" stands for lower triangular (all entries above the main diagonal are zero), and "U" stands for upper triangular (all entries below the main diagonal are zero). The diagonal entries of L are typically set to 1 (Doolittle's method).

How Does LU Decomposition Work?

LU decomposition is essentially a systematic recording of Gaussian elimination. The algorithm proceeds column by column:

1. Select a pivot: For numerical stability, find the largest absolute value in the current column (partial pivoting) and swap rows if needed. Record the swap in P.
2. Compute multipliers: For each row below the pivot, calculate the multiplier m = A[i][k] / A[k][k]. Store these multipliers in L.
3. Eliminate: Subtract the appropriate multiple of the pivot row from each lower row. The result builds U.
4. Repeat for each column until U is fully upper triangular.

Why is LU Decomposition Useful?

LU decomposition is one of the most widely used matrix factorizations in numerical computing:

• Solving linear systems: To solve Ax = b, first decompose A = LU, then solve Ly = b (forward substitution) and Ux = y (back substitution). This is especially efficient when solving multiple systems with the same A but different b vectors.
• Computing determinants: det(A) = det(L) × det(U) = product of diagonal entries of U (accounting for row swaps).
• Matrix inversion: The inverse of A can be found by solving A × A⁻¹ = I column by column using the LU factorization.
• Numerical stability: With partial pivoting, LU decomposition is numerically stable for most practical matrices.

Computational Complexity

LU decomposition of an n×n matrix requires approximately 2n³/3 floating-point operations. Once computed, each subsequent solve (forward and back substitution) requires only 2n² operations. This makes LU decomposition far more efficient than Gaussian elimination when solving multiple systems with the same coefficient matrix.

When to Use LU Decomposition

• You have a square matrix and need to solve Ax = b for multiple right-hand sides
• You need to compute the determinant of a matrix
• You need to find the inverse of a matrix
• You're implementing numerical methods for differential equations (finite element/difference methods)

Limitations

• Only works for square matrices (for non-square, consider QR or SVD)
• The matrix must be non-singular (invertible) for a unique factorization
• Without pivoting, the algorithm can fail even for non-singular matrices