Anna Yesypenko
The University of Texas at Austin
Title
Fast Randomized Solvers for Complex Physical Systems
Abstract
The efficient solution of large linear systems is a fundamental challenge in numerous scientific and engineering applications, particularly in solving challenging partial differential equations (PDEs) that arise in uncertainty quantification, optimal control, and inverse problems. Traditional approaches struggle to scale due to memory and computational bottlenecks. A key challenge lies in developing algorithms that leverage underlying structure to achieve competitive complexity in both storage and computation.
In this talk, I will present our recent work in hierarchical matrix representations that bridge numerical approximation, randomized sampling, and practical computing. A hierarchical matrix can be represented using O(N) bits and using our method, its structure can be recovered through a constant number of matrix-vector products. Moreover, this representation is a composition of sparse triangular factors, each of which is easily invertible. This decomposition enables approximate direct solvers that achieve O(N) complexity for solving dense linear systems -- leading to significant reductions in both storage requirements and computational cost compared to classical methods. This factorization can also be used as a generic preconditioner for discretized PDEs that is robust to ill-conditioning and indefiniteness.
Our results build upon and extend foundational work in numerical PDEs, integral equations, fast multipole methods, and hierarchical matrices, while incorporating novel randomized numerical linear algebra techniques. The proposed framework offers scalable and efficient solutions for challenging and large-scale problems in scientific computing, with broad applicability across various disciplines. I will discuss the theoretical foundations, computational implications, and future research directions of randomized sampling for structured systems.
