Overview

Every algorithm in this unit — elimination, $QR$ factorisation, Hessenberg reduction, the QR eigenvalue algorithm — costs $O(n^2)$ to $O(n^3)$ and requires storing the full $n\times n$ matrix in memory. For $n$ in the thousands, this is routine; for $n$ in the millions (a large-scale risk system's full position-level covariance structure, or a fine finite-difference grid for a multi-asset pricing PDE), it becomes computationally prohibitive, and the matrices involved are typically sparse — mostly zero entries, with structure that dense methods cannot exploit. This closing topic builds the alternative: iterative methods that never form or factor the full matrix, working instead through repeated matrix-vector multiplication — an operation that costs only as much as the matrix has nonzero entries, however large $n$ is.