Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Convergent iterative schemes for time parallelization

Authors: Izaskun Garrido, Barry Lee, Gunnar E. Fladmark and Magne S. Espedal
Journal: Math. Comp. 75 (2006), 1403-1428
MSC (2000): Primary 65N55, 65Y05; Secondary 65M55, 65M60
Published electronically: February 24, 2006
MathSciNet review: 2219035
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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
  • 3. S.Bellavia, B.Morini, A globally convergent Newton-GMRES subspace method for systems of nonlinear equations, SIAM J. Sci. Comput., 23, No. 3, SIAM, 2001, pp. 940-960. MR 1860971 (2002h:65077)
  • 4. P. N. Brown, Y. Saad, Hybrid Krylov Methods for nonlinear systems of equations, SIAM J. Sci. Stat. Comput., 11, No. 3, SIAM, 1990, pp. 450-481. MR 1047206 (91e:65069)
  • 5. G. E. Fladmark, Secondary Oil Migration. Mathematical and numerical modelling in SOM simulator, In Norsk Hydro (eds.), Research centre Bergen, R-077857, 1997.
  • 6. M.J. Gander, H. Zhao, Overlapping Schwarz Waveform Relaxation for the Heat Equation in n-Dimensions, BIT, 42, 2002, pp. 779-795. MR 1944537 (2003m:65170)
  • 7. I. Garrido, E. Øian, M. Chaib, G. Fladmark, M. Espedal, Implicit treatment of compositional flow, Comput. Geosci., 8, No. 3, Kluwer, 2004, pp. 1-19. MR 2057524
  • 8. J. L.Lions, Y.Maday, GabrielTurinici, Rèsolution d'EDP par un schéma en temps pararéel, C. R. Acad. Sci. Paris, 332, No. 1, pp. 1-6, 2001. MR 1842465 (2002c:65140)
  • 9. 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.
  • 10. G. Qin, H. Wang, R. E. Ewing and M. S. Espedal, Numerical simulation of compositional fluid flow in porous media, Z.-C. Shi Z. Chen, R. E. Ewing (eds.), Numerical treatement of multiphase flows in porous media, 552, pp. 232-243. Springer-Verlag, Berlin, 2000.MR 1876022
  • 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.
  • 12. S. Schaffer, A semicoarsening multigrid method for elliptic partial differential equations with highly discontinuous and anisotropic coefficients SIAM J. Sci. Comput, 20, No. 1, pp. 228-242, 1998. MR 1639126 (99d:65355)
  • 13. U. Trottenberg, C.W.Oosterlee and A.Schuller, Multigrid, Academic Press, 2001. MR 1807961 (2002b:65002)
  • 14. S. Vandewalle, and G.Horton, A space-time multigrid method for parabolic partial differential equations, SIAM J. Sci. Comput, 16, No. 4, pp. 848-864, 1995.MR 1335894 (96d:65158)
  • 15. P.Wesseling, An Introduction to Multigrid Methods, John Wiley, 1992.MR 1156079 (93g:65006)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65N55, 65Y05, 65M55, 65M60

Retrieve articles in all journals with MSC (2000): 65N55, 65Y05, 65M55, 65M60

Additional Information

Izaskun Garrido
Affiliation: Department of Mathematics, University of Bergen, Johs. Brunsgt. 12, N-5008 Bergen, Norway

Barry Lee
Affiliation: CASC, Lawrence Livermore National Laboratory, Livermore, California 94551

Gunnar E. Fladmark
Affiliation: Department of Mathematics, University of Bergen, Johs. Brunsgt. 12, N-5008 Bergen, Norway

Magne S. Espedal
Affiliation: Department of Mathematics, University of Bergen, Johs. Brunsgt. 12, N-5008 Bergen, Norway

Keywords: Alternating Schwarz, time parallelization, reservoir simulator, multilevel, full approximation storage
Received by editor(s): May 29, 2003
Received by editor(s) in revised form: April 20, 2005
Published electronically: February 24, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society