LANS Informal Seminar: Jie Chen

Seminar Title: How to Solve a Billion-by-Billion Dense Linear System in Minutes
Speaker: Jie Chen, Postdoctoral Appointee, MCS Division, Argonne National Laboratory

Date/Time: 2014-03-26 15:00
Location: Building 240, Room 1404 – 1405

Description:
Solving linear systems of equations is a common step in many large computations in real life. The size of a system one can solve defines the scope of a computational method and affects the modeling approaches one can adopt for a particular application. State-of-the-art linear solvers can solve billion-scale sparse linear systems by using iterative methods, and they can solve million-scale dense linear systems by using direct factorization methods. In this talk, I present some recent research progress on pushing the scale limit of the size of a dense system one can possibly handle. There is no free lunch, since clearly storing an arbitrary matrix incurs a quadratic cost. We restrict our consideration to matrices with exploitable structures: multilevel Toeplitz and recursive low-rank compressibility. These structures cover an extensive array of applications in practice, including the solving of differential/integral equations, data analysis, uncertainty quantification, N-body simulations, electronic structure calculations, and many others that I have neglected to the best of my limited knowledge. Both structures enable the design of data storage and algorithms with a (near-)linear complexity. I will introduce the basic mathematics. Parallelization is the way demonstrating the practical usefulness and advantage of linear-complexity methods at scale. We show achieved parallel scalability for the multilevel Toeplitz structure by using nonblocking MPI collectives. For the recursive low-rank compressible structure, the algorithms are being implemented, and we have a good reason to expect that they scale even better than those for the multilevel Toeplitz structure because of a more economic communication pattern.