chapter  4
34 Pages

A Scalable Hybrid Linear Solver Based on Combinatorial Algorithms

Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.4 Computational Results in PDE-Constrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

The availability of large-scale computing platforms comprising of tens of thousands of multicore processors motivates the need for the next generation of highly scalable sparse linear system solvers. These solvers must optimize parallel performance, processor (serial) performance, as well as memory requirements, while being robust across broad classes of applications and systems. In this chapter, we present a hybrid parallel solver that combines the desirable characteristics of direct methods (robustness) and effective iterative solvers (low computational cost), while alleviating their drawbacks (memory requirements, lack of robustness). The hybrid solver is based on the general sparse direct solver PARDISO [1], and a class of Spike factorization [2, 3, 4, 5, 6, 7, 8, 9, 10, 11] solvers. The resulting algorithm, called PSPIKE, is as robust as direct solvers, more reliable than classical preconditioned Krylov-subspace methods, and much more scalable than direct sparse solvers. We discuss several combinatorial problems that arise in the design of this hybrid solver, present algorithms to solve these combinatorial problems, and demonstrate their impact on a large-scale three-dimensional PDE-constrained optimization problem.