Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 37 Ā· Linear Systems

LU Decomposition and Pivoting

Factor a matrix as PA = LU, reuse the factors to solve many right-hand sides cheaply, compute determinants and inverses, and compare with scipy.linalg.lu_factor.

Gaussian elimination solves one system A x = b. But often you must solve with the same matrix and many different right-hand sides: a structure under different loads, an implicit time-stepping scheme with a new b every step. Repeating the whole elimination each time wastes effort, since the expensive O(n³) work depends only on A.

LU decomposition records the elimination as a matrix product. You factor A once (O(n³)) and then solve each new b in just O(n²). It is the heart of nearly every dense linear solver, including the ones inside NumPy and SciPy.

The factorisation

The multipliers used in elimination fit into a unit lower triangular matrix L (ones on the diagonal), and the result of elimination is the upper triangular matrix U. Then

A = L U

With row swaps from partial pivoting recorded in a permutation matrix P, the factorisation becomes

P A = L U

To solve A x = b, apply the permutation to b and solve two triangular systems:

  1. Forward substitution: solve L y = P b for y.
  2. Back substitution: solve U x = y for x.
flowchart LR
    A["A"] -->|"factor once, O(n^3)"| B["P A = L U"]
    B --> C["b"]
    C -->|"y = forward solve of L y = P b"| D["y"]
    D -->|"x = back solve of U x = y, O(n^2)"| E["x"]

Factor once, then every new right-hand side costs only two triangular solves.

Implementation

Python LU factorisation with partial pivoting

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The factors are stored compactly in a single array: the strictly lower part holds the multipliers L, the upper part holds U. Rows perm of A equal L @ U.

Solving with the factors

Python Factor once, solve many times

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All 20 systems share one O(n³) factorisation; each extra solve adds only O(n²) work.

Determinants, inverses and what they cost

The factors answer several questions almost for free:

  • Determinant: det(A) = ± product of the diagonal of U, with the sign (-1)^s for s row swaps.
  • Inverse: solve A X = I column by column. This is rarely needed: if you only want A⁻¹ b, solve instead.
  • Linear solve with many b: as above.
Python Determinant from U and SciPy's LU

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note that SciPy's lu returns A = P L U, where P is the transpose of the P in P A = L U. Be careful when comparing conventions between books and libraries.

Pivoting strategies and failure of plain LU

Without pivoting, an LU factorisation exists only if every leading principal submatrix is non-singular, and even then it can be numerically unstable. Partial pivoting always works for a non-singular matrix. For extra safety, complete pivoting searches the whole remaining submatrix (rows and columns) for the largest entry: it is more stable in theory but costlier, and partial pivoting is stable enough in virtually all practical cases.

A related idea is scaled partial pivoting, which compares each candidate to the largest entry in its row. It helps when rows have very different magnitudes (for example one equation measured in millimetres and another in kilometres).

Variant Searches Use
No pivoting nothing only for special matrices (diagonally dominant, SPD)
Partial pivoting rows of the current column the default everywhere
Scaled partial rows, scaled by row size badly scaled equations
Complete pivoting rows and columns rare; rank-revealing needs
Python Row scaling and pivoting

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions give the right answer here because the solver pivots; but a naive "largest absolute entry" rule picks different pivots after scaling, which is what scaled pivoting protects against.

In SciPy, use lu_factor and lu_solve when you will solve repeatedly with the same matrix, and solve when you will solve once. Pass assume_a="pos" or "sym" to solve if you know the matrix is symmetric positive definite or symmetric, to use a faster specialised factorisation.

Check your understanding

Quick check Ā· 5 questions

of 5 answered You scored / 5 Ā· perfect!

  1. 1. What does the factorisation P A = L U give you?

    After factoring (O(n^3)), each right-hand side costs only forward and back substitution (O(n^2)).
  2. 2. What is stored in the strictly lower part of the packed LU array?

    Each multiplier a_ik / a_kk becomes an entry of L below the diagonal.
  3. 3. How do you get det(A) from the LU factors?

    L has ones on its diagonal, so only U matters; each row interchange flips the sign.
  4. 4. When would you prefer lu_factor + lu_solve over solve?

    The factorisation can be reused across right-hand sides.
  5. 5. Which is the standard pivoting strategy in practice?

    Partial pivoting is stable enough for virtually all applications and is cheap.

Summary

  • P A = L U records elimination: L holds multipliers, U the triangular result, P the row swaps.
  • Factor once in O(n³), then solve each right-hand side in O(n²).
  • The determinant is the product of U's diagonal with a sign for swaps; avoid forming inverses.
  • Always use partial pivoting; scaled or complete pivoting are for special situations.
  • SciPy: lu, lu_factor, lu_solve; NumPy's solve uses LAPACK's LU internally.

Next: Matrix Norms and Condition Numbers