We present ShyLU, a new hybrid direct-iterative preconditioner and solver for general sparse linear systems. We use a Schur complement approach where subproblems are solved using a direct solver while the Schur complement is solved iteratively. We employ a block decomposition, which is formed in a fully automatic way using state-of-the-art partitioning and ordering algorithms in the Zoltan and Scotch software packages. We discuss the choice of partitioning strategy, and in particular, narrow vs. wide separators, and study the impact on the Schur complement system.
ShyLU was developed in Trilinos and will become a Trilinos package. We have two main goals: First, we wish ShyLU to be a fast and robust solver/preconditioner for multicore compute nodes. Second, due to its modular design, ShyLU can serve as an research platform to compare algorithms. For example, ShyLU supports two different approaches to forming a sparse preconditioner for the Schur complement: dropping and probing.
We show results that demonstrate the robustness and effectiveness of ShyLU for problems from a variety of applications. We have found it is particularly effective on circuit simulation problems where many iterative methods fail.
We also show results from a hybrid MPI + threads version of ShyLU. We observe that on multicore systems with many cores per node, it is advantageous to use MPI even within a single compute node.
Finally, we describe how ShyLU in future work can be used as a subdomain solver within a domain decomposition framework. This will help overcome scalability issues in our Schur complement approach for very large problems.