Positive definite and banded systems

Reading: Golub & Van Loan §4.1–4.3, pp. 154–186.

By the end of this week you should be able to

• Test for and exploit diagonal dominance and symmetry.
• Derive the Cholesky factorization and explain why it needs no pivoting.
• Store and solve a banded system in O(n) work per bandwidth.

Algorithms introduced

• Cholesky factorization A = LL^T
• Banded LU and banded Cholesky

Where this shows up in AI

Covariance and kernel matrices are symmetric positive definite. Cholesky is the workhorse of Gaussian process regression and of sampling from a multivariate normal.

Materials