Nonlinear Convergence Analysis for the Parareal Algorithm
Martin Gander and Ernst Hairer
Abstract.
Time domain decomposition methods have a long history: already
Nievergelt (1964) made the following visionary statement:
``For the last 20 years, one has tried to speed up numerical
computation mainly by providing ever faster computers. Today, as it
appears that one is getting closer to the maximal speed of
electronic components, emphasis is put on allowing operations to be
performed in parallel. In the near future, much of numerical
analysis will have to be recast in a more ``parallel" form.''
Nievergelt proposed a parallel algorithm based on a decomposition of
the time direction for the solution of ordinary differential
equations. While his idea targeted large scale parallelism,
Miranker (1967) proposed a little later a family of naturally
parallel Runge Kutta methods for small scale parallelism:
``It appears at first sight that the sequential nature of the
numerical methods do not permit a parallel computation on all of the
processors to be performed. We say that the front of
computation is too narrow to take advantage of more than one
processor... Let us consider how we might widen the computation
front.''
Waveform relaxation methods, introduced by Lelarasmee (1982)
for the large scale simulation of VLSI design, are another fundamental
way to introduce time parallelism into the solution of evolution
problems. For an up to date historical review and further references,
see Gander (2005).
The present research was motivated by the introduction of the parareal
algorithm by Lions (2001). We show in this paper a general
superlinear convergence result for the parareal algorithm applied to a
nonlinear system of ordinary differential equations.
Key Words.
Ordinary differential equations, parareal algorithm, parallelism.