Spacetime meshing with adaptive refinement and coarsening

ABSTRACT

We propose a new algorithm for constructing finite-element meshes suitable for spacetime discontinuous Galerkin solutions of linear hyperbolic PDEs. Given a triangular mesh of some planar domain Ω and a target time value T, our method constructs a tetrahedral mesh of the spacetime domain Ω X [0,T] in constant running time per tetrahedron in ℝ³ using an advancing front method. Elements are added to the evolving mesh in small patches by moving a vertex of the front forward in time. Spacetime discontinuous Galerkin methods allow the numerical solution within each patch to be computed as soon as the patch is created. Our algorithm employs new mechanisms for adaptively coarsening and refining the front in response to a posteriori error estimates returned by the numerical code. A change in the front induces a corresponding refinement or coarsening of future elements in the spacetime mesh. Our algorithm adapts the duration of each element to the local quality, feature size, and degree of refinement of the underlying space mesh. We directly exploit the ability of discontinuous Galerkin methods to accommodate discontinuities in the solution fields across element boundaries.

REFERENCES

• 1: A. Adler. On the bisection method for triangles. Math. Comp. 40(162):571--574, 1983.
• 2: Douglas N. Arnold , Arup Mukherjee , Luc Pouly, Locally Adapted Tetrahedral Meshes Using Bisection, SIAM Journal on Scientific Computing, v.22 n.2, p.431-448, 2000 [doi>10.1137/S1064827597323373]
• 3: E. Bänsch. Local mesh refinement in 2 and 3 dimensions. Impact of Computing in Science and Engineering 3:181--191, 1991.
• 4: M. Bern and P. Plassmann. Mesh generation. Handbook of Computational Geometry, 291--332, 2000. Elsevier Science Publishers B.V. North-Holland.
• 5: J. Bey, Tetrahedral grid refinement, Computing, v.55 n.4, p.355-378, 1995 [doi>10.1007/BF02238487]
• 6: Bernardo Cockburn , Pierre-Alain Gremaud, Error estimates for finite element methods for scalar conservation laws, SIAM Journal on Numerical Analysis, v.33 n.2, p.522-554, April 1996 [doi>10.1137/0733028]
• 7: B. Cockburn, G. Karniadakis, and C. Shu, editors. Discontinuous Galerkin Methods: Theory, Computation and Applications. Lecture Notes in Computational Science and Engineering 11, Springer-Verlag, 2000.
• 8: J. Erickson, D. Guoy, J. M. Sullivan, and A. Üngör. Building space-time meshes over arbitrary spatial domains. Proc. 11th Int. Meshing Roundtable, 391--402, 2002.
• 9: Mark T. Jones , Paul E. Plassmann, Adaptive refinement of unstructured finite-element meshes, Finite Elements in Analysis and Design, v.25 n.1-2, p.41-60, March 1997 [doi>10.1016/S0168-874X(96)00039-X ]
• 10: L. V. Kalé et al. Parallel Programming Laboratory, Computer Science Department, University of Illinois. hhttp://charm.cs.uiuc.edu/i.
• 11: L. V. Kalé and S. Krishnan. Charm++: Parallel programming with message-driven objects. Parallel Programming using C++, 175--213, 1996. MIT Press.
• 12: B. Kearfott. A proof of covergence and an error bound for the method of bisection in ℝn. Math. Comp. 32(144):1147--1153, 1978.
• 13: Anwei Liu , Barry Joe, On the shape of tetrahedra from bisection, Mathematics of Computation, v.63 n.207, p.141-154, July 1994 [doi>10.2307/2153566]
• 14: Anwei Liu , Barry Joe, Quality local refinement of tetrahedral meshes based on bisection, SIAM Journal on Scientific Computing, v.16 n.6, p.1269-1291, Nov. 1995 [doi>10.1137/0916074]
• 15: R. B. Lowrie, P. L. Roe, and B. van Leer. Space-time methods for hyperbolic conservation laws. Barriers and Challenges in Computational Fluid Dynamics, 79--98, 1998. ICASE/LaRC Interdisciplinary Series in Science and Engineering 6, Kluwer.
• 16: Joseph M. Maubach, Local bisection refinement for N-simplicial grids generated by reflection, SIAM Journal on Scientific Computing, v.16 n.1, p.210-227, Jan. 1995 [doi>10.1137/0916014]
• 17: A. Merrouche, A. Selman, and C. Knopf-Lenoir. 3D adaptive mesh refinement. Communications In Numerical Methods In Engineering 14:397--407, 1998.
• 18: William F. Mitchell , Robert Skeel, Unified multilevel adaptive finite element methods for elliptic problems, 1988
• 19: William F. Mitchell, A comparison of adaptive refinement techniques for elliptic problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.4, p.326-347, Dec. 1989 [doi>10.1145/76909.76912]
• 20: William F. Mitchell, Adaptive refinement for arbitrary finite-element spaces with hierarchical bases, Journal of Computational and Applied Mathematics, v.36 n.1, p.65-78, Aug. 20, 1991 [doi>10.1016/0377-0427(91)90226-A ]
• 21: J. Palaniappan, R. B. Haber, and R. L. Jerrard. A spacetime discontinuous galerkin method for scalar conservation laws. Comp. Methods Appl. Mechs. Engng., 2004. in press.
• 22: Gerard R. Richter, An explicit finite element method for the wave equation, Applied Numerical Mathematics, v.16 n.1-2, p.65-80, Dec. 1994 [doi>10.1016/0168-9274(94)00048-4 ]
• 23: M. C. Rivara. Algorithms for refining triangular grids suitable for adaptive and multigrid techniques. Internat. J. Numer. Methods Eng. 20:745--756, 1984.
• 24: M. C. Rivara. A grid generator based on 4-triangles conforming mesh-refinement algorithms. Internat. J. Numer. Methods Eng. 24(7):1343--1354, 1987.
• 25: María-Cecilia Rivara, Local modification of meshes for adaptive and/or multigrid finite-element methods, Journal of Computational and Applied Mathematics, v.36 n.1, p.79-89, Aug. 20, 1991 [doi>10.1016/0377-0427(91)90227-B ]
• 26: I. G. Rosenberg and F. Stenger. A lower bound on the angles of triangles constructed by bisecting the longest side. Math. Comput. 29:390--395, 1975.
• 27: E. G. Sewell. Automatic generation of triangulations for piecewise polynomial approximation. Ph. D. thesis, Department of Mathematics, Purdue University, West Lafayette, IN, 1972.
• 28: A. Sheffer, A. Üngör, S.-H. Teng, and R. B. Haber. Generation of 2D space-time meshes obeying the cone constraint. Advances in Computational Engineering & Sciences, 1360--1365, 2000. Tech Science Press.
• 29: M. Stynes. On faster convergence of the bisection method for all triangles. Math. Comp. 35(152):1195--1201, 1980.
• 30: J. P. Suárez, A. Plaza, and G. F. Carey. Propagation path properties in iterative longest-edge refinement. Proc. 12th Internat. Meshing Roundtable, 79--90, 2003. hhttp://www.andrew.cmu.edu/user/sowen/abstracts/Su983.htmli.
• 31: L. L. Thompson. Design and Analysis of Space-Time and Galerkin Least-Squares Finite Element Methods for Fluid-Structure Interaction in Exterior Domains. Ph.D. thesis, Stanford University, 1994.
• 32: A. Üngör, C. Heeren, X. Li, A. Sheffer, R. B. Haber, and S.-H. Teng. Constrained 2D space-time meshing with all tetrahedra. Proc. 16th IMACS World Congress, 2000.
• 33: A. Üngör and A. Sheffer. Pitching tents in space-time: Mesh generation for discontinuous Galerkin method. Int. J. Foundations of Computer Science 13(2):201--221, 2002.
• 34: Alper Üngör , Alla Sheffer , Robert B. Haber , Shang-Hua Teng, Layer based solutions for constrained space-time meshing, Applied Numerical Mathematics, v.46 n.3-4, p.425-443, September 2003 [doi>10.1016/S0168-9274(03)00037-0]
• 35: L. Yin. A Spacetime Discontinuous Galerkin Finite-Element Method for Elastodynamic Analysis. Ph. D. thesis, Department of Theoretical & Applied Mechanics, University of Illinois, Urbana, IL, 2002.
• 36: L. Yin, A. Acharya, N. Sobh, R. Haber, and D. A. Tortorelli. A space-time discontinuous Galerkin method for elastodynamic analysis. Discontinuous Galerkin Methods: Theory, Computation and Applications (B. Cockburn, G. Karniadakis, and C. Shu, eds.), pp. 459--464. Springer-Verlag, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Hyperbolic equations; Finite element methods

General Terms:
Algorithms, Performance

Keywords:
adaptivity, advancing front, mesh generation, spacetime discontinuous Galerkin, tetrahedral meshes, unstructured meshes