NONLINEAR PARALLEL-IN-TIME SCHUR COMPLEMENT SOLVERS FOR
ORDINARY DIFFERENTIAL EQUATIONS
SANTIAGO BADIA†AND MARC OLM‡
Abs ac . In his wo k, we p opose a pa allel-in- ime sol e o linea and nonlinea o dina y di -
e en ial equa ions. The app oach is based on an e icien mul ile el sol e o he Schu complemen
ela ed o a mul ile el ime pa i ion. Fo linea p oblems, he scheme leads o a as di ec me hod.
Nex , wo di e en s a egies o sol ing nonlinea ODEs a e p oposed. Fi s , we conside a New-
on me hod o e he global nonlinea ODE, using he mul ile el Schu complemen sol e a e e y
nonlinea i e a ion. Second, we s a e he global nonlinea p oblem in e ms o he nonlinea Schu
complemen (a an a bi a y le el), and pe o m nonlinea i e a ions o e i . Nume ical expe imen s
show ha he p oposed schemes a e weakly scalable, i.e., we can e icien ly exploi inc easing com-
pu a ional esou ces o sol e o mo e ime s eps he same p oblem.
Keywo ds: Time pa allelism, o dina y di e en ial equa ions, domain decomposi ion, nonlinea sol e ,
scalabili y
Con en s
1. In oduc ion 2
2. S a emen o he p oblem 3
3. An ODE di ec sol e 3
3.1. Applica ion o di e en ime in eg a o s 5
3.2. Pa a eal in e p e a ion 6
3.3. Pa allel e iciency 7
4. I e a i e sol e s o nonlinea ODEs 8
4.1. New on-Schu complemen me hods 8
4.2. Nonlinea Schu complemen -New on me hods 9
5. Nume ical expe imen s 11
5.1. Expe imen al se -up 11
5.2. Two-le el sol e s 12
5.3. Mul ile el sol e 13
6. Conclusions 15
Re e ences 15
Da e: Sep embe 20, 2017.
†Uni e si a Poli ècnica de Ca alunya, Jo di Gi ona1-3, Edi ici C1, E-08034 Ba celona &Cen e In e nacional de
Mè odes Numè ics en Enginye ia, Pa c Medi e ani de la Tecnologia, Es e e Te ades 5, E-08860 Cas ellde els, Spain
E-mail: [email p o ec ed]. SB g a e ully acknowledges he suppo ecei ed om he Ca alan Go e nmen h ough
he ICREA Acadèmia Resea ch P og am. This wo k has been pa ially unded by he p ojec MTM2014-60713-P om
he “Minis e io de Economía, indus ia y Compe i i ad” o Spain.
‡Uni e si a Poli ècnica de Ca alunya, Jo di Gi ona1-3, Edi ici C1, E-08034 Ba celona &Cen e In e nacional de
Mè odes Numè ics en Enginye ia, Pa c Medi e ani de la Tecnologia, Es e e Te ades 5, E-08860 Cas ellde els, Spain E-
mail: [email p o ec ed]. MO g a e ully acknowledges he suppo om he Agència de Ges ió i d’Aju s Uni e si a is
i de Rece ca, unde he FI-AGAUR 2015 g an .
1
a Xi :1703.08466 2 [ma h.NA] 19 Sep 2017
Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 2
1. In oduc ion
A he beginning o he nex decade supe compu e s a e expec ed o each a peak pe o mance o
one exa lop/s, which implies a 100 imes imp o emen wi h espec o cu en supe compu e s. This
imp o emen will no be based on as e p ocesso s, bu on a much la ge numbe o p ocesso s (in
a b oad sense). This si ua ion will ce ainly ha e an impac in la ge scale compu a ional science and
enginee ing (CSE). Pa allel algo i hms will be equi ed o exhibi much highe le els o concu ency,
keeping good scalabili y p ope ies.
When dealing wi h ansien p oblems, since in o ma ion always mo es o wa d in ime, one can
exploi sequen iali y. Howe e , he emendous amoun s o pa allelism o be exploi ed in he nea
u u e ce ainly mo i a es o change his pa adigm. One o he mo i a ions o exploi highe le els o
pa allelism will be o educe he ime- o-solu ion. In he simula ion o o dina y di e en ial equa ions
(ODEs), he way o go is o exploi concu ency in ime. The idea is o de elop pa allel-in- ime sol e s
ha p o ide he solu ion a all ime alues in one sho , ins ead o he adi ional sequen ial app oach
ha exploi s he a ow o ime. I scalable pa allel-in- ime sol e s a e a ailable, he use o highe le els
o pa allelism will ce ainly educe he ime- o-solu ion.
Pa allel-in- ime sol e s a e ecei ing apidly inc easing a en ion. Di e en i e a i e me hods ha e
been conside ed so a , e.g., he pa a eal me hod [15] o spec al de e ed-co ec ion ime in eg a o s
[10]. Wi h ega d o di ec me hods, ime-pa allel me hods can be ound in [12]. In gene al hese
me hods can exploi low le els o concu ency [8] o a e ailo ed o pa icula ypes o equa ions [13].
We e e o [12] o an excellen up- o-da e e iew o ime pa allelism. I has also mo i a ed he
de elopmen o space- ime pa allel sol e s o ansien pa ial di e en ial equa ions (PDEs) [5, 11].
In his wo k, we p opose a pa allel-in- ime sol e o ODEs ha elies on he well-known Schu
complemen me hod in linea algeb a. Fo linea (sys ems o ) ODEs, he app oach can be unde s ood
as a Schu complemen sol e in ime. When he coa se p oblem is oo la ge compa ed o he local
p oblems, due o he s uc u e o he coa se p oblem, we can conside ecu si ely he Schu comple-
men s a egy, leading o mul ile el implemen a ions, in o de o push o wa d scalabili y limi s. The
me hod can be applied o θ-me hods, discon inuous Gale kin (DG) me hods, Runge-Ku a me hods,
and BDF me hods. We also no e ha he p oposed me hod can also be unde s ood as a pa a eal
scheme in which he coa se sol e is au oma ically compu ed in such a way ha he scheme is a di ec
me hod (con e gence in one i e a ion is assu ed). (The in e p e a ion o he pa a eal me hod as an
app oxima ion o he Schu complemen p oblem has al eady been poin ed ou in [11].) As a esul ,
he p oposed me hod sol es he d awback o he pa a eal scheme, i.e., i s poo pa allel e iciency, in-
e sely p opo ional o he numbe o i e a ions being equi ed by he i e a i e algo i hm. One o he
messages o his wo k is o show ha he app oxima ion o he Schu complemen in pa a eal me hods
does no eally pay he p ice when (jus by oughly mul iplying by wo he numbe o ope a ions) one
can ha e a highly scalable di ec pa allel-in- ime sol e .
In o de o ex end hese ideas o nonlinea PDEs, we conside wo di e en s a egies. Fi s , we
conside a global linea iza ion o he p oblem in ime using, e.g., New on’s me hod. We no e ha he
idea o a global linea iza ion o nonlinea ODEs o exploi ime-pa allelism is no new. I was al eady
conside ed by Bellen and Zena o in 1989 [6]. (In any case, he sol e s p oposed in [6] a e di e en om
he ones p esen ed he ein. They a e es ic ed o he S e ensen’s linea iza ion me hod, which leads
o a diagonal p oblem pe nonlinea i e a ions, whe e pa alleliza ion can ob iously be used.) A e
he linea iza ion o he p oblem, we conside he Schu complemen sol e commen ed abo e a e e y
nonlinea i e a ion. A second s a egy consis s in applying he nonlinea Schu complemen s a egy
i s , and nex o conside he linea iza ion o such ope a o , leading o nes ed nonlinea i e a ions.
The pa allel-in- ime ideas in his wo k can na u ally be blended wi h domain decomposi ion ideas
o design highly scalable space- ime pa allel sol e s. We ha e combined hese ideas wi h a mul ile el
balancing DD by cons ain s (BDDC) p econdi ione (see [16, 17]) in [5], by judiciously choosing he
quan i ies o be con inuous among p ocesso s in a space- ime pa i ion, i.e. [9]. The esul ing space-
ime pa allel sol e has been p o ed o be scalable on housands o p ocesso s o di e en ansien
(non)linea PDEs.
Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 3
0
0 1
0 2
0··· n0
0
m(0)
0 m(1)
0 m(2)
0 m(n1)
0
0
1 1
1 2
1··· n1
1
.
.
.
0
`··· n`
`
m(0)
`−1 m(n`)
`−1
Figu e 1. Mul ile el ime pa i ion o [0, T]. The subindex in β
αdeno es he pa i ion
le el, whe eas he supe index deno es he ime s ep in such pa i ion. In o de o ela e
ime alues o wo cons i u i e le els, we use he no a ion β
α= m(β)
α−1, i.e., he ime
alue β
αco esponds o he ime s ep m(β)a he p e ious le el.
The ou line o he a icle is as ollows. In Sec . 2, we s a e he p oblem. We in oduce a ime-pa allel
di ec me hod o linea ODEs based on he compu a ion o a mul ile el ime Schu complemen in Sec .
3. In Sec . 4, we ex end he me hod o nonlinea ODEs, by combining i s a New on linea iza ion s ep
wi h a Schu complemen linea sol e and nex conside ing nonlinea Schu complemen p oblems. We
p esen a de ailed se o nume ical expe imen s in Sec . 5, showing he excellen scalabili y p ope ies
o he p oposed me hods. Finally, we d aw some conclusions in Sec . 6.
2. S a emen o he p oblem
In his sec ion, we de elop a pa allel di ec sol e o he nume ical app oxima ion o o dina y
di e en ial equa ions (ODEs). We conside a sys em o ODEs o size munk:
du( )
d +κ( , u( )) = 0,u( 0) = u0,(1)
o ∈( 0= 0, T]. Le us assume ha κ(·,·)is con inuous wi h espec o he i s a gumen and
Lipschi z con inuous wi h espec o he second a gumen , and ha exis ence and uniqueness holds.
Fo he ime in e al [0, T], we de ine a hie a hical mul ile el pa i ion as ollows (see Fig. 1 o
a de ailed illus a ion). We de ine a (le el-0) ime pa i ion {0 = 0
0, 1
0, . . . , n0
0=T}in o n0 ime
elemen s. Nex , we conside a (le el-1) coa se ime pa i ion {0 = 0
1, . . . , n1
1=T}in o n1 ime
subdomains (o le el-1 elemen s), de ined by agg ega ion o elemen s a he p e ious le el, i.e., o
e e y i∈ {0, . . . , n1} he e exis s an m(i)∈ {0, . . . , n0}such ha i
1= m(i)
0. We p oceed ecu si ely,
c ea ing coa se pa i ions o highe le els. We de ine he ime elemen ia le el-kas he ime in e al
( i
k, i+1
k).
We will p esen he me hod in a gene al way ha is independen o he ime in eg a ion scheme
being used. We de ine he nonlinea ope a o s Ai+1
0:ui7→ ui+1 o i∈ {0, . . . , n0−1}, such ha , gi en
he ini ial alue ui, sol es (1) in ( i
0, i+1
0), and p o ides ui+1 =u( i+1
0). We concep ually s a e he
sol e a he con inuous le el, e en hough one can conside di e en ime in eg a ion schemes ins ead,
e.g., θ-me hods, DG me hods, o Runge-Ku a me hods. The use o BDF- ype schemes equi es some
u he ellabo a ion. We e e o Sec . 3.1 o mo e de ails.
3. An ODE di ec sol e
In his sec ion, we assume ha κ( , ·)is a linea ope a o . (The nonlinea ex ension is desc ibed in
Sec . 4.) In his case, i is easy o check ha Ai+1
0(·)is an a ine mapping, and we ha e Ai+1
0(ui) =
Φi+1
0ui+gi+1
0, whe e Φi+1
0is a linea ope a o (an munk ×munk ma ix). Bo h Φi+1
0and gi+1
0can be
explici ly compu ed om κ(·,·)and o a gi en ime in eg a ion scheme. Thus, he global p oblem
Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 4
(1) o linea ODEs can be s a ed in algeb aic o m as:





I
−Φ1
0I
......
−Φn0
0I










u0
0
u1
0
.
.
.
un0
0




=




u0
g1
0
.
.
.
gn0
0




,(2)
whe e Iis he iden i y ma ix (o size munk ×munk). We can also ep esen he global sys em (2) in
compac no a ion wi h
K0u0=g0,o equi alen ly KII
0KIΓ
0
KΓI
0KΓΓ
0 uI
0
uΓ
0=gI
0
gΓ
0,
whe e we ha e conside ed a seg ega ion o deg ees o eedom (DOFs) a le el-0 u0in o he in e ace
DOFs uΓ
0, namely he ime s ep alues ha a e also in he le el-1 pa i ion, and he in e io do s uI
0.
K0is a 2-banded lowe block- iangula ma ix. In o de o de ine he Schu complemen p oblem, we
i s conside an in e io co ec ion o he p oblem a hand,
KII
0 I
0=gI
0,(3)
i.e., we sol e he sys em (2) in he subspace o ec o s ha anish in he le el-1 ime alues 0
1, . . . , n1
1.
The solu ion o (3) in ol es n1independen local ODE p oblems: sol e o i= 0, . . . , n1−1





I
−Φm(i)+1
0I
......
−Φm(i+1)−1
0I











m(i)
0
m(i)+1
0.
.
.
m(i+1)−1
0






=




0
gm(i)+1
0.
.
.
gm(i+1)−1
0




.(4)
A e he in e io co ec ion, we mus sol e he p oblem
KII
0KIΓ
0
KΓI
0KΓΓ
0 δuI
0
uΓ
0=0
gΓ
0,and compu e uI
0= I
0+δuI
0.(5)
In o de o sol e (5), we de ine he ollowing ex ension ope a o (usually deno ed as he ha monic
ex ension ope a o in he ame o domain decomposi ion sol e s o PDEs):
KII
0KIΓ
0
0 IΓ EI
0
EΓ
0=0
IΓ, hus E0=−(KII
0)−1KIΓ
0
IΓ.(6)
Thus, using he ac ha uΓ
0=u1, he Schu complemen o le el-0 eads:
(KΓΓ
0+KIΓ
0EI
0)u1=gΓ
0−KIΓ
0 I
0, ep esen ed by K1u1=g1.(7)
The Schu complemen o he le el-0 sys em is he le el-1 p oblem. By cons uc ion, he ex ension
ope a o solu ion o (6) can be w i en as a block-diagonal ma ix E0= diag(e(0),e(1),··· ,e(n1−1),I),
which in ol es n1×munk independen local ODE p oblems: sol e o i= 0, . . . , n1−1





I
−Φm(i)+1
0I
......
−Φm(i+1)−1
0I











(e(i))m(i)
0
(e(i))m(i)+1
0
.
.
.
(e(i))m(i+1)−1
0






=




I
0
.
.
.
0




.(8)
A e some manipula ion, he Schu complemen p oblem (7) can be w i en as:





I
−Φ1
1I
......
−Φn1
1I










u0
1
u1
1
.
.
.
un1
1




=




u0
gm(1)
1.
.
.
gm(n1)
1




,(9)
Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 5
whe e Φi
1
.
=Φm(i)
0em(i)−1
(i−1) and gi
1
.
=gm(i)
0+Φm(i)−1
0 m(i)−1
0. Thus, he Schu complemen ma ix K1
a he nex le el has also he same s uc u e as he o iginal p oblem, i.e., i is a ODE- ype sol e o e
he coa se le el-1 ime pa i ion. The compu a ion o he in e io co ec ion, he ex ension ope a o
E0, he Schu complemen ma ix K1, and he Schu complemen igh -hand side g1can eadily be
compu ed in pa allel. In Alg. 1 ( o k= 0), all he s eps o assemble he Schu complemen p oblem
a e lis ed, indica ing on he le -hand side he line ask co esponding le el.
Algo i hm 1: Schu complemen se -up (le el-k)
Da a: Kk,gk
Resul : k,Ek,Kk+1,gk+1
1: Compu e he in e io co ec ion ksolu ion o (3), by sol ing he nk+1 local ODE p oblems (4) o
i= 0,...,nk+1 −1k−1
2: Compu e he ex ension ope a o Eksolu ion o (6), by sol ing he nk+1 ×munk p oblems (8) o
i= 0,...,nk+1 −1, and compu e KIΓ
kEI
0and −KIΓ
kuI
kin (7) k−1
3: Assemble he Schu complemen sys em (9), i.e., Kk+1 and gk+1 (see (7)) k−1→k
In a wo-le el implemen a ion, i.e., `= 1, he Schu complemen p oblem (5) would be compu ed
in se ial. I would inally lead o u0= 0+E0u1. This app oach leads o n1indepeden le el-0
p oblems o size n0
n1and one coa se le el-1 p oblem o size n1. Clea ly, when n1inc eases, he coa se
p oblem becomes he bo leneck o he simula ions. In o de o push o wa d he scalabili y limi s o
his app oach, we can conside a mul ile el Schu complemen echnique. When n1exceeds n0
n1, since
(9) has he same s uc u e as he o iginal sys em (2), one can conside he same Schu complemen
app oach o he le el-1 sys em, leading o a h ee-le el algo i hm. We can p oceed ecu si ely o
include an a bi a y numbe o le els. In Alg. 2, we s a e he mul ile el Schu complemen ODE
sol e . We commen on he pa allel e iciency and compu a ional cos o his algo i hm in Sec .
3.3.
Algo i hm 2: Mul ile el Schu complemen ODE sol e
Da a: K0,g0
Resul : u0=K−1
0g0
1: o k= 0,...,`−1do
2: Call Alg. 1 wi h (Kk,gk) o ge ( k,Ek,Kk+1,gk+1)k, k + 1
3: end
4: Sol e K`u`=g``
5: o k=`−1,...,0do
6: Compu e uk= k+Ekuk+1 k
7: end
3.1. Applica ion o di e en ime in eg a o s. The p e ious app oach can s aigh o wa dly be
used o θ-me hods. Fo DG and Runge-Ku a me hods, we can equi e mul iple in e media e s ages
o mo e om i
0 o i+1
0. In he DG case, we ha e some addi ional ime alues pe ime elemen . We
can conside ha all he elemen alues bu he las one a e elimina ed a he elemen le el, using he
so-called s a ic condensa ion echnique. In his case, he esul ing disc e e p oblem can be s a ed as
in 2. The DG me hod being used only a ec s he exp ession o Φi+1
0and gi+1
0. (We no e ha DG
me hods do no sa is y ime causali y a he elemen le el, bu i does no a ec he lowe 2-banded
block- iangula s uc u e a e he elimina ion o “in e io ” elemen alues.) We p oceed analogously
o mul i-s age Runge-Ku a me hods.
BDF schemes (o second and highe o de ) sligh ly di e om he ac ha he compu a ion o
he solu ion a a gi en ime s ep no only equi es alue om he p e ious ime s ep, bu some

Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 6
addi ional s ages. Fo a BDF(X) scheme, he sys em ma ix in (2) is a (X+1)-banded lowe block-
iangula ma ix. I a ec s he concep o in e ace nodes Γ; o decouple he global p oblems in o local
p oblems, we equi e o inc ease he size o he in e ace X imes. As a esul , he coa se-scale space
dimension is X imes la ge , as well as he numbe o coa se space basis unc ions being compu ed.
In his sense, high o de BDF schemes a e be a bad choice when dealing wi h pa allel compu a ions,
since he in e ace among subdomains inc eases, wi h he co esponding compu a ional cos , due o a
loss o locali y wi h espec o he con inuous p oblem. High o de Runge-Ku a o DG me hods a e
be e sui ed o ime-pa allel compu a ions. In any case, a e conside ing he modi ica ion desc ibed
abo e, he echniques p oposed in his wo k can be applied o BDF me hods.
3.2. Pa a eal in e p e a ion. The mul ile el Schu complemen sol e de ined in Alg. 2 can also
be unde s ood as a (mul ile el) pa a eal scheme. In he pa a eal scheme, we conside a coa se sol e
o p o ide ini ial condi ions o local ine sol e s. Ins ead, in he Schu complemen me hod, one i s
compu es he ( ine) in e io co ec ion, which is equi ed o he assembly o he igh -hand side in he
coa se sol e . The me hod abo e can be s a ed in a di e en way, by de ining he es ic ion ope a o
F0as ollows:
FI
0FΓ
0KII
00
KΓI
0IΓ=0
IΓ, hus F0=−KΓI
0(KII
0)−1IΓ.
Analogously o he ex ension ope a o E0, he compu a ion o he es ic ion ope a o is a block-
diagonal ma ix F0= diag(I, T
(0), T
(1),··· , T
(n1−1)), which in ol es n1×munk independen local (back-
wa ds) ODE p oblems: sol e o i= 0, . . . , n1−1






I−(Φm(i)+2
0)T
I...
...−(Φm(i+1)
0)T
I













m(i)+1
(i)
m(i)+2
(i).
.
.
m(i+1)
(i)







=




0
0
.
.
.
I




.
The well-posedness o he backwa d p oblem is a di ec consequence o he well-posedness o i s ans-
pose, he o wa d p oblem. Thus, he Schu complemen p oblem eads:
K1u1=gΓ
0+FI
0gI
0=g1.
The coa se pa a eal p oblem in he Schu complemen me hod is o Pe o -Gale kin ype, using as
coa se ial space he ange o E0and as coa se es space he ange o FT
0, i.e,
K1=F0K0E0,g1=F0g0.(10)
I is easy o check ha (7) and (10) a e equi alen . The ine sol e is simply he in e io co ec ion
(3). (We no e ha ine and coa se co ec ions a e independen , since hey a e K0-o hogonal.). The
de ini ion o he coa se space is au oma ic and he me hod is no an i e a i e bu a di ec sol e . As
a esul , he me hod does no su e om he low pa allel e iciency o pa a eal me hods, which is
p opo ional o he in e se o pa a eal i e a ions [15]. E en hough he implemen a ion ha in ol es
he compu a ion o he ial and es coa se spaces is he one being used in non-symme ic PDE sol e s
wi h inexac Schu complemen p econdi ioning (see, e.g., [1]), i is no con enien o ODE sol e s,
since i in ol es an addi ional ine sol e .
Fig. 2 depic s o wa d and backwa d coa se unc ions o a es p oblem. The local oscilla ions in
he DG(1) and DG(2) schemes a e due o he ac ha ime causali y does no hold inside he elemen .
(We no e ha he p e ious de elopmen s ha e been conside ed a e elimina ing (using elemen -wise
sol e s) all he elemen alues bu he las one (in ime).) Fig. 3 shows coa se le el-1, ine le el-0, and
ull solu ion o a selec ed simple p oblem wi h di e en coa se DOFs posi ion conside a ion.
Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 7
DG(0) DG(1) DG(2)
π/3 2π/3 π
e(1)
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
02π/3 2π/3 π
e(1)
-1
-0.5
0
0.5
1
1.5
2
0π/3 2π/3 π
e(1)
-0.5
0
0.5
1
1.5
(a) Coa se shape unc ion e(1) o 1
1=π/3
0π/3 2π/3 π
(1)
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
02π/3 2π/3 π
(1)
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
02π/3 2π/3 π
(1)
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
(b) Coa se shape unc ion (1) o 1
1=π/3
Figu e 2. Coa se shape unc ions e(1) and (1) ( 1
1=π/3) o he simple anspo
ope a o du
d . A pa i ion o an in e al [0, π]in o h ee subdomains is conside ed.
Each subdomain is pa i ioned in o 5 ime elemen s. Sub-in e als a e depic ed in
consecu i e di e en colou in o de o aid isualiza ion, and do s aid o iden i y
coa se DOFs posi ion (in he cen e o he elemen o DG(0)).
DG(0) DG(1) DG(2)
0 0.5 1 1.5 2 2.5 3
u( )
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
uF
u C
u = u F + u C
0 0.5 1 1.5 2 2.5 3
u( )
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
1.4 uF
uC
u=u F + u C
0 0.5 1 1.5 2 2.5 3
u( )
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
1.4
uF
uC
u=u F + u C
Figu e 3. Decomposi ion o u0in o ine E0u0and coa se u1componen o he sim-
ple p oblem ∂ u= cos( ), on [0, π]. The ime domain is pa i ioned in o 10 subdomains
and each subdomain is an agg ega ion o 50 elemen s.
3.3. Pa allel e iciency. Le us conside he mul ile el Schu complemen sol e in Alg. 2 o a linea
ODE. Using he same app oach as in mul ig id me hods, we can conside a ixed coa sening a io θ
be ween subdomains, and lea e ee he numbe o le els ` equi ed o a pa icula simula ion wi h
n0 ime s ep alues. The numbe o p ocesso s being used is assumed o be equal o n1=n0/θ, i.e.,
he numbe o subdomains a le el-1, and he numbe o ime s eps pe p ocesso a all le els is θ(a
he las le el i can be smalle ). Thus, we de ine `+ 1 = ceiling(log n0
log θ), whe e ceiling(A) e u ns he
leas in ege g ea e han o equal o A.
Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 8
Alg. 2 equi es a le els 0, . . . , ` −1 o sol e 1 + munk local linea ODE p oblems wi h θ ime s eps
pe p ocesso (see Alg. 1), one o compu e he in e io co ec ion and munk o compu e he ex ension
ope a o . One linea ODE wi h a mos θ ime s eps mus be sol ed a he las le el. The di e en
le els mus be compu ed in a sequen ial way.
Based on he sol e desc ibed abo e, we can es ima e he o de o loa ing-poin ope a ions (FLOPs)
equi ed o sol e he linea ODE. Sequen ially, i is o he o de o FLOP0≈n0(m2
unk +munk),
since we equi e m2
unk +munk ope a ions pe ime s ep. On he o he hand, he numbe o FLOPs
equi ed o compu e he same p oblem in pa allel using Alg. 2 is he one needed o sol e (1 +
munk)p oblems o size n0,n0/θ,. . .,n0/θ`. Using he geome ic sequence sum o mula, we ge
FLOPp≈FLOP0(1 + munk)(1 −1
θ`+1 )(1 −1
θ)−1<FLOP0(1 + munk)(1 −1
θ)−1, bu hese ope a ions
can be pe o med in pa allel exploi ing dis ibu ed memo y machines. Wi h ega d o ime, he o al
CPU ime o he mul ile el Schu complemen in Alg. 2 is he agg ega ion o he CPU ime o he
solu ion o (1 + munk)linea ODEs wi h θ ime s eps o all le els. Thus, he pa allel CPU ime is
CPUp≈`θ(m2
unk +munk)(1 + munk), whe eas he se ial CPU ime is CPU0≈n0(m2
unk +munk). As
a esul , he CPU ime linea ly depends on he size o he global sys em in a e y mild loga i hmic
way, i.e., i inc eases wi h log n0due o he exp ession o `, and he pa allel algo i hm will apidly lead
o a sho e ime- o-solu ion han he se ial sol e .1As a esul , he speed-up o he p oposed di ec
sol e is S= CPU0/CPUp≈P`−1(1 + munk)−1. The speed-up is quasi-linea (i only inc eases wi h
log n0), and hus algo i hmically s ongly scalable. Analogously, he me hod is algo i hmically weakly
scalable, because he o al CPU ime does no depend on he numbe o p ocesso s o global sys em
size (appa om he loga i hmic e m).
4. I e a i e sol e s o nonlinea ODEs
In his sec ion, we assume ha κ(·,·)is nonlinea . The nonlinea ODE (1) in (0, T]can be s a ed in
compac o m as A0(u0) = 0, which can also be spli in o in e io and in e ace ime s eps as ollows:
AI
0(u0)
AΓ
0(u0)=0.(11)
We conside wo di e en ypes o sol e s o he nonlinea p oblem.
4.1. New on-Schu complemen me hods. In o de o sol e he nonlinea ODE, we can use New-
on’s me hod o e he global-in- ime p oblem, and sol e a e e y i e a ion a linea ODE using he
mul ile el Schu complemen in Alg. 2. We can compu e he Jacobian ma ix ela ed o (11) a ound
a poin ¯
u0as:
J0(¯
u0).
=∂A0
∂u0
(¯
u0) = d¯
u0
d +∂K0
∂u0
(¯
u0),(12)
whe e we ha e used he ac ha A0has wo e ms, one ela ed o he ime de i a i e and he o he
one ela ed o κ( , ·)(see 1). Thus, o sol e (12) in ol es he solu ion o a linea ODE o he o m (2).
The esul ing mul ile el New on-Schu complemen sol e o nonlinea ODEs is s a ed in Alg. 3.
Figu e 4 shows he solu ion i e a es using his algo i hm o a selec ed nonlinea p oblem wi h known
analy ic solu ion u= sin( ). Each solu ion upda e ob ained om a linea ized p oblem is sol ed wi h
he di ec sol e in Alg. 2 using wo le els, i.e., `= 1. The nonlinea i e a ions o he NEw on-Schu
complemen me hods do no depend on he pa i ion being used, since i is a linea iza ion o he global
p oblem and a (pa allel) di ec sol e is used a e e y nonlinea i e a ion. In any case, he compa ison
agains he sequen ial app oach is mo e complica ed he e, since di e en nonlinea i e a ions (local s.
global) a e being used in e e y case. We no e ha we can eadily conside o he i e a i e me hods, e.g.,
Pica d’s me hod o Ande son accele a ion echniques. In he case o Pica d’s me hod, he compu a ion
o he Jacobian is no equi ed. Ins ead, he ope a o A0mus be w i en as A0(u0) = e
A0(u0)u0and
1We no e ha he communica ions a e no conside ed in he p e ious es ima ions. In any case, i has been expe i-
men ally obse ed ha he communica ion ime in (incomple e) mul ile el Schu complemen me hods is small compa ed
o he compu a ion ime up o almos hal a million asks in [4].
Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 9
use a e e y nonlinea i e a ion he linea ope a o e
A0(¯
u0)ins ead o J0(¯
u0). In Sec . 5, we conside
a hyb id Pica d-New on nonlinea sol e .
0 ≤ ≤ 2 π
0123456
uk( )
-4
-3.5
-3
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
uk=1
uk=2
uk=3
uk=4
uk=5
uk=6
uk=7
(a) Con e gence his o y
0 ≤ ≤ 2 π
0123456
δu1( )
-4
-3.5
-3
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
u0 = 0
uk=1 = u 0 + δu1
(b) Fi s i e a ion
0 ≤ ≤ 2 π
0123456
δu1( )
-4
-3.5
-3
-2.5
-2
-1.5
-1
-0.5
0
0.5
1
δu1
F
δu1
C
δu1 = δu1
F + δu1
C
(c) Addi i e solu ion
Figu e 4. I e a ions o he solu ion o he nonlinea equa ion ∂ u−u2= cos( ) −
sin2( ) on = [0,2π]using New on’s me hod and he pa allel ODE di ec sol e . Fine
and coa se solu ions o he i s nonlinea solu ion upda e δu1. The ime in e al
is disc e ized wi h 500 ime s eps di ided in o 15 subdomains. DG(0) (equi alen o
Backwa d-Eule ) is used.
Algo i hm 3: New on-Schu complemen sol e
Da a: u0
Resul : u0such ha A0(u0) = 0
1: z←u0% Ini ial guess k
2: while no con e gence do
3: Sol e p oblem J0(z)y=−A0(z)using he mul ile el Schu complemen Alg. 2 wi h
(J0(z),−A0(z)) 0,...,`
4: Assign z←z+yk
5: end
6: Re u n zk, . . . , `
4.2. Nonlinea Schu complemen -New on me hods. Following he ideas in nonlinea domain
decomposi ion (see, e.g., [7, 14]), one can s a e he p oblem as a nonlinea Schu complemen a a
gi en le el and nex i s linea iza ion using, e.g., New on’s me hod. In o de o p esen he p oblem,
we conside he wo-le el case. La e , he algo i hm will be ex ended o mul iple le els. Le us de ine
he le el-1 nonlinea Schu complemen p oblem
A1(u1) = AΓ
0(E0(u1)),whe e E0(u1).
= [EI
0(u1),u1]T,
is he nonlinea ha monic ex ension ope a o , solu ion o
AI
0(E0(u1)) .
=AI
0([EI
0(u1),u1]T) = 0.(13)
We no e ha he compu a ion o E0(u1)in ol es n1independen local nonlinea ODE sol e s, using
he same a ionale as o he linea case. We deno e by [i] he ime s eps a le el-0 in he ime in e al
( i
1, i+1
1), i.e., m(i−1)+1
0, . . . , m(i)−1
0. Thus, (13) can be compu ed as:
A[i]
0(E[i]
0(ui
1)) = 0, o i= 0, . . . , n1−1.(14)
Nonlinea pa allel-in- ime mul ile el Schu complemen sol e s o o dina y di e en ial equa ions 16
[3] S. Badia, A. F. Ma ín, and J. P incipe,On he scalabili y o inexac balancing domain de-
composi ion by cons ain s wi h o e lapped coa se/ ine co ec ions, Pa allel Compu ing, 50 (2015),
pp. 1–24.
[4] S. Badia, A. F. Ma ín, and J. P incipe,Mul ile el Balancing Domain Decomposi ion a
Ex eme Scales, SIAM Jou nal on Scien i ic Compu ing, (2016), pp. C22–C52.
[5] S. Badia and M. Olm,Space- ime balancing domain decomposi ion, SIAM Jou nal on Scien i ic
Compu ing, 39 (2017), pp. C194—-C213.
[6] A. Bellen and M. Zenna o,Pa allel algo i hms o ini ial- alue p oblems o di e ence and
di e en ial equa ions, Jou nal o Compu a ional and Applied Ma hema ics, 25 (1989), pp. 341–
350.
[7] X.-C. Cai and D. E. Keyes,Nonlinea ly p econdi ioned inexac New on algo i hms, SIAM
Jou nal on Scien i ic Compu ing, 24 (2002), pp. 183–200.
[8] A. J. Ch is lieb, C. B. Macdonald, and B. W. Ong,Pa allel high-o de in eg a o s, SIAM
J. Sci. Compu ., 32 (2010), pp. 818–835.
[9] C. R. Doh mann,A p econdi ione o subs uc u ing based on cons ained ene gy minimiza ion,
SIAM Jou nal on Scien i ic Compu ing, 25 (2003), pp. 246–258.
[10] M. Emme and M. J. Minion,Towa d an e icien pa allel in ime me hod o pa ial di e -
en ial equa ions, Comm. App. Ma h. and Comp. Sci., 7 (2012), pp. 105–132.
[11] R. Falgou , S. F iedho , T. Kole , S. MacLachlan, and J. Sch ode ,Pa allel ime
in eg a ion wi h mul ig id, SIAM Jou nal on Scien i ic Compu ing, 36 (2014), pp. C635–C661.
[12] M. J. Gande ,50 yea s o ime pa allel ime in eg a ion, in Mul iple shoo ing and ime domain
decomposi ion, Sp inge , 2015.
[13] M. J. Gande and S. Gü el,Pa aExp: A pa allel in eg a o o linea ini ial– alue p oblems,
SIAM J. Sci. Compu ., 35 (2013), pp. C123–C142.
[14] A. Klawonn, M. Lanse , and O. Rheinbach,Nonlinea FETI-DP and BDDC Me hods,
SIAM Jou nal on Scien i ic Compu ing, 36 (2014), pp. A737–A765.
[15] J. Lions, Y. Maday, and A. Tu inici,A pa a eal in ime disc e iza ion o PDEs, Acad. Sci.
Pa is, 332 (2001), pp. 661–668.
[16] J. Mandel, B. Sousedík, and C. Doh mann,Mul ispace and mul ile el BDDC, Compu ing,
83 (2008), pp. 55–85.
[17] X. Tu,Th ee-le el BDDC in h ee dimensions, SIAM Jou nal on Scien i ic Compu ing, 29 (2007),
pp. 1759–1780.