Communication-avoiding Sparse Direct Methods for Solving System of Linear Equations (LU)

Abstract: Solving a system of linear equations $Ax=b$, where the co-efficient matrix $A$, is very large and sparse is at the heart of many scientific computing applications. Sparse direct methods solve such a system by first, factoring the coefficient matrix $A $ as a product $LU$ of a unit lower triangular matrix $L$ and an upper triangular matrix $U$, known as $LU$-factorization; followed by backward and forward substitution for solving two triangular systems $Ly=b$ and $Ux=y$ to get the final solution. The focus of the talk is how to improve the strong scalability of sparse direct methods on heterogeneous distributed memory systems. At large node counts, the relative cost of data transfer between the nodes can be prohibitively large and it limits the scalability of solver algorithms.

In this talk, I will present highly scalable communication-avoiding algorithms for sparse LU factorization and sparse triangular solver. The communication-avoiding "3Dimension(D)" algorithms for sparse LU factorization and triangular solve use three-dimensional partitioning of sparse matrices mapped to a three-dimensional logical arrangement of MPI processes. By redesigning the algorithms to use such a 3D partition, we show that we can reduce the asymptotic per-process communication volume for "planar" sparse matrices (e.g., from 2D grid or mesh domains) and certain non-planar sparse matrices (specifically for 3D grids and meshes). Because of reduced communication, 3D algorithms are significantly more scalable than the memory optimal 2D counterparts. The new communication-avoiding 3D sparse LU factorization code and the 3D sparse triangular achieves speedups up to 27× and up to 7.2× over the baseline 2D SuperLU_DIST library.  The new algorithms are available in the latest SuperLU_DIST version 7.2.

Speaker’s Bio: Piyush Sao is a research scientist in the Discrete Algorithms group where he works on scalable numerical and discrete algorithms for scientific computing and data analytics. He received his Ph.D. from the Georgia Institute of Technology and B.Tech. from IIT Madras in India. He leads the development effort for the Snapshot Project that was a finalist for the Gordon-Bell prize in 2020 and the R&D 100 award in 2021. He was a part of the team that placed the Summit supercomputer 3rd on the Graph500 list.