Full threaded tree algorithms for adaptive refinement fluid dynamics simulations. (English) Zbl 0934.76057

Summary: We describe a fully threaded tree (FTT) algorithm for adaptive mesh refinement of regular meshes. By using a tree threaded at all levels, we avoid traversals for finding nearest neighbors. All operations on a tree including tree modifications are \({\mathcal O}(N)\), where \(N\) is a number of cells, and can be performed in parallel. An implementation of the tree requires \(2N\) words of memory. In this paper, FTT algorithm is applied to the integration of the Euler equations of fluid dynamics. The integration on a tree can utilize flux evaluation algorithms used for grids, but requires a different time-stepping strategy to be computationally efficient. We present an adaptive-mesh time-stepping algorithm in which different time steps are used at different levels of the tree. Time stepping and mesh refinement are interleaved to avoid extensive buffer layers of fine mesh, which were otherwise required ahead of moving shocks. Finally, we describe a filtering algorithm for removing high-frequency noise during mesh refinement, and discuss some test examples. \(\copyright\) Academic Press.


76M20 Finite difference methods applied to problems in fluid mechanics
76N15 Gas dynamics (general theory)
65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
Full Text: DOI arXiv


[1] Berger, M. J.; Oliger, J., Adaptive mesh refinement for hyperbolic partial differential equations, J. Comput. Phys., 53, 484 (1984) · Zbl 0536.65071
[2] Berger, M. J.; Colella, P., Local adaptive mesh refinement for shock hydrodynamics, J. Comput. Phys., 82, 64 (1989) · Zbl 0665.76070
[3] Berger, M. J.; LeVeque, R. J., An Adaptive Cartesian Mesh Algorithm for the Euler Equations in Arbitrary Geometries (1989)
[4] Quirk, J. J., An Adaptive Grid Algorithm for Computational Shock Hydrodynamics (1991) · Zbl 0856.65108
[5] Quirk, J. J., An alternative to unstructured grids for computing gas dynamic flows around arbitrary complex two-dimensional bodies, Comput. & Fluids, 23, 125 (1994) · Zbl 0788.76067
[6] Quirk, J. J.; Karni, S., On the dynamics of a shock-bubble interaction, J. Fluid Mech., 318, 129 (1996) · Zbl 0877.76046
[7] Pembert, R. B.; Bell, J. B.; Colella, P.; Crutchfield, W. Y.; Welcome, M. L., An Adaptive Cartesian Grid Method for Unsteady Compressible Flow in Complex Geometries (1993)
[8] Bell, J.; Berger, M. J.; Saltzman, J.; Welcome, M., Three-dimensional adaptive mesh refinement for hyperbolic conservation laws, SIAM J. Sci. Comput., 15, 127 (1994) · Zbl 0793.65072
[9] Ruffert, M., Collisions between a white dwarf and a main-sequence star, Astronom. & AstroPhys., 265, 82 (1992)
[10] Ruffert, M.; Arnett, W. D., Three-dimensional hydrodynamic Bondi-Hoyle accretion, Astrophys. J., 427, 351 (1994)
[11] Klein, R. I.; McKee, C. F.; Colella, P., On the hydrodynamic interaction of shock waves with interstellar clouds, Astrophys. J., 420, 213 (1994)
[12] Duncan, G. G.; Hughes, P. A., Simulations of relativistic extragalactic jets, Astrophys. J. Lett., 436, L119 (1994)
[13] Young, D. P.; Melvin, R. G.; Bieterman, M. B.; Johnson, F. T.; Samant, S. S.; Bussoletti, J. E., A locally refined rectangular grid finite element method: Application to computational fluid dynamics and computational physics, J. Comput. Phys., 92, 1 (1991) · Zbl 0709.76078
[14] Zeeuw, D. D.; Powell, K. G., An adaptively refined cartesian mesh solver for the Euler equations, J. Comput. Phys., 104, 56 (1993) · Zbl 0766.76066
[15] Edwards, M. G.; Oden, J. T.; Demkowicz, L., An \(hr\), SIAM J. Sci. Comput., 14, 185 (1993)
[16] Coirier, W. J., An Adaptively-Refined, Cartesian, Cell-Based Scheme for the Euler and Navier-Stokes Equations (1994)
[17] Coirier, W. J.; Powell, K. G., An accuracy assessment of cartesian-mesh approaches for the Euler equations, J. Comput. Phys., 117, 121 (1995) · Zbl 0817.76055
[19] Aftosmis, M. J.; Melton, J. E.; Berger, M. J., Adaptation and Surface Modeling for Cartesian Mesh Methods (1995)
[20] Melton, J. E.; Berger, M. J.; Aftosmis, M. J.; Wong, M. D., 3D Applications of a Cartesian Grid Euler Method (1995)
[21] Chiang, Yu-L.; van Leer, B.; Powell, K. G., Simulation of Unsteady Inviscid Flow on an Adaptively Refined Cartesian Grid (1992)
[22] Bayyuk, S. A.; Powell, K. G.; van Leer, B., A Simulation Technique for 2-D Unsteady Inviscid Flows around Arbitrary Moving and Deforming Bodies of Arbitrary Geometry (1993)
[24] Dale, N.; Walker, H. M., Abstract Data Types: Specifications, Implementations, and Applications (1996)
[25] Kravtsov, A. V.; Klypin, A. A.; Khokhlov, A. M., Adaptive refinement tree—A new high-resolution N-Body code for cosmological simulations, Ap. J. Suppl., 111, 73 (1997)
[26] Colella, P.; Glaz, H. M., Efficient solution algorithms for the Riemann problem for real gases, J. Comput. Phys., 59, 264 (1985) · Zbl 0581.76079
[27] van Leer, B., Towards the ultimate conservative difference scheme. V. A second-order sequel to Godunov’s method, J. Comput. Phys., 32, 101 (1979) · Zbl 1364.65223
[28] Colella, P.; Woodward, P. R., The piecewise parabolic method (PPM) for gas-dynamical simulations, J. Comput. Phys., 54, 174 (1984) · Zbl 0531.76082
[29] Korobeinikov, V. P., Zadachi Teorii Tochechnogo Vzryiva, 78 (1985)
[30] Haas, J.-F.; Sturtevant, B., Interaction of weak shock waves with cylindrical and spherical gas inhomogeneities, J. Fluid Mech., 181, 41 (1987)
[31] Picone, J. M.; Boris, J. P., Vorticity generation by shock propagation through bubbles in a gas, J. Fluid Mech., 188, 23 (1988)
[32] Woodward, P. R.; Colella, P., The numerical simulation of two-dimensional fluid flow with strong shocks, J. Comput. Phys., 54, 115 (1984) · Zbl 0573.76057
[33] Porter, D. H.; Woodward, P. R.; Yang, W.; Mei, Q., Simulation and visualization of compressible convection in two and three dimensions, Nonlinear Astrophysical Fluid Dynamics, 234 (1990) · Zbl 0825.76749
[34] Oran, E. S.; Boris, J. P., Computing turbulent shear flows—A convenient conspiracy, Comput. in Phys., 7, 523 (1993)
[35] Oran, E. S.; Boris, J. P., Numerical Simulations of Reactive Flows (1987) · Zbl 0466.76098
[36] Khokhlov, A. M.; Oran, E. S., Interaction of a shock with sinusoidally perturbed flame, Combust. & Flame (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.