Why care about SPD-ness?

If $A$ is SPD, then
  1. $A$ is invertible, so the system $Ax = b$ has a unique solution for every vector $b$.
  2. Gaussian Elimination can run to completion on $A$ and no row swaps are needed!
    3. (This means that all pivots encountered are nonzero.)
  3. Gaussian elimination is stable.

We have the same conclusions we did had for SDD matrices, but in this case we get more.

Cholesky factorization

If $A$ is SPD, the we can find a lower triangular $L$ (not necessarily unit!) such that $$A=LL^T,$$ by running GE with minor modifications.

You will develop the necessary modifications in HW3.

Let's take a closer look

We can compute the entries of $L$ “directly” in order.

Last one before we go!

Tridiagonal matrices also come up often in practice and we may exploit their structure to write fast linear solvers.

An $n \times n$ matrix $T$ is tridiagonal if $a_{ij} = 0$ whenever $|i - j| > 1$.

A tridiagonal matrix can only have nonzero entries along the diagonal, the superdiagonal, and the subdiagonal.
Congratulations! You reached the end of this lecture.
Take me home