CoreSource checked

LU Decomposition

Factors a matrix into lower and upper triangular matrices.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Numerical Methods
Difficulty: Intermediate
Family: Linear Algebra
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 5
Code example: Not ready
Visualization: Ready

Overview

LU Decomposition rewrites a matrix as a product that makes repeated linear solves faster.

Core Concepts

numeric approximationmatrix operationlinear algebraconvergence checkerror control

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n^3)

Average

O(n^3)

Worst

O(n^3)

Space

O(n^2)

When to Use

Use LU Decomposition when you need to factor a matrix.
Use it for solving many systems with one matrix with inputs like square matrix.
Use it when an approximate numeric result is acceptable and the input assumptions are satisfied.
Use it when the Linear Algebra tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when rounding error, ill-conditioning, or convergence failure would hide the real answer.
Avoid it when O(n^3) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not lower triangular matrix.

What It Does

Factors a matrix
Supports efficient repeated solves

Use Cases

Solving many systems with one matrix
Matrix inversion support
Numerical linear algebra

Inputs

Square matrix

Outputs

Lower triangular matrix
Upper triangular matrix
Optional pivot information

Key Formulas (1)

Matrix factorization

A = L · U

A = L * U

Factors a matrix into lower and upper triangular matrices.

Pseudocode

1.Start with a square matrix
2.Choose pivots as needed
3.Store elimination multipliers in the lower matrix
4.Store remaining row values in the upper matrix
5.Use the factors for forward and back substitution

Canonical Example

Input: equation = x^2 - 9 = 0 or matrix system Ax = b
Output: approximate numeric solution
Explanation: LU Decomposition: The method iteratively or algebraically approximates the requested mathematical result.

Implementation Notes

Keep the input contract explicit: Square matrix.
Use this step as the implementation spine: Start with a square matrix.
Then preserve the next state change: Choose pivots as needed.
Prefer trusted numeric libraries for matrix operations once the concept is validated.
Use small examples with known answers to verify the numeric update before scaling up.

Common Pitfalls

LU Decomposition is closely related to Gaussian Elimination.
Ignoring singular or ill-conditioned inputs can produce unstable numeric results.
Stopping based only on iteration count instead of checking residual, tolerance, or error.
Returning lower triangular matrix without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show one matrix separating into lower and upper triangular parts.

Step 1 of 5: Start with a square matrix

matrix-factorization

Notes

LU Decomposition operates in O(n^3) time and O(n^2) space within the Linear Algebra family. Key governing relation: A = L * U. Often compared with Gaussian Elimination and Linear Regression.