Every algorithm since Topic 6 has assumed is small enough to factor, reduce, or diagonalise directly. This note opens the unit's final topic by building the object every large-scale iterative method is based on: the Krylov subspace, generated by nothing more than repeated matrix-vector multiplication — the one operation that stays cheap (, not or ) no matter how large is, provided is sparse. The Arnoldi iteration builds an orthonormal basis for this subspace incrementally, reusing Gram-Schmidt one final time.
Learning objectives. By the end of this note you should be able to:
- define the Krylov subspace and explain why it grows using only matrix-vector products;
- state the Arnoldi iteration and identify it as Gram-Schmidt applied to a specific, evolving vector sequence;
- explain the resulting Hessenberg structure and its relation to Topic 9's reduction;
- explain why Krylov methods are the natural choice for sparse, large-scale problems.
In this lesson
- The Krylov subspace
- The Arnoldi iteration
Before you start
The full lesson, with worked examples and exercise solutions, is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or browse the Linear Algebra, Optimisation and Numerical Methods syllabus.