Fast Construction of Hierarchically Low-Rank Matrices Using Randomized Sketching

Sherry Xiaoye Li surveys randomized construction of hierarchically low-rank matrices, including H/H2, HODLR, HSS, and butterfly formats with different off-diagonal structures. Applications include integral equations, boundary elements, discretized PDEs, and statistical or machine-learning kernel matrices, using either iterative matrix-vector products or direct factorization and solves. Constructing these representations from an implicit dense operator is often the main cost. The talk offers a unified view of sketch distributions, sketch sizes, approximation error bounds, high-performance implementation, applications, and open questions.