Parareal Algorithm

Ma. Cristina Bargo

Laboratoire Jacques-Louis Lions

Université Pierre et Marie Curie
University of the Philippines Diliman

CEMRACS 2009
August 7, 2009

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 1 / 15

Outline

1 History

2 The Algorithm

3 Some Properties

4 Work Done on Parareal Algorithm

5 Simple Implementation

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 2 / 15

History

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 3 / 15

History

Lions, Maday and Turinici [4] (2001)

I parallel in real time → parareal

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 3 / 15

History

Lions, Maday and Turinici [4] (2001)

I parallel in real time → parareal
Bal and Maday [2] (2002)
I equivalent to [4] for linear problems
I better results for nonlinear problems

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 3 / 15

History

Lions, Maday and Turinici [4] (2001)

I parallel in real time → parareal
Bal and Maday [2] (2002)
I equivalent to [4] for linear problems
I better results for nonlinear problems
Baffico et al [1] (2002)
I most common formulation

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 3 / 15

The Problem

Find u such that

(
∂t u + A (t, u) = 0, t > t0
(1)
u = u0 , t = t0

where A : R × V → V 0 (V a Hilbert space) and t0 ≥ 0.

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 4 / 15

The Problem

Find u such that

(
∂t u + A (t, u) = 0, t > t0
(1)
u = u0 , t = t0

where A : R × V → V 0 (V a Hilbert space) and t0 ≥ 0.

u(t + τ ) = E(t + τ, t, v), where v = u(t) and τ > 0, with

∀µ > 0, τ > 0, E (t + τ + µ, t + τ, E(t + τ, t, v)) = E(t + τ + µ, t, v)

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 4 / 15

The Problem

Find u such that

(
∂t u + A (t, u) = 0, t > t0
(1)
u = u0 , t = t0

where A : R × V → V 0 (V a Hilbert space) and t0 ≥ 0.

u(t + τ ) = E(t + τ, t, v), where v = u(t) and τ > 0, with

∀µ > 0, τ > 0, E (t + τ + µ, t + τ, E(t + τ, t, v)) = E(t + τ + µ, t, v)

Let t0 = T0 < T1 < · · · < TN = T , and ∆Tn = Tn − Tn−1 . Then

∀n > 0, u(Tn ) = E(Tn , T0 , u0 ) = E(Tn , Tn−1 , u(Tn−1 ))

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 4 / 15

The Tools

Notations :

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 5 / 15

The Tools

Notations :
Fine solver F (t2 , t1 , u1 )

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 5 / 15

The Tools

Notations :
Fine solver F (t2 , t1 , u1 )
I approximation of the solution u(t2 ) to problem (1) with initial
condition u(t1 ) = u1
I can be a classical discretization scheme with small timestep δt

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 5 / 15

The Tools

Notations :
Fine solver F (t2 , t1 , u1 )
I approximation of the solution u(t2 ) to problem (1) with initial
condition u(t1 ) = u1
I can be a classical discretization scheme with small timestep δt
Coarse solver G(t2 , t1 , u1 )

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 5 / 15

The Tools

Notations :
Fine solver F (t2 , t1 , u1 )
I approximation of the solution u(t2 ) to problem (1) with initial
condition u(t1 ) = u1
I can be a classical discretization scheme with small timestep δt
Coarse solver G(t2 , t1 , u1 )
I another approximation to u(t2 ), less accurate than F (t2 , t1 , u1 ) but
cheaper to solve
I can be another discretization scheme with a larger timestep δT
(δT >> δt)

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 5 / 15

The Algorithm

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 6 / 15

The Algorithm

Iteration 0 :

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 6 / 15

The Algorithm

Iteration 0 :
I U00 = u0 (the initial condition in problem (1))
I U0n+1 = G(tn+1 , tn , U0n ) (the coarse solver)

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 6 / 15

The Algorithm

Iteration 0 :
I U00 = u0 (the initial condition in problem (1))
I U0n+1 = G(tn+1 , tn , U0n ) (the coarse solver)
Iteration 1, 2, · · ·

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 6 / 15

The Algorithm

Iteration 0 :
I U00 = u0 (the initial condition in problem (1))
I U0n+1 = G(tn+1 , tn , U0n ) (the coarse solver)
Iteration 1, 2, · · ·
I Parallel : F (tn+1 , tn , Ukn ) for n = 0, 1, 2, · · · , n − 1

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 6 / 15

The Algorithm

Iteration 0 :
I U00 = u0 (the initial condition in problem (1))
I U0n+1 = G(tn+1 , tn , U0n ) (the coarse solver)
Iteration 1, 2, · · ·
I Parallel : F (tn+1 , tn , Ukn ) for n = 0, 1, 2, · · · , n − 1
I Serial : Uk0 = u0 and

(2) Uk+1 k+1 k k

n+1 = G(tn+1 , tn , Un ) + F (tn+1 , tn , Un ) − G(tn+1 , tn , Un )

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 6 / 15

Some Properties

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 7 / 15

Some Properties

For k → ∞, then Ukn → Un where

Un+1 = F (tn+1 , t0 , U0 ) = F (tn+1 , tn , Un )

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 7 / 15

Some Properties

For k → ∞, then Ukn → Un where

Un+1 = F (tn+1 , t0 , U0 ) = F (tn+1 , tn , Un )

∀n = 0, 1, 2, · · · , N we can show that Unn = Un

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 7 / 15

Some Properties

For k → ∞, then Ukn → Un where

Un+1 = F (tn+1 , t0 , U0 ) = F (tn+1 , tn , Un )

∀n = 0, 1, 2, · · · , N we can show that Unn = Un

converges much faster (Maday, Rønquist and Staff, 2006 [5])

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 7 / 15

Some Properties

For k → ∞, then Ukn → Un where

Un+1 = F (tn+1 , t0 , U0 ) = F (tn+1 , tn , Un )

∀n = 0, 1, 2, · · · , N we can show that Unn = Un

converges much faster (Maday, Rønquist and Staff, 2006 [5])
stability results (Staff and Rønquist, 2005 [8])

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 7 / 15

Work Done on Parareal Algorithm

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 8 / 15

Work Done on Parareal Algorithm

pricing of an American put (Bal and Maday, 2002 [2])

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 8 / 15

Work Done on Parareal Algorithm

pricing of an American put (Bal and Maday, 2002 [2])

molecular dynamics simulations (Baffico et al, 2002 [1]) - fine scheme
uses the full model, coarse scheme is based on a simpler model of the
original

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 8 / 15

Work Done on Parareal Algorithm

pricing of an American put (Bal and Maday, 2002 [2])

molecular dynamics simulations (Baffico et al, 2002 [1]) - fine scheme
uses the full model, coarse scheme is based on a simpler model of the
original
control problems (Maday and Turinici, 2002 [6])

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 8 / 15

Work Done on Parareal Algorithm

pricing of an American put (Bal and Maday, 2002 [2])

molecular dynamics simulations (Baffico et al, 2002 [1]) - fine scheme
uses the full model, coarse scheme is based on a simpler model of the
original
control problems (Maday and Turinici, 2002 [6])
combined with domain-decomposition methods (Maday and Turinici,
2005 [7])

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 8 / 15

Work Done on Parareal Algorithm

pricing of an American put (Bal and Maday, 2002 [2])

molecular dynamics simulations (Baffico et al, 2002 [1]) - fine scheme
uses the full model, coarse scheme is based on a simpler model of the
original
control problems (Maday and Turinici, 2002 [6])
combined with domain-decomposition methods (Maday and Turinici,
2005 [7])
Navier-Stokes (Fischer, Hecht and Maday, 2005 [3]) - using fine and
coarse mesh in space

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 8 / 15

Work Done on Parareal Algorithm

pricing of an American put (Bal and Maday, 2002 [2])

molecular dynamics simulations (Baffico et al, 2002 [1]) - fine scheme
uses the full model, coarse scheme is based on a simpler model of the
original
control problems (Maday and Turinici, 2002 [6])
combined with domain-decomposition methods (Maday and Turinici,
2005 [7])
Navier-Stokes (Fischer, Hecht and Maday, 2005 [3]) - using fine and
coarse mesh in space
Goal : Use the algorithm to solve more complicated problems

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 8 / 15

Simple Implementation

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 9 / 15

Simple Implementation

 T
Sample Problem : Find u = u1 u2 so that

 ∂u = Au, t ∈ (0, 100]
∂t h iT
u = u0 = 1 0 , t=0

where A is the 2 × 2 matrix given by

 
−0.02 0.2
A=
−0.2 −0.02

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 9 / 15

Simple Implementation

t0 = 0 and T = 100
N = 100 and ∆Tn = ∆T = 1
Coarse scheme : Implicit Euler with δT = ∆T = 1
Fine scheme : Implicit Euler with δt = 0.1
Horizontal axis is u1 and the vertical axis is u2
fine scheme : 0.62 s
parareal scheme : 0.29496 s

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 10 / 15

Simple Implementation
Iteration 0

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 11 / 15

Simple Implementation
Iteration 1

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 12 / 15

Simple Implementation
Iteration 2

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 13 / 15

Simple Implementation
Iteration 3

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 14 / 15

Simple Implementation
Iteration 4

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 15 / 15

 L. Baffico, S. Bernard, Y. Maday, G. Turinici, and G. Zérah.
Parallel-in-time molecular-dynamics simulations.
Phys. Rev. E, 66(5) :057701, Nov 2002.
Guillaume Bal and Yvon Maday.
A “parareal” time discretization for nonlinear PDE’s with application to
the pricing of an american put.
In L.F. Pavarino and A. Toselli, editors, Recent Developments in
Domain Decomposition Methods, volume 23 of Lecture Notes in
Computational Science and Engineering, pages 189–202.
Springer-Verlag, Berlin, 2002.
Paul F. Fischer, Frédéric Hecht, and Yvon Maday.
A parareal in time semi-implicit approximation of the Navier-Stokes
equations.
In Domain Decomposition Methods in Science and Engineering,
volume 40 of Lecture Notes in Computational Science and Engineering,
pages 433–440. Springer, Berlin, 2005.
Jacques-Louis Lions, Yvon Maday, and Gabriel Turinici.
MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 15 / 15
 Résolution d’EDP par un schéma en temps “pararéel”.
C. R. Acad. Sci. Paris Sér. I Math., 332(7) :661–668, 2001.
Y. Maday, E.M. Rø nquist, and G.A. Staff.
The parareal-in-time algorithm : basics, stability and more.
2006.
Yvon Maday and Gabriel Turinici.
A parareal in time procedure for the control of partial differential
equations.
C. R. Math. Acad. Sci. Paris, 335(4) :387–392, 2002.
Yvon Maday and Gabriel Turinici.
The parareal in time iterative solver : a further direction to parallel
implementation.
In Domain decomposition methods in science and engineering,
volume 40 of Lecture Notes in Computational Science and Engineering,
pages 441–448. Springer, Berlin, 2005.
Gunnar Andreas Staff and Einar M. Rønquist.
Stability of the parareal algorithm.
MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 15 / 15
 In Domain Decomposition Methods in Science and Engineering,
volume 40 of Lecture Notes in Computational Science and Engineering,
pages 449–456. Springer, Berlin, 2005.

MC Bargo (UPMC + UPD) Parareal Algorithm CEMRACS 2009 15 / 15