Nonlinear parallel-in-time Schur complement solvers for ordinary differential equations

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.