Title: Memory efficient adaptive mesh generation and implementation of multigrid algorithms using Sierpinski curves

Authors: M. Bader, S. Schraufstetter, C.A. Vigh, J. Behrens

Addresses: Institut fur Informatik, TU Munchen, Germany. ' Institut fur Informatik, TU Munchen, Germany. ' Institut fur Informatik, TU Munchen, Germany. ' Alfred Wegener Institute for Polar and Marine Research, Bremerhaven, Germany

Abstract: We will present an approach to numerical simulation on recursively structured adaptive discretisation grids. The respective grid generation process is based on recursive bisection of triangles along marked edges. The resulting refinement tree is sequentialised according to a Sierpinski space-filling curve, which leads to both minimal memory requirements and inherently cache-efficient processing schemes. The locality properties induced by the space-filling curve are even retained throughout adaptive refinement of the grid. We demonstrate the efficiency of the approach by implementing a multilevel-preconditioned conjugate gradient solver for a simple, yet adaptive, test problem: solving Poisson|s equation on a re-entrant corner problem.

Keywords: adaptive grid generation; space-filling curves; cache efficiency; simulation; memory efficiency; adaptive mesh generation; multigrid algorithms; Sierpinski curves; re-entrant corner problem.

DOI: 10.1504/IJCSE.2008.021108

International Journal of Computational Science and Engineering, 2008 Vol.4 No.1, pp.12 - 21

Published online: 04 Nov 2008 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article