Week 8
Linear systems
Midterm
Structured and fast solvers
Reading: Golub & Van Loan §4.5, 4.7–4.8, pp. 196–233.
By the end of this week you should be able to
- Solve a block tridiagonal system by block elimination.
- Recognise Toeplitz and circulant structure and exploit it.
- Diagonalize a circulant matrix with the DFT and solve in O(n log n).
Algorithms introduced
- Block tridiagonal elimination
- Classical Toeplitz methods
- FFT-based circulant and discrete Poisson solvers
Where this shows up in AI
A convolution is a circulant matrix. The same structure that makes convolution cheap in a CNN makes these systems fast to solve.
Materials
- Slides
posted before class - Notes
posted after class - Code
to be added - Due this week
Midterm examination