Combinatorial Multigrid: Advanced Preconditioners For Ill-Conditioned Linear Systems

The Combinatorial Multigrid (CMG) technique is a

practical and adaptable solver and combinatorial preconditioner

for solving certain classes of large, sparse systems of linear equations.

CMG is similar to Algebraic Multigrid (AMG) but replaces

large groupings of fine-level variables with a single coarse-level

one, resulting in simple and fast interpolation schemes. These

schemes further provide control over the refinement strategies at

different levels of the solver hierarchy depending on the condition

number of the system being solved [1]. While many pre-existing

solvers may be able to solve large, sparse systems with relatively

low complexity, inversion may require O(n2) space; whereas, if

we know that a linear operator has ~n = O(n) nonzero elements,

we desire to use O(n) space in order to reduce communication

as much as possible.

Being able to invert sparse linear systems of equations, asymptotically

as fast as the values can be read from memory, has been

identified by the Defense Advanced Research Projects Agency

(DARPA) and the Department of Energy (DOE) as increasingly

necessary for scalable solvers and energy-efficient algorithms [2],

[3] in scientific computing. Further, as industry and government

agencies move towards exascale, fast solvers and communicationavoidance

will be more necessary [4], [5]. In this paper, we present

an optimized implementation of the Combinatorial Multigrid in

C using Petsc and analyze the solution of various systems using

the CMG approach as a preconditioner on much larger problems

than have been presented thus far. We compare the number of

iterations, setup times and solution times against other popular

preconditioners for such systems, including Incomplete Cholesky

and a Multigrid approach in Petsc against common problems,

further exhibiting superior performance by the CMG. 1 2

Index Terms—combinatorial algorithms, spectral support

solver, linear systems, fast solvers, preconditioners, multigrid,

graph laplacian, benchmarking, iterative solvers

For information on Reservoir’s technology related to this paper, visit Algorithms.