Peano—A Traversal and Storage Scheme for Octree-Like Adaptive Cartesian Multiscale Grids

Tobias Weinzierl, Miriam Mehl

Research output: Contribution to journalArticlepeer-review

50 Scopus citations


Almost all approaches to solving partial differential equations (PDEs) are based upon a spatial discretization of the computational domain-a grid. This paper presents an algorithm to generate, store, and traverse a hierarchy of d-dimensional Cartesian grids represented by a (k = 3)- spacetree, a generalization of the well-known octree concept, and it also shows the correctness of the approach. These grids may change their adaptive structure throughout the traversal. The algorithm uses 2d + 4 stacks as data structures for both cells and vertices, and the storage requirements for the pure grid reduce to one bit per vertex for both the complete grid connectivity structure and the multilevel grid relations. Since the traversal algorithm uses only stacks, the algorithm's cache hit rate is continually higher than 99.9 percent, and the runtime per vertex remains almost constant; i.e., it does not depend on the overall number of vertices or the adaptivity pattern. We use the algorithmic approach as the fundamental concept for a mesh management for d-dimensional PDEs and for a matrix-free PDE solver represented by a compact discrete 3 d-point operator. In the latter case, one can implement a Jacobi smoother, a Krylov solver, or a geometric multigrid scheme within the presented traversal scheme which inherits the low memory requirements and the good memory access characteristics directly. © 2011 Society for Industrial and Applied Mathematics.
Original languageEnglish (US)
Pages (from-to)2732-2760
Number of pages29
JournalSIAM Journal on Scientific Computing
Issue number5
StatePublished - Jan 2011
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): UK-c0020
Acknowledgements: This work was supported by the InternationalGraduate School of Science and Engineering (IGSSE) and the Institute for Advanced Study (IAS)of the Technische Universitat Munchen. Furthermore, this publication is partially based on worksupported by Award No. UK-c0020, made by the King Abdullah University of Science and Technology(KAUST).
This publication acknowledges KAUST support, but has no KAUST affiliated authors.


Dive into the research topics of 'Peano—A Traversal and Storage Scheme for Octree-Like Adaptive Cartesian Multiscale Grids'. Together they form a unique fingerprint.

Cite this