Krylov Subspace Methods

Solving a linear system $Ax = b$ directly means inverting matrix $A$, which for a matrix with millions of rows (a risk model's covariance matrix, say) is computationally out of reach. Krylov subspace methods sidestep this entirely: instead of touching $A$'s individual entries, they only ever need to compute $A$ times a vector, repeated a modest number of times, and build an increasingly good approximate answer from the small set of vectors that operation produces.

The trick is that the vectors $b, Ab, A^2b, A^3b, \ldots$ (the "Krylov subspace") tend to already contain most of the directions needed to approximate the true solution, especially for the well-behaved matrices common in practice. Methods like conjugate gradient and GMRES search for the best possible answer within that small subspace rather than solving the full system, and the subspace grows by one dimension per matrix-vector multiply — so accuracy improves steadily using operations that are cheap even at huge scale, especially when $A$ is sparse (mostly zeros).

A worked example

A risk model's covariance matrix might have a million assets, making a direct inverse (roughly $10^{18}$ operations) impossible. A Krylov method like conjugate gradient instead performs a matrix-vector multiply — often costing only as many operations as there are nonzero entries, perhaps a few million, if the matrix is sparse — and typically converges to a usably accurate answer within a few dozen to a few hundred such multiplies, cutting total cost by many orders of magnitude versus a direct solve.