Designing scalable numerical algorithms

Many large scientific problems are difficult not because matrix-vector products are unavailable, but because the underlying operators are too large or too dense to manipulate explicitly. A useful algorithm therefore has to ask two questions at once: what structure is present, and how little information is needed to discover it?

Adaptive randomized methods provide one answer. They use inexpensive sketches to identify useful low-rank structure and increase computational effort only where the problem demands it. This viewpoint is especially natural for hierarchical approximations and inverse problems, where accuracy and computational cost must be balanced across multiple scales.