Algorithms and Data Structures for Multi-Adaptive Time-Stepping

ABSTRACT

Multi-adaptive Galerkin methods are extensions of the standard continuous and discontinuous Galerkin methods for the numerical solution of initial value problems for ordinary or partial differential equations. In particular, the multi-adaptive methods allow individual and adaptive time steps to be used for different components or in different regions of space. We present algorithms for efficient multi-adaptive time-stepping, including the recursive construction of time slabs and adaptive time step selection. We also present data structures for efficient storage and interpolation of the multi-adaptive solution. The efficiency of the proposed algorithms and data structures is demonstrated for a series of benchmark problems.

REFERENCES

• 1: Alexander, S. G. and Agnor, C. B. 1998. n-body simulations of late stage planetary formation with a simple fragmentation model. ICARUS 132, 113--124.
• 2: Davé, R., Dubinski, J., and Hernquist, L. 1997. Parallel treeSPH. New Astronomy 2, 277--297.
• 3: Clint Dawson , Robert Kirby, High Resolution Schemes for Conservation Laws with Locally Varying Time Steps, SIAM Journal on Scientific Computing, v.22 n.6, p.2256-2281, 2000 [doi>10.1137/S1064827500367737]
• 4: Delfour, M., Hager, W., and Trochu, F. 1981. Discontinuous Galerkin methods for ordinary differential equations. Math. Comp. 36, 455--473.
• 5: Dupont, T., Hoffman, J., Johnson, C., Kirby, R. C., Larson, M. G., Logg, A., and Scott, L. R. 2003. The FEniCS project. Tech. Rep. 2003--21, Chalmers Finite Element Center Preprint Series.
• 6: C. Engstler , C. Lubich, MUR8: a multirate extension of the eighth-order Dormand-Prince method, Applied Numerical Mathematics, v.25 n.2-3, p.185-192, Nov. 1997 [doi>10.1016/S0168-9274(97)00058-5]
• 7: Eriksson, K., Estep, D., Hansbo, P., and Johnson, C. 1995. Introduction to adaptive methods for differential equations. Acta Numerica 4, 105--158.
• 8: Kenneth Eriksson , Claes Johnson, Adaptive finite element methods for parabolic problems. I.: a linear model problem, SIAM Journal on Numerical Analysis, v.28 n.1, p.43-77, Feb. 1991 [doi>10.1137/0728003]
• 9: Kenneth Eriksson , Claes Johnson, Adaptive finite element methods for parabolic problems II: optimal error estimates in L∞L2 and L∞L∞ , SIAM Journal on Numerical Analysis, v.32 n.3, p.706-740, June 1995 [doi>10.1137/0732033]
• 10: Kenneth Eriksson , Claes Johnson, Adaptive finite element methods for parabolic problems IV: nonlinear problems, SIAM Journal on Numerical Analysis, v.32 n.6, p.1729-1749, Dec. 1995 [doi>10.1137/0732078]
• 11: Kenneth Eriksson , Claes Johnson, Adaptive finite element methods for parabolic problems V: long-time integration, SIAM Journal on Numerical Analysis, v.32 n.6, p.1750-1763, Dec. 1995 [doi>10.1137/0732079]
• 12: Kenneth Eriksson , Claes Johnson , Stig Larsson, Adaptive Finite Element Methods for Parabolic Problems VI: Analytic Semigroups, SIAM Journal on Numerical Analysis, v.35 n.4, p.1315-1325, Aug. 1, 1998 [doi>10.1137/S0036142996310216]
• 13: Eriksson, K., Johnson, C., and Thomée, V. 1985. Time discretization of parabolic problems by the discontinuous Galerkin method. RAIRO MAN 19, 611--643.
• 14: Donald Estep, A posteriori error bounds and global error control for approximation of ordinary differential equations, SIAM Journal on Numerical Analysis, v.32 n.1, p.1-48, Feb. 1995 [doi>10.1137/0732001]
• 15: Estep, D. and French, D. 1994. Global error control for the continuous Galerkin finite element method for ordinary differential equations. M²AN 28, 815--852.
• 16: Estep, D., Larson, M., and Williams, R. 2000. Estimating the error of numerical solutions of systems of nonlinear reaction--diffusion equations. Memoirs of the American Mathematical Society 696, 1--109.
• 17: Estep, D. and Stuart, A. 2002. The dynamical behavior of the discontinuous Galerkin method and related difference schemes. Math. Comp. 71, 1075--1103.
• 18: Estep, D. and Williams, R. 1996. Accurate parallel integration of large sparse systems of differential equations. Math. Models. Meth. Appl. Sci. 6, 535--568.
• 19: FEniCS. 2008. The FEniCS project. www.fenics.org.
• 20: J. E. Flaherty , R. M. Loy , M. S. Shephard , B. K. Szymanski , J. D. Teresco , L. H. Ziantz, Adaptive local refinement with octree load balancing for the parallel solution of three-dimensional conservation laws, Journal of Parallel and Distributed Computing, v.47 n.2, p.139-152, Dec. 15, 1997 [doi>10.1006/jpdc.1997.1412]
• 21: Free Software Foundation. 1999. GNU LGPL. URL: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
• 22: Kjell Gustafsson , Michael Lundh , Gustaf Söderlind, A PI stepsize control for the numerical solution of ordinary differential equations, BIT, v.28 n.2, p.270-287, February 1988 [doi>10.1007/BF01934091]
• 23: Hoffman, J. and Logg, A. 2002. DOLFIN: Dynamic Object oriented Library for FINite element computation. Tech. Rep. 2002--06, Chalmers Finite Element Center Preprint Series.
• 24: Hughes, T. J. R., Levit, I., and Winget, J. 1983a. Element-by-element implicit algorithms for heat-conduction. J. Eng. Mech.-ASCE 109, 576--585.
• 25: Hughes, T. J. R., Levit, I., and Winget, J. 1983b. An element-by-element solution algorithm for problems of structural and solid mechanics. Comput. Meth. Appl. Mech. Eng. 36, 241--254.
• 26: Hulme, B. L. 1972a. Discrete Galerkin and related one-step methods for ordinary differential equations. Math. Comput. 26, 120, 881--891.
• 27: Hulme, B. L. 1972b. One-step piecewise polynomial Galerkin methods for initial value problems. Math. Comput. 26, 118, 415--426.
• 28: Jamet, P. 1978. Galerkin-type approximations which are discontinuous in time for parabolic equations in a variable domain. SIAM J. Numer. Anal. 15, 5, 912--928.
• 29: Johnson, C. 1988. Error estimates and adaptive time-step control for a class of one-step methods for stiff ordinary differential equations. SIAM J. Numer. Anal. 25, 4, 908--926.
• 30: Robert C. Kirby , Anders Logg, A compiler for variational forms, ACM Transactions on Mathematical Software (TOMS), v.32 n.3, p.417-444, September 2006 [doi>10.1145/1163641.1163644]
• 31: Robert C. Kirby , Anders Logg, Efficient compilation of a class of variational forms, ACM Transactions on Mathematical Software (TOMS), v.33 n.3, p.17-es, August 2007 [doi>10.1145/1268769.1268771]
• 32: Lew, A., Marsden, J. E., Ortiz, M., and West, M. 2003. Asynchronous variational integrators. Arch. Rational. Mech. Anal. 167, 85--146.
• 33: Anders Logg, Multi-Adaptive Galerkin Methods for ODEs I, SIAM Journal on Scientific Computing, v.24 n.6, p.1879-1902, 2002 [doi>10.1137/S1064827501389722]
• 34: Anders Logg, Multi-Adaptive Galerkin Methods for ODEs II: implementation and Applications, SIAM Journal on Scientific Computing, v.25 n.4, p.1119-1141, 2003 [doi>10.1137/S1064827501389734]
• 35: Logg, A. 2004. Automation of computational mathematical modeling. Ph.D. thesis, Chalmers University of Technology, Sweden.
• 36: Anders Logg, Multiadaptive Galerkin Methods for ODEs III: A Priori Error Estimates, SIAM Journal on Numerical Analysis, v.43 n.6, p.2624-2646, 2006 [doi>10.1137/040604133]
• 37: Logg, A. 2007. Automating the finite element method. Arch. Comput. Methods Eng. 14, 93--138.
• 38: Logg, A., Wells, G. et al. DOLFIN: A general-purpose finite element library. http://www.fenics.org/dolfin/.
• 39: Makino, J. and Aarseth, S. 1992. On a Hermite integrator with Ahmad-Cohen scheme for gravitational many-body problems. Publ. Astron. Soc. Japan 44, 141--151.
• 40: Osher, S. and Sanders, R. 1983. Numerical approximations to nonlinear conservation laws with locally varying time and space grids. Math. Comp. 41, 321--336.
• 41: Savcenco, V. 2008. Multirate numerical integration for ordinary differential equations. Ph.D. thesis, Universiteit van Amsterdam.
• 42: Savcenco, V., Hundsdorfer, W., and Verwer, J. 2005. A multirate time stepping strategy for parabolic PDEs. Tech. Rep. MAS--E0516, Centrum voor Wiskunde en Informatica (CWI).
• 43: Gustaf Söderlind, Digital filters in adaptive time-stepping, ACM Transactions on Mathematical Software (TOMS), v.29 n.1, p.1-26, March 2003 [doi>10.1145/641876.641877]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Error analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Initial value problems
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis; Efficiency

General Terms:
Algorithms, Performance

Keywords:
C++, DOLFIN, Multi-adaptivity, ODE, algorithms, continuous Galerkin, discontinuous Galerkin, implementation, individual time steps, local time steps, mcgq, mdgq, multirate