39
$\begingroup$

I'm currently looking into parallel methods for ODE integration. There is a lot of new and old literature out there describing a wide range of approaches, but I haven't found any recent surveys or overview articles describing the topic in general.

There's the book by Burrage [1], but it's almost 20 years old and hence does not cover many of the more modern ideas like the parareal algorithm.

[1] K. Burrage, Parallel and Sequential Methods for Ordinary Differential Equations, Clarendon Press, Oxford, 1995

$\endgroup$
35
+50
$\begingroup$

I'm not aware of any recent overview articles, but I am actively involved in the development of the PFASST algorithm so can share some thoughts.

There are three broad classes of time-parallel techniques that I am aware of:

  • across the method — independent stages of RK or extrapolation integrators can be evaluated in parallel; see also the RIDC (revisionist integral deferred correction algorithm)
  • across the problem — waveform relaxation
  • across the time-domain — Parareal; PITA (parallel in time algorithm); and PFASST (parallel full approximation scheme in space and time).

Methods that parallelize across the method usually perform very close to spec but don't scale beyond a handful of (time) processors. Typically they are relatively easier to implement than other methods and are a good if you have a few extra cores lying around and are looking for predictable and modest speedups.

Methods that parallelize across the time domain include Parareal, PITA, PFASST. These methods are all iterative and are comprised of inexpensive (but inaccurate) "coarse" propagators and expensive (but accurate) "fine" propagators. They achieve parallel efficiency by iteratively evaluating the fine propagator in parallel to improve a serial solution obtained using the coarse propagator.

The Parareal and PITA algorithms suffer from a rather unfortunate upper bound on their parallel efficiency $E$: $E < 1/K$ where $K$ is the number of iterations required to obtain convergence throughout the domain. For example, if your Parareal implementation required 10 iterations to converge and you are using 100 (time) processors, the largest speedup you could hope for would be 10x. The PFASST algorithm relaxes this upper bound by hybridizing the time-parallel iterations with the iterations of the Spectral Deferred Correction time-stepping method and incorporating Full Approximation Scheme corrections to a hierarchy of space/time discretizations.

Lots of games can be played with all of these methods to try and speed them up, and it seems as though the performance of these across-the-domain techniques depends on what problem you are solving and which techniques are available for speeding up the coarse propagator (coarsened grids, coarsened operators, coarsened physics etc.).

Some references (see also references listed in the papers):

I have written two implementations of PFASST that are available on the 'net: PyPFASST and libpfasst.

$\endgroup$
  • 1
    $\begingroup$ I am currently learning parareal. And I think it is of much help to me. $\endgroup$ – eccstartup Jun 25 '13 at 5:25
  • $\begingroup$ This is a great overview. However it should be explicitly mentioned that ODEs are often solved after a spatial discretization of PDEs. Therefore, parallelism across the method can yield great scalability to thousands of cores if your spatial domain is big enough. This is because the vast majority of compute times goes into the computation of, for instance, the RK stage RHS evaluations. $\endgroup$ – NoseKnowsAll Oct 30 '17 at 18:34
15
$\begingroup$

Although this post is now two years old, in case someone stumbles across it, let me give a brief update:

Martin Gander recently wrote a nice review article, that gives a historical perspective on the field and discusses many different PINT methods: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

There is now also a community website which lists very many references and gives descriptions of different methods: http://www.parallel-in-time.org/

A discussion of the Parareal parallel-in-time algorithm in particular can be found here: https://en.wikipedia.org/wiki/Parareal

$\endgroup$
  • 1
    $\begingroup$ A little surprised that Gander doesn't talk about the MGRIT approach by Falgout, et al., especially since it looks to be backed by nice software (XBraid), but I know the MGRIT papers have only come out recently. $\endgroup$ – Geoff Oxberry Jul 13 '15 at 6:35
  • 1
    $\begingroup$ Hi Geoff, I am quite sure Martin Gander wrote the paper before the MGRIT papers were published - while the review paper is going to appear in 2015, I think the preprint came online late 2013 already. $\endgroup$ – Daniel Jul 13 '15 at 7:10
  • 1
    $\begingroup$ At first glance it looks like "parallel across the method" is omitted in this review -- for instance, extrapolation is never mentioned. $\endgroup$ – David Ketcheson Feb 1 '16 at 8:59
4
$\begingroup$

Here is a short introduction to waveform relaxation. When talking about the time-parallel method like parareal or PITA or other methods, one should distinguish between the dissipative and the conservative (Hamiltonian) ODE systems. The latter seems more difficult to parallelize in time dimension by partitioning to time sub-intervals. Here is an analysis of parareal for Hamiltonian systems. The dissipative system is easier because the error caused at initial time $u_0$ tends to disappear due to the dissipation $u(t)=\exp(-\lambda t)u_0,$ $\mathrm{Re}\,\lambda>0.$

$\endgroup$
  • $\begingroup$ As I said, I've already found a lot of articles on the individual topics. What I'm missing is a general overview over the approaches. $\endgroup$ – Florian Brucker Jun 25 '13 at 8:10
  • 1
    $\begingroup$ FWIW, the PFASST algorithm exhibits very good convergence (to be published soon) for Hamiltonian systems even for many (hundreds) of time processors. Having said that, getting appreciable speedup depends (once again) on making the coarse propagators a lot cheaper than the fine propagator - a multipole expansion or some other multiphysics approach seems to be necessary to get good speedup for particle systems. $\endgroup$ – Matthew Emmett Jun 25 '13 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.