A study of combinatorial issues in a sparse hybrid solver

ABSTRACT. The solution of large sparse linear systems is an important kernel in scientific computing. Hybrid direct-iterative methods provide a compromise between the robustness of direct solvers and the lower memory requirements of iterative solvers. We show that combinatorial algorithms such as partition-ing, ordering, and coloring play an important role in hybrid solvers. We identify combinatorial issues and study the effects of partitioning in a new hybrid solver, ShyLU