302	RWTH Publication No: 47098        2009        IGPM302.pdf
TITLE	A Hash Data Structure for Adaptive PDE-Solvers Based on Discontinuous Galerkin Discretizations
AUTHORS	Kolja Brix, Ralf Massjung, Alexander Voß
ABSTRACT	Adaptive multiscale methods are among the most effective techniques for the numerical solution of partial differential equations. Efficient grid management is an important task in these solvers. In this paper we focus on this problem for Discontinuous Galerkin discretization methods in 2 and 3 spatial dimensions and present a data structure for handling adaptive grids of different cell types in a unified approach. Instead of tree-based techniques where connectivity is stored via pointers, we associate each cell that arises in the refinement hierarchy with a cell identifier, and construct algorithms that establish hierarchical and spatial connectivity. By means of bitwise operations, the complexity of the connectivity algorithms can be bounded independent of the level. The grid is represented by a hash table which results in a low-memory data structure and ensures fast access to cell data. The spatial connectivity algorithm also supports the application of quadrature rules for face integrals that occur in Discontinuous Galerkin discretizations. The concept allows to implement Discontinuous Galerkin methods largely independent of spatial dimension and cell type. We demonstrate this by outlining how typical algorithmic tasks that arise in these implementations can be performed with our data structure.
KEYWORDS	discontinuous Galerkin method, adaptive method, multilevel method, pointerless data structures, neighboring algorithm.
DOI	10.1137/090767418
PUBLICATION	Refinement and Connectivity Algorithms for Adaptive Discontinuous Galerkin Methods. SIAM Journal on Scientific Computing, Volume 33, Issue 1, pp. 66-101, 2011.