Convergent iterative schemes for time parallelization. (English) Zbl 1089.76038

Garrido, Izaskun; Lee, Barry; Fladmark, Gunnar E.; Espedal, Magne S.

Math. Comput. 75, No. 255, 1403-1428 (2006).

Summary: Parallel methods are usually not applied to the time domain because of the inherit sequentialness of time evolution. But for many evolutionary problems, computer simulation can benefit substantially from time parallelization methods. In this paper, we present several such algorithms that actually exploit the sequential nature of time evolution through a predictor-corrector procedure. This sequentialness ensures convergence of a parallel predictor-corrector scheme within a fixed number of iterations. The performance of these novel algorithms, which are derived from the classical alternating Schwarz method, are illustrated through several numerical examples using the reservoir simulator Athena.

MSC:

76M12	Finite volume methods applied to problems in fluid mechanics
76M20	Finite difference methods applied to problems in fluid mechanics
76T30	Three or more component flows
76S05	Flows in porous media; filtration; seepage
65Y05	Parallel numerical computation

Keywords:

predictor-corrector procedure; convergence; Schwarz method; reservoir simulator Athena

Software:

Wesseling

References:

[1]	L.Baffico, S.Bernard, Y.Maday, G.Turinici, G.Zérah, Parallel in time molecular dynamics simulations, 2002.
[2]	G.Bal, Y.Maday, A parareal time discretization for non-linear PDE’s with application to the pricing of an American put, Lect. Notes Comput. Sci. Eng., vol. 23, Springer, Berlin, 2002. MR1962689 · Zbl 1022.65096
[3]	Stefania Bellavia and Benedetta Morini, A globally convergent Newton-GMRES subspace method for systems of nonlinear equations, SIAM J. Sci. Comput. 23 (2001), no. 3, 940 – 960. · Zbl 0998.65053 · doi:10.1137/S1064827599363976 · doi.org
[4]	Peter N. Brown and Youcef Saad, Hybrid Krylov methods for nonlinear systems of equations, SIAM J. Sci. Statist. Comput. 11 (1990), no. 3, 450 – 481. · Zbl 0708.65049 · doi:10.1137/0911026 · doi.org
[5]	G. E. Fladmark, Secondary Oil Migration. Mathematical and numerical modelling in SOM simulator, In Norsk Hydro , Research centre Bergen, R-077857, 1997.
[6]	Martin J. Gander and Hongkai Zhao, Overlapping Schwarz waveform relaxation for the heat equation in \? dimensions, BIT 42 (2002), no. 4, 779 – 795. · Zbl 1022.65112 · doi:10.1023/A:1021900403785 · doi.org
[7]	I. Garrido, E. Øian, M. Chaib, G. E. Fladmark, and M. S. Espedal, Implicit treatment of compositional flow, Comput. Geosci. 8 (2004), no. 1, 1 – 19. · Zbl 1221.76115 · doi:10.1023/B:COMG.0000024426.15902.d8 · doi.org
[8]	Jacques-Louis Lions, Yvon Maday, and Gabriel Turinici, Résolution d’EDP par un schéma en temps ”pararéel”, C. R. Acad. Sci. Paris Sér. I Math. 332 (2001), no. 7, 661 – 668 (French, with English and French summaries). · Zbl 0984.65085 · doi:10.1016/S0764-4442(00)01793-6 · doi.org
[9]	G. Å. Øye, H. Reme, Parallelization of a Compositional Simulator with a Galerkin Coarse/Fine Method, P. Amestoy and others , 1685, pp. 586-594. Euro-Par’99, Springer-Verlag, Berlin, 1999.
[10]	Guan Qin, Hong Wang, Richard E. Ewing, and Magne S. Espedal, Numerical simulation of compositional fluid flow in porous media, Numerical treatment of multiphase flows in porous media (Beijing, 1999) Lecture Notes in Phys., vol. 552, Springer, Berlin, 2000, pp. 232 – 243. · Zbl 1072.76569 · doi:10.1007/3-540-45467-5_20 · doi.org
[11]	H. Reme, G.Å. Øye, Use of local grid refinement and a Galerkin technique to study secondary migration in fractured and faulted regions, Computing and Visualisation in Science, 2, pp. 153-162, Springer-Verlag, Berlin, 1999. · Zbl 1067.74584
[12]	Steve Schaffer, A semicoarsening multigrid method for elliptic partial differential equations with highly discontinuous and anisotropic coefficients, SIAM J. Sci. Comput. 20 (1998), no. 1, 228 – 242. · Zbl 0913.65111 · doi:10.1137/S1064827595281587 · doi.org
[13]	U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, Inc., San Diego, CA, 2001. With contributions by A. Brandt, P. Oswald and K. Stüben.
[14]	G. Horton and S. Vandewalle, A space-time multigrid method for parabolic partial differential equations, SIAM J. Sci. Comput. 16 (1995), no. 4, 848 – 864. · Zbl 0828.65105 · doi:10.1137/0916050 · doi.org
[15]	Pieter Wesseling, An introduction to multigrid methods, Pure and Applied Mathematics (New York), John Wiley & Sons, Ltd., Chichester, 1992. · Zbl 0760.65092