Parallel hybrid sparse system solvers

We present a family of hybrid algorithms that are suitable for the solution of large sparse linear systems on parallel computing platforms. This study is motivated by the lack of robustness of Krylov subspace iterative schemes with black-box preconditioners, such as incomplete LU-factorizations and the lack of scalability of direct sparse system solvers. Our hybrid solver is as robust as direct solvers and as scalable as iterative solvers whose preconditioners are both effective and scalable. Our method relies on weighted symmetric and nonsymmetric matrix reordering for bringing the largest elements on or closer to the main diagonal resulting in a very effective extracted banded preconditioner. Systems involving the extracted banded preconditioner are solved via a member of the recently developed SPIKE family of algorithms. The effectiveness of our method is demonstrated by solving large sparse linear systems that arise in various applications such as computational fluid dynamics, oil reservoir simulations, and nonlinear optimizations. Finally, we present a highly accurate method for predicting the parallel scalability of our system solver on architectures with more nodes than the platform on which our experiments have been performed.