In this paper, we investigate the coupling between operator splitting techniques and a time parallelization scheme, the parareal algorithm, as a numerical strategy for the simulation of reaction-diffusion equations modelling multi-scale reaction waves. This type of problems induces peculiar difficulties and potentially large stiffness which stem from the broad spectrum of temporal scales in the nonlinear chemical source term as well as from the presence of large spatial gradients in the reactive fronts, spatially very localized. In a series of previous studies, the numerical analysis of the operator splitting as well as the parareal algorithm has been conducted and such approaches have shown a great potential in the framework of reaction-diffusion and convection-diffusion-reaction systems. However, complementary studies are needed for a more complete characterization of such techniques for these stiff configurations. Therefore, we conduct in this work a precise numerical analysis that considers the combination of time operator splitting and the parareal algorithm in the context of stiff reaction fronts. The impact of the stiffness featured by these fronts on the convergence of the method is thus quantified, and allows to conclude on an optimal strategy for the resolution of such problems. We finally perform some numerical simulations in the field of nonlinear chemical dynamics that validate the theoretical estimates and examine the performance of such strategies in the context of academical one-dimensional test cases as well as multi-dimensional configurations simulated on parallel architecture.
@article{M2AN_2011__45_5_825_0,
author = {Duarte, Max and Massot, Marc and Descombes, St\'ephane},
title = {Parareal operator splitting techniques for multi-scale reaction waves: Numerical analysis and strategies},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
volume = {45},
year = {2011},
pages = {825-852},
doi = {10.1051/m2an/2010104},
mrnumber = {2817546},
zbl = {1269.65089},
language = {en},
url = {http://dml.mathdoc.fr/item/M2AN_2011__45_5_825_0}
}
Duarte, Max; Massot, Marc; Descombes, Stéphane. Parareal operator splitting techniques for multi-scale reaction waves: Numerical analysis and strategies. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 45 (2011) pp. 825-852. doi : 10.1051/m2an/2010104. http://gdmltest.u-ga.fr/item/M2AN_2011__45_5_825_0/
[1] , Fourth order Chebyshev methods with recurrence relation. J. Sci. Comput. 23 (2002) 2041-2054. | MR 1923724 | Zbl 1009.65048
[2] , and , Implicit-explicit multistep finite element methods for nonlinear parabolic problems. Math. Comp. 67 (1998) 457-477. | MR 1458216 | Zbl 0896.65066
[3] , , , and , Parallel-in-time molecular-dynamics simulations. Phys. Rev. E 66 (2002) 1-4.
[4] , On the convergence and the stability of the parareal algorithm to solve partial differential equations, in Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng. 40, Springer, Berlin (2003) 426-432. | MR 2235769 | Zbl 1066.65091
[5] and , A “parareal” time discretization for non-linear PDE's with application to the pricing of an American put, in Recent Developments in Domain Decomposition Methods, Lect. Notes Comput. Sci. Eng. 23, Springer, Berlin (2003) 189-202. | MR 1962689 | Zbl 1022.65096
[6] , A model for fast computer simulation of waves in excitable media. Physica D 49 (1991) 61-70.
[7] and , A parallel shooting technique for solving dissipative ODEs. Computing 51 (1993) 209-236. | MR 1253404 | Zbl 0788.65079
[8] , Analyse et Simulation Numérique de Phénomènes liés à la Combustion Supersonique. Ph.D. thesis, École Nationale des Ponts et Chaussées, France (1994).
[9] and , Comparison and analysis of some numerical schemes for stiff complex chemistry problems. RAIRO Modél. Math. Anal. Numér. 29 (1995) 259-301. | Numdam | MR 1342709 | Zbl 0829.76062
[10] and , Numerical simulation of laminar reacting flows with complex chemistry. Combust. Theory Modelling 4 (2000) 535-556. | Zbl 0970.76065
[11] , Convergence of a splitting method of high order for reaction-diffusion systems. Math. Comp. 70 (2001) 1481-1501. | MR 1836914 | Zbl 0981.65107
[12] and , Numerical simulation of a stroke: Computational problems and methodology. Prog. Biophys. Mol. Biol. 97 (2008) 40-53.
[13] and , Operator splitting for nonlinear reaction-diffusion systems with an entropic structure: Singular perturbation and order reduction. Numer. Math. 97 (2004) 667-698. | MR 2127928 | Zbl 1060.65105
[14] and , Strang's formula for holomorphic semi-groups. J. Math. Pures Appl. 81 (2002) 93-114. | MR 1994884 | Zbl 1030.35095
[15] , and , Operator splitting for stiff nonlinear reaction-diffusion systems: Order reduction and application to spiral waves, in Patterns and waves (Saint Petersburg, 2002), AkademPrint, St. Petersburg (2003) 386-482. | MR 2014215
[16] , , and , On the local and global errors of splitting approximations of reaction-diffusion equations with high spatial gradients. Int. J. Computer Mathematics 84 (2007) 749-765. | MR 2335366 | Zbl 1122.65061
[17] , , , , and , Operator splitting techniques for multi-scale reacting waves and application to low mach number flames with complex chemistry: Theoretical and numerical aspects. In preparation (2011).
[18] , A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with application to multiple shooting. Numer. Math. 22 (1974) 289-315. | MR 351093 | Zbl 0313.65070
[19] , Newton Methods for Nonlinear Problems - Affine invariance and adaptive algorithms. Springer-Verlag (2004). | MR 2063044 | Zbl 1226.65043
[20] , and , Fast simulations of waves in three-dimensional excitable media. Int. J. Bif. Chaos 7 (1997) 2529-2545. | MR 1626957 | Zbl 0899.92002
[21] , , , , , and , New resolution strategy for multi-scale reaction waves using time operator splitting, space adaptive multiresolution and dedicated high order implicit/explicit time integrators. J. Sci. Comput. (to appear) available on HAL (http://hal.archives-ouvertes.fr/hal-00457731). | MR 2890259 | Zbl 1243.65107
[22] , , , , and , Simulation of human ischemic stroke in realistic 3D geometry: A numerical strategy. Bull. Math. Biol. (to appear) available on HAL (http://hal.archives-ouvertes.fr/hal-00546223). | MR 3016905 | Zbl pre06243544
[23] , Multiscale methods in turbulent combustion: Strategies and computational challenges. Computational Science & Discovery 2 (2009) 013001.
[24] and , An Introduction to Nonlinear Chemical Dynamics - Oscillations, Waves, Patterns and Chaos. Oxford University Press (1998). | Zbl 1146.92332
[25] and , Time-decomposed parallel time-integrators: Theory and feasibility studies for fluid, structure, and fluid-structure applications. Int. J. Numer. Methods Eng. 58 (2003) 1397-1434. | MR 2012613 | Zbl 1032.74701
[26] , and , A parareal in time semi-implicit approximation of the Navier-Stokes equations, in Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng. 40, Springer, Berlin (2003) 433-440. | MR 2235770 | Zbl pre02143574
[27] and , Nonlinear convergence analysis for the parareal algorithm, in Domain Decomposition Methods in Science and Engineering XVII, Springer, Berlin (2008) 45-56. | MR 2427859 | Zbl 1140.65336
[28] and , Analysis of the parareal time-parallel time-integration method. J. Sci. Comput. 29 (2007) 556-578. | MR 2306258 | Zbl 1141.65064
[29] , and , A convergence algorithm for time parallelization applied to reservoir simulation, in Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng. 40, Springer, Berlin (2003) 469-476. | MR 2235774 | Zbl 1228.76107
[30] , , and , Convergent iterative schemes for time parallelization. Math. Comput. 75 (2006) 1403-1428. | MR 2219035 | Zbl 1089.76038
[31] , Multicomponent flow modeling. Birkhäuser Boston Inc., Boston, MA (1999). | MR 1713516 | Zbl 0956.76003
[32] , Significance of vapor phase chemical reactions on cvd rates predicted by chemically frozen and local thermochemical equilibrium boundary layer theories. J. Electrochem. Soc. 135 (1988) 1562-1570.
[33] and , Chemical oscillations and instabilites. Oxford University Press (1994).
[34] , , , , , and , A numerical study of the blocking of migraine by Rolando sulcus. Prog. Biophys. Mol. Biol. 97 (2008) 54-59.
[35] and , Solving ordinary differential equations II - Stiff and differential-algebraic problems. Second edition, Springer-Verlag, Berlin (1996). | MR 1439506 | Zbl 0729.65051
[36] , and , Geometric Numerical Integration - Structure-Preserving Algorithms for Odinary Differential Equations. Second edition, Springer-Verlag, Berlin (2006). | MR 2221614 | Zbl 1094.65125
[37] and , Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations. Springer-Verlag, Berlin (2003). | MR 2002152 | Zbl 1030.65100
[38] , and , Chemical vortex dynamics in the Belousov-Zhabotinsky reaction and in the two-variable Oregonator model. J. Phys. Chem. 93 (1989) 740-749.
[39] and , Computation accuracy and efficiency of the time-splitting method in solving atmosperic transport-chemistry equations. Atmos. Environ. 31 (1997) 2215-2224.
[40] , and , A semi-implicit numerical scheme for reacting flow. II. Stiff, operator-split formulation. J. Comput. Phys. 154 (1999) 467-482. | MR 1712580 | Zbl 0958.76061
[41] , and , Étude de l'équation de la diffusion avec croissance de la quantité de matière et son application a un problème biologique. Bulletin de l'Université d'état Moscou, Série Internationale Section A Mathématiques et Mécanique 1 (1937) 1-25. | Zbl 0018.32106
[42] , and , Résolution d'EDP par un schéma en temps “pararéel”. C. R. Acad. Sci. Paris Sér. I Math. 332 (2001) 661-668. | MR 1842465 | Zbl 0984.65085
[43] , On splitting methods for Schrödinger-Poisson and cubic nonlinear Schrödinger equations. Math. Comp. 77 (2008) 2141-2153. | MR 2429878 | Zbl 1198.65186
[44] and , A parareal in time procedure for the control of partial differential equations. C. R., Math. 335 (2002) 387-391. | MR 1931522 | Zbl 1006.65071
[45] and , The parareal in time iterative solver: A further direction to parallel implementation, in Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng. 40, Springer, Berlin (2003) 441-448. | MR 2235771 | Zbl 1067.65102
[46] , Splitting and alternating direction methods, in Handbook of numerical analysis I, North-Holland, Amsterdam (1990) 197-462. | MR 1039325 | Zbl 0875.65049
[47] , Singular perturbation analysis for the reduction of complex chemistry in gaseous mixtures using the entropic structure. Discrete Contin. Dyn. Syst. Ser. B 2 (2002) 433-456. | MR 1898324 | Zbl 1001.80006
[48] , and , Numerical solution of the atmospheric diffusion equation for chemically reacting flows. J. Comput. Phys. 45 (1982) 1-42. | MR 650424 | Zbl 0502.76098
[49] and , Modeling Low Mach number reacting flow with detailed chemistry and transport. J. Sci. Comput. 25 (2005) 263-287. | MR 2231951 | Zbl 1203.80025
[50] , and , A semi-implicit numerical scheme for reacting flow. I. Stiff chemistry. J. Comput. Phys. 143 (1998) 381-402. | MR 1631172 | Zbl 0936.76064
[51] , Toward non commutative numerical analysis: High order integration in time. J. Sci. Comput. 17 (2002) 107-125. | MR 1910554 | Zbl 0999.65095
[52] , and , IRKC: An IMEX solver for stiff diffusion-reaction PDEs. J. Comput. Appl. Math. 196 (2006) 485-497. | MR 2249440 | Zbl 1100.65075
[53] , Error estimate for the modified Newton method with applications to the solution of nonlinear, two-point boundary value problems. J. Optim. Theory Appl. 39 (1983) 489-511. | MR 703817 | Zbl 0487.65045
[54] , and , RKC: An explicit solver for parabolic PDEs. J. Comput. Appl. Math. 88 (1998) 315-326. | MR 1613246 | Zbl 0910.65067
[55] , Contribution à la modélisation des écoulements réactifs : Réduction des modèles de cinétique chimique et simulation de la pollution atmosphérique. Ph.D. thesis, École Polytechnique, France (1999).
[56] , An analysis of operator splitting techniques in the stiff case. J. Comput. Phys. 161 (2000) 140-168. | MR 1762076 | Zbl 0953.65062
[57] and , Reduction of chemical kinetics in air pollution modeling. J. Comput. Phys. 164 (2000) 354-376. | MR 1792516 | Zbl 0961.92038
[58] and , Stability of the parareal algorithm, in Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng. 40, Springer, Berlin (2003) 449-456. | MR 2235772 | Zbl 1066.65079
[59] , Accurate partial difference methods. I. Linear Cauchy problems. Arch. Ration. Mech. Anal. 12 (1963) 392-402. | MR 146970 | Zbl 0113.32303
[60] , On the construction and comparison of difference schemes. SIAM J. Numer. Anal. 5 (1968) 506-517. | MR 235754 | Zbl 0184.38503
[61] , A pseudo non-time splitting method in air quality modeling. J. Comp. Phys. 127 (1996) 152-157. | Zbl 0859.65133
[62] , Sur l'approximation de la solution des équations de Navier-Stokes par la méthode des pas fractionnaires. I. Arch. Rational Mech. Anal. 32 (1969) 135-153. | MR 237973 | Zbl 0195.46001
[63] , Sur l'approximation de la solution des équations de Navier-Stokes par la méthode des pas fractionnaires. II. Arch. Rational Mech. Anal. 33 (1969) 377-385. | MR 244654 | Zbl 0207.16904
[64] and , An implicit-explicit Runge-Kutta-Chebyshev scheme for diffusion-reaction equations. SIAM J. Sci. Comput. 25 (2004) 1824-1835. | MR 2088938 | Zbl 1061.65090
[65] and , Note on operator splitting in a stiff linear case. Rep. MAS-R9830 (1998).
[66] , and , RKC time-stepping for advection-diffusion-reaction problems. J. Comput. Phys. 201 (2004) 61-79. | MR 2098853 | Zbl 1059.65085
[67] , and , Traveling wave solutions of parabolic systems. American Mathematical Society, Providence, RI (1994). | MR 1297766 | Zbl 1001.35060
[68] , The method of fractional steps. The solution of problems of mathematical physics in several variables. Springer-Verlag, New York (1971). | MR 307493 | Zbl 0209.47103