Sparse systems, conjugate gradient, and preconditioning

Reading: Golub & Van Loan §11.1–11.3, 11.5, 10.1, pp. 598–639, 650–670, 546–556.

By the end of this week you should be able to

• Work with a matrix available only as the operator x → Ax.
• Derive the conjugate gradient method and its convergence rate in terms of the condition number.
• Explain what a preconditioner does to the spectrum and why that is the whole game.

Algorithms introduced

• Jacobi, Gauss-Seidel, and SOR
• The conjugate gradient method
• Preconditioned CG; the symmetric Lanczos process

Where this shows up in AI

Hessian-free (Newton-CG) optimization never forms the Hessian, only Hessian-vector products. The same matrix-free idea underlies large-scale kernel methods and PDE-constrained learning.

Materials