Frank Hulsemann : September 20, 2005

Pushing geometric multigrid to its limits.

Abstract

When they are applicable, geometric multigrid methods belong to the fastest known methods for solving linear systems arising from the discretisation of partial differential equations.

In this work we set out to determine the order of magnitude for problems on unstructured grids that can be solved on supercomputers today. To that end, we start from a method with optimal algorithmic complexity (geometric multigrid) and then identify and optimize the implementation of the most relevant components.

The combination of algorithmic and run-time efficiency results in a code that can claim to give the fastest solution of the largest linear systems encountered so far.

After a brief description of key multigrid concepts, the emphasis turns to run-time performance issues and subsequent optimization of the implementation.