Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 37 ยท Linear Systems

Special Systems: Cholesky, Tridiagonal and Conjugate Gradient

Exploit matrix structure: Cholesky factorisation for symmetric positive definite matrices, the O(n) Thomas algorithm for tridiagonal systems and the conjugate gradient method.

General Gaussian elimination knows nothing about the matrix. But many matrices from science and engineering have structure: they are symmetric, positive definite, banded or sparse. Exploiting that structure can make a solver twice as fast, a thousand times as fast, or let it handle problems that would otherwise not fit in memory.

This final lesson of the chapter covers three structure-exploiting methods: Cholesky factorisation for symmetric positive definite (SPD) matrices, the Thomas algorithm for tridiagonal systems, and the conjugate gradient method for large SPD systems. They show up constantly in heat-flow models, splines, least squares and optimization.

Symmetric positive definite matrices

A matrix A is symmetric positive definite (SPD) if A = Aแต€ and xแต€ A x > 0 for every non-zero vector x. Equivalent tests: all eigenvalues are positive; all leading principal minors are positive. Matrices like Bแต€B (with B of full column rank), covariance matrices and stiffness matrices are SPD.

Cholesky factorisation

For an SPD matrix, elimination needs no pivoting, and the LU factors collapse into one:

A = L Lแต€ with L lower triangular and a positive diagonal.

Cost: about nยณ/3 operations, half of LU, and half the storage. The entries come from simple formulas:

l_jj = sqrt(a_jj - sum over k < j of l_jkยฒ) and l_ij = (a_ij - sum over k < j of l_ik l_jk) / l_jj for i > j.

A negative number under the square root means the matrix is not positive definite, so Cholesky doubles as a test for positive definiteness.

Python Cholesky factorisation from scratch

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.

To solve A x = b, do a forward solve with L, then a back solve with Lแต€. With SciPy: cho_factor and cho_solve, or solve(A, b, assume_a="pos").

Python Cholesky solves and random 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 last lines are a famous use of Cholesky: to draw correlated random variables with covariance ฮฃ, multiply independent standard normals by L.

Tridiagonal systems and the Thomas algorithm

A tridiagonal matrix has non-zero entries only on the main diagonal and the two neighbouring diagonals:

a_i x_(i-1) + b_i x_i + c_i x_(i+1) = d_i

These arise from second derivatives on a line, cubic splines and implicit time stepping of the heat equation. Since each row has at most three entries, elimination only ever touches one entry below the diagonal, and the Thomas algorithm solves the whole system in O(n) operations instead of O(nยณ).

It is Gaussian elimination without pivoting, specialised: a forward sweep modifies c and d, then a back substitution.

Python The Thomas algorithm

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.

One hundred thousand unknowns are solved instantly, something a dense solver could not even store (that matrix would need 80 GB). The Thomas algorithm is stable when the matrix is diagonally dominant or SPD, as in these applications. For tridiagonal systems that are not, use solve_banded, which pivots.

The conjugate gradient method

For a large sparse SPD system the conjugate gradient (CG) method is the standard iterative solver. It views A x = b as minimising the quadratic ฯ†(x) = ยฝ xแต€ A x - bแต€ x, whose gradient is A x - b = -r, the negative residual. Plain steepest descent zigzags; CG chooses successive search directions that are A-conjugate (orthogonal in the A-inner product), so each step does not spoil the progress of earlier ones.

In exact arithmetic CG finds the answer in at most n steps, but in practice it produces an excellent approximation after far fewer, and each step needs only one matrix-vector product with A.

Python Conjugate gradient from scratch

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.

This matrix has n = 2000 unknowns and CG needs about half that many iterations, because its condition number grows like nยฒ. In general the error shrinks by about (โˆšฮบ - 1) / (โˆšฮบ + 1) per step, so a large ฮบ means slow convergence, which is why practical codes use a preconditioner M โ‰ˆ A that is cheap to invert, so that Mโปยน A has a much smaller condition number.

flowchart TD
    A["Linear system A x = b"] --> B{"Structure?"}
    B -->|"small or medium, dense"| C["LU with partial pivoting"]
    B -->|"symmetric positive definite, dense"| D["Cholesky"]
    B -->|"tridiagonal or banded"| E["Thomas / solve_banded"]
    B -->|"large, sparse, SPD"| F["Conjugate gradient + preconditioner"]
    B -->|"large, sparse, general"| G["GMRES, BiCGSTAB or sparse LU"]

Choose the solver from the structure of the matrix, not from habit.

In SciPy, scipy.sparse stores sparse matrices and scipy.sparse.linalg offers spsolve (direct), cg, gmres and bicgstab (iterative). Passing assume_a="pos" to scipy.linalg.solve uses Cholesky automatically.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What factorisation does an SPD matrix have?

    Cholesky gives A = L L^T and needs about half the work of LU.
  2. 2. What does a negative value under the square root during Cholesky tell you?

    Cholesky succeeds exactly for positive definite matrices, so failure signals they are not.
  3. 3. What is the cost of the Thomas algorithm for n unknowns?

    Each row involves at most three entries, so one forward and one backward sweep suffice.
  4. 4. Why does conjugate gradient suit very large sparse SPD systems?

    CG touches the matrix only through products with vectors, which are cheap for sparse matrices.
  5. 5. What does a preconditioner do for CG?

    CG converges at a rate set by the condition number; a good preconditioner lowers it.

Summary

  • Structure matters: use Cholesky for SPD matrices (half the cost of LU, no pivoting), the Thomas algorithm for tridiagonal ones (O(n)), and conjugate gradient for large sparse SPD systems.
  • Cholesky fails if and only if the matrix is not positive definite, and generates correlated random samples.
  • CG minimises a quadratic using A-conjugate directions; its speed depends on the condition number, so precondition.
  • Match the method to the matrix: dense, banded, sparse, SPD or general.

Next: Polynomial Interpolation: Lagrange and Newton