A Fast Geometric Multigrid Method for Volumetric Meshes

Abstract

Linear systems are ubiquitous in the field of numerical simulation, and can be used to describe or approximate physical processes on arbitrary objects. These objects can be represented using volumetric meshes, often made out of tetrahedra. If the mesh contains many vertices, the corresponding linear system becomes too large to solve using conventional methods. Multigrid methods are a scalable alternative to iteratively approximate solutions for such large problems, but before they can be employed, a multigrid hierarchy that corresponds to the mesh must first be defined. A bad hierarchy can lead to bad convergence when solving the problem, but creating a more accurate hierarchy can be computationally expensive itself. We present an adaptation of Gravo MG, an algorithm to define such hierarchies for triangular meshes. This adaptation translates the same design principles for the hierarchy construction from the triangular to the tetrahedral case. Furthermore, we address some new challenges that arise when dealing with volumetric meshes, particularly the preservation of the boundary when coarsening the mesh.