A parallel sparse solver and its relation to graphs

A solver for sparse linear systems is an important kernel in many areas of science and engineering. Typically, sparse linear systems of equations arise from the discretization of partial differential equations (PDEs), while some sparse systems are not governed by PDEs. Even in the case that the coefficient matrix is dense, applications still require an effective preconditioner, which is often sparse. For solving large problems, one needs to resort to parallel computing in order to reduce the time to solution. Sparse algorithms are well-known for their poor utilization of the cache due to irregular memory access. In addition, traditional algorithms that are designed for sequential platforms usually have inherited limitations for parallelism. Therefore, there is a need for novel algorithms to work on today's multicore clusters. Given a system of equations Ax = f, where A is large and sparse, it is known that hybrid solvers that contain both direct and iterative components are promising in terms of robustness and scalability on parallel computing platforms. In this paper, we review the generalized parallel sparse DS factorization algorithm and its relationship to sparse graphs. We will provide an example of parallel scalability of the hybrid solver compared to other well-known preconditioned Krylov subspace methods.