LANS Informal Seminar
"How to Solve a Billion-by-Billion Dense Linear System in Minutes"
DATE: March 26, 2014
TIME: 15:00:00 - 16:00:00 Description:
SPEAKER: Jie Chen, Postdoctoral Appointee, MCS Division, Argonne National Laboratory
LOCATION: Building 240, Room 1404 - 1405, Argonne National Laboratory
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.
TIME: 15:00:00 - 16:00:00
Please send questions or suggestions to Debojyoti Ghosh: ghosh at mcs dot anl dot gov.