CME 510: Linear Algebra and Optimization Seminar

This seminar series highlights recent developments in numerical linear algebra and numerical optimization. The goal is to bring together scientists from different theoretical and application areas to solve complex scientific computing problems. Presenters include academic researchers and industrial R&D staff.

Dr Sherry Li, Lawrence Berkeley National Lab 

 Fast Construction of Hierarchically Low-Rank Matrices  Using Randomized Sketching

Hierarchically low-rank (H-LR) matrices have been widely used to design fast solvers for integral equations, boundary element methods, discretized PDEs, and kernel matrices in statistical and machine learning.  These matrices include H/H2-matrices, HODLR matrices, HSS matrices and butterfly matrices.  They differ in the treatment of the off-diagonal low-rank structures.  These matrices can be used in iterative solvers where stuctured-matrix-vector-product is needed, or in direct solvers where structured-factorization and stuctured-solve are needed.  The computational bottleneck in these types of solvers is often the construction algorithm, which converts a standard dense matrix into an H-LR format.  The dense matrix may not be explicitly stored.  In recent advances of this field, we have seen extensive use of randomized sketching to speed up the construction process. Regardless of which H-LR formats, the common questions include:

1) which random matrix to use?

2) what size of the random matrix to use?

3) what are the error bounds of the H-LR approximation?

4) what are the key ingredients needed for high-performance implementations?

We present a unified view to answer these questions, illustrate the algorithms on various applications, and discuss some open problems.

Speaker Bio

Dr Xiaoye S. Li is a Senior Scientist in the Applied Math and Computational Research Division, Lawrence Berkeley National Laboratory, where she leads the Scalable Solvers Group.  She has worked on diverse problems in high-performance scientific computing, including parallel algorithms, sparse-matrix computations, multi-precision arithmetic, combinatorial scientific computing, and Bayesian optimization in machine learning.  She has coauthored over 160 publications, and is the principal developer of SuperLU, a widely-used sparse direct solver.  In addition, she has contributed to the development of several other mathematical libraries, including LAPACK, Quad-Double, STRUMPACK, and XBLAS.  She is a Fellow of SIAM.