Convergent iterative schemes for time parallelization

Garrido, Izaskun; Lee, Barry; Fladmark, Gunnar; Espedal, Magne

doi:10.1090/S0025-5718-06-01832-1

Convergent iterative schemes for time parallelization
HTML articles powered by AMS MathViewer

by Izaskun Garrido, Barry Lee, Gunnar E. Fladmark and Magne S. Espedal PDF

Math. Comp. 75 (2006), 1403-1428 Request permission

Abstract:

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.

References

L. Baffico, S. Bernard, Y. Maday, G. Turinici, G. Zérah, Parallel in time molecular dynamics simulations, 2002.
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
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. MR 1860971, DOI 10.1137/S1064827599363976
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. MR 1047206, DOI 10.1137/0911026
G. E. Fladmark, Secondary Oil Migration. Mathematical and numerical modelling in SOM simulator, In Norsk Hydro (eds.), Research centre Bergen, R-077857, 1997.
Martin J. Gander and Hongkai Zhao, Overlapping Schwarz waveform relaxation for the heat equation in $n$ dimensions, BIT 42 (2002), no. 4, 779–795. MR 1944537, DOI 10.1023/A:1021900403785
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. MR 2057524, DOI 10.1023/B:COMG.0000024426.15902.d8
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). MR 1842465, DOI 10.1016/S0764-4442(00)01793-6
G. Å. Øye, H. Reme, Parallelization of a Compositional Simulator with a Galerkin Coarse/Fine Method, P. Amestoy and others (eds.), 1685, pp. 586–594. Euro-Par’99, Springer-Verlag, Berlin, 1999.
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. MR 1876022, DOI 10.1007/3-540-45467-5_{2}0
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.
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. MR 1639126, DOI 10.1137/S1064827595281587
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. MR 1807961
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. MR 1335894, DOI 10.1137/0916050
Pieter Wesseling, An introduction to multigrid methods, Pure and Applied Mathematics (New York), John Wiley & Sons, Ltd., Chichester, 1992. MR 1156079