Special CMX Seminar

Large dense matrices arise naturally in numerical methods for PDEs, integral equations, and related problems in scientific computing. These matrices can be too expensive to form or store explicitly, but in many cases their off-diagonal blocks have low numerical rank. This rank structure can be exploited to design compressed representations and fast solvers.

This talk describes randomized algorithms for recovering rank-structured matrices from matrix-vector products with the matrix and its adjoint. A central theme is sample efficiency: for several hierarchical formats, the number of random samples can be made proportional to the relevant off-diagonal rank, rather than to the matrix size. The talk will discuss how randomized sketches capture low-rank structure and how this information can be organized into compressed representations, factorizations, or preconditioners. Numerical examples will illustrate the performance of these methods on matrix-free problems arising from PDEs.