Parallel hybrid sparse linear system solvers with applications

We consider the challenge of solving large scale sparse linear systems arising from different applications in science, engineering, and big data analysis, with the goal of achieving robust and parallel scalable linear system solvers on modern distributed memory parallel architectures. We first present the PSPIKE+ family of parallel hybrid linear system solvers, which relies on the proposed G-PAVER reordering scheme to construct effective preconditioners consisting of a set of overlapping diagonal blocks. Our experiments demonstrate that preconditioners of this form are both robust and parallel scalable on distributed memory platforms. We then describe PSPIKE++, which employs a two-level preconditioning scheme for further enhanced robustness as compared to that of PSPIKE+. As an application of solving large sparse linear systems in parallel, we consider the undirected s-t min-cut problem, which itself has found many applications in large scale data analysis. We present a parallel iteratively reweighted least squares min-cut algorithm (PIRMCut), which reduces the s-t min-cut problem to solving a sequence of Laplacian systems all with the same fixed nonzero structure. On both distributed and shared memory architectures, our parallel implementation of PIRMCut demonstrate significant speed improvement over a state-of-the-art serial combinatorial s-t max-flow/min-cut solver