Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 38 ยท Linear Algebra

LU, QR, Cholesky and Schur Decompositions

Learn the LU, QR, Cholesky and Schur matrix decompositions in scipy.linalg, how to reuse a factorization for many right-hand sides, and which one to choose.

A matrix decomposition (or factorization) writes a matrix as a product of simpler matrices, such as triangular or orthogonal ones. Simpler pieces are cheap to work with: a triangular system is solved in one sweep of substitution. This is how solve really works, and knowing the four main decompositions lets you speed up programs, check results and understand error messages.

This lesson builds on solving systems. We meet LU, QR, Cholesky and Schur, learn to reuse a factorization, and finish with a guide for choosing between them.

LU: the general-purpose workhorse

LU decomposition factors a square matrix into A = P L U: a permutation P (row swaps for numerical safety), a lower-triangular L with ones on the diagonal and an upper-triangular U. It is Gaussian elimination written as matrices, and it costs about 2/3 n^3 operations.

The expensive step is the factorization. Once you have it, each new right-hand side b costs only about 2 n^2: one forward substitution and one backward substitution. lu_factor returns the compact factorization and lu_solve reuses it.

Python LU and reusing the factorization

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 permutation matrix shows the solver reordered the rows so that the biggest entry (8) became the pivot. Without that, a tiny pivot would divide by almost nothing and ruin accuracy. When the same matrix appears with many different b vectors (time stepping, iterative refinement, solving for several loads) factor once with lu_factor and call lu_solve repeatedly.

flowchart LR
    A["A"] --> F["lu_factor<br/>expensive, once"]
    F --> X["(lu, piv)"]
    X --> S1["lu_solve b1<br/>cheap"]
    X --> S2["lu_solve b2<br/>cheap"]
    X --> S3["lu_solve b3<br/>cheap"]

Factor once, solve many right-hand sides cheaply.

QR: orthogonal and stable

QR decomposition writes A = Q R where Q has orthonormal columns (Q^T Q = I) and R is upper triangular. It works for rectangular matrices too, which makes it the standard tool for least-squares problems. Orthogonal matrices do not amplify errors, so QR is numerically very stable.

For a tall matrix with 5 rows and 3 columns, mode="economic" returns the thin Q (5 by 3) and square R (3 by 3), which is what you almost always want. The default "full" mode returns a 5 by 5 Q with extra columns.

Python QR and a least-squares solution

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.

solve_triangular(R, c) solves a triangular system by pure substitution, so it needs only n^2 operations and no pivoting. It is the building block that LU, QR and Cholesky all end in. Pass lower=True for lower-triangular matrices.

Cholesky: fast for symmetric positive-definite matrices

A symmetric matrix is positive definite if x^T A x > 0 for every non-zero vector x. Covariance matrices, the normal-equation matrices X^T X of full-rank data and many physics matrices have this property. For them, cholesky finds a lower-triangular L with A = L L^T, using half the work of LU and no pivoting.

Cholesky doubles as a test: if the matrix is not positive definite, it raises LinAlgError. And it has a famous statistical use: multiplying independent standard normal numbers by L produces correlated ones.

Python Cholesky solve and correlated samples

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 sample covariance of 20,000 generated points comes out close to the cov matrix we asked for. Like LU, Cholesky has a cho_factor/cho_solve pair for reuse.

Schur: triangular form for eigenvalue problems

The Schur decomposition writes A = Z T Z^T with an orthogonal Z and an upper-triangular T (for real matrices with only real eigenvalues; complex eigenvalues lead to small 2-by-2 blocks unless you ask for output="complex"). The eigenvalues of A sit on the diagonal of T. You rarely call Schur directly, but it is the numerically safe route to eigenvalues and to matrix functions such as expm and sqrtm, which we meet in the next lesson.

Python Schur form and its diagonal

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 sorted diagonal of T equals the eigenvalues. The last line shows triangular back substitution: with U upper triangular, the last unknown is 10 / 5 = 2, and the others follow upward.

Choosing a decomposition

Situation Use Why
General square system LU (solve, lu_factor) Fastest general method, pivoting for stability
Many right-hand sides, same matrix lu_factor or cho_factor, then solve Pay the factorization once
Symmetric positive definite Cholesky Half the cost, no pivoting, doubles as a PD test
Rectangular or least squares QR (or SVD when rank is doubtful) Stable, handles tall matrices
Eigenvalues, matrix functions Schur (inside eig, expm) Orthogonal, backward stable

All of these produce the same solution when the matrix is well conditioned; the difference is speed, memory and behavior on hard matrices. When in doubt, call solve and let SciPy pick, adding assume_a if you know the structure.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why use lu_factor and lu_solve instead of calling solve repeatedly?

    Factoring costs about 2/3 n^3 operations, while each substitution costs about 2 n^2. For many right-hand sides with the same matrix, reuse saves most of the work.
  2. 2. Which decomposition requires a symmetric positive-definite matrix?

    Cholesky factors A as L L^T and only exists for symmetric positive-definite matrices. SciPy raises LinAlgError otherwise.
  3. 3. What are the properties of Q in a QR decomposition?

    Q has orthonormal columns, which makes QR numerically stable. R is the upper-triangular factor.
  4. 4. Where are the eigenvalues of A found in the Schur decomposition A = Z T Z^T (real case, real eigenvalues)?

    T is triangular and similar to A, so its diagonal entries are the eigenvalues of A.

Summary

  • Decompositions factor a matrix into triangular or orthogonal pieces that are cheap to use.
  • LU (lu, lu_factor, lu_solve) is the general method; reuse the factorization for many right-hand sides.
  • QR is stable and the basis of least squares; use mode="economic" for tall matrices.
  • Cholesky halves the cost for symmetric positive-definite matrices and doubles as a test.
  • Schur gives triangular form with eigenvalues on the diagonal; solve_triangular finishes the job.

Next: Eigenvalues and Singular Values.