parallel-in-timealgorithm:MGRIT资源-CSDN下载

需积分: 4 90 浏览量 2019-01-05 11:49:02 上传评论收藏 1.82MB PDF 举报

资源推荐

资源详情

资源评论

Computing and Visualization in Science (2018) 19:1–17

https://doi.org/10.1007/s00791-018-0296-z

SPECIAL ISSUE PARALLEL-IN-TIME METHODS

Wave propagation characteristics of Parareal

Daniel Ruprecht

Received: 10 April 2017 / Accepted: 10 November 2017 / Published online: 29 May 2018

Abstract

The paper derives and analyses the (semi-)discrete dispersion relation of the Parareal parallel-in-time integration method. It

investigates Parareal’s wave propagation characteristics with the aim to better understand what causes the well documented

stability problems for hyperbolic equations. The analysis shows that the instability is caused by convergence of the ampli-

ﬁcation factor to the exact value from above for medium to high wave numbers. Phase errors in the coarse propagator are

identiﬁed as the culprit, which suggests that speciﬁcally tailored coarse level methods could provide a remedy.

Keywords Parareal · Convergence · Dispersion relation · Hyperbolic problem · Advection-dominated problem

1 Introduction

Parallel computing has become ubiquitous in science and

engineering, but requires suitable numerical algorithms to

be efﬁcient. Parallel-in-time integration methods have been

identiﬁed as a promising direction to increase the level of con-

currency in computer simulations that involve the numerical

solution of time dependent partial differential equations [5].

A variety of methods has been proposed [8,10,12,22,25],

the earliest going back to 1964 [27]. While even complex

diffusive problems can be tackled successfully [11,14,24,

33]—although parallel efﬁciencies remain low—hyperbolic

or advection-dominated problems have proved to be much

harder to parallelise in time. This currently prevents the use

of parallel-in-time integration for most problems in com-

putational ﬂuid dynamics, even though many applications

struggle with excessive solution times and could beneﬁt

greatly from new parallelisation s trategies.

For the Parareal parallel-in-time algorithm there is some

theory available illustrating its limitations in this respect.

Bal shows that Parareal with a sufﬁciently damping coarse

method is unconditionally stable for parabolic problems but

not for hyperbolic equations [2]. An early investigation of

Parareal’s stability properties showed instabilities f or imag-

inary eigenvalues [31]. Gander and Vandewalle [17]givea

detailed analysis of Parareal’s convergence and show that

Daniel Ruprecht

[email protected]

School of Mechanical Engineering, University of Leeds,

Leeds LS2 9JT, UK

even for the simple advection equation u

= 0, Parareal

is either unstable or inefﬁcient. Numerical experiments reveal

that the instability emerges in the nonlinear case as a

degradation of convergence with increasing Reynolds num-

ber [32]. Approaches exist to stabilise Parareal for hyperbolic

equations [3,4,7,13,15,23,29], but typically with signiﬁcant

overhead, leading to further degradation of efﬁciency, or lim-

ited applicability.

Since a key characteristic of hyperbolic problems is

the existence of waves propagating with ﬁnite speeds,

understanding Parareal’s wave propagation characteristics is

important to understand and, hopefully, resolve these prob-

lems. However, no such analysis exists that gives insight into

how the instability emerges. A better understanding of the

instability could show the way to novel methods that allow

the efﬁcient and robust parallel-in-time solution of ﬂows gov-

erned by advection. Additionally, just like for “classical”

time stepping methods, detailed knowledge of Parareal’s the-

oretical properties for test cases will help understanding its

performance for complex test problems where mathematical

theory is not available.

To this end, the paper derives a discrete dispersion rela-

tion for Parareal to study how plane wave solutions u(x, t) =

exp(−iωt) exp(iκ x) are propagated in time. It studies the

discrete phase speed and ampliﬁcation factor and how they

depend on e.g. the number of processors, choice of coarse

propagator and other parameters. The analysis reveals that

the source of the instability is a convergence from above in

the ampliﬁcation factor in higher wave number modes. In

diffusive problems, where high wave numbers are naturally

123

2 D. Ruprecht

strongly damped, this does not cause any problems, but in

hyperbolic problems with little or no diffusion it causes the

ampliﬁcation factors to exceed a value of one and thus trig-

gers instability. Furthermore, the paper identiﬁes phase errors

in the coarse propagator as the source of these issues. This

suggests that controlling coarse level phase errors could be

key to devising efﬁcient parallel-in-time methods for hyper-

bolic equations.

All results presented in this paper have been produced

using pyParareal, a simple open-source Python code. It

is freely available [28] to maximise the usefulness of the

here presented analysis, allowing other researchers to test

different equations or to explore sets of parameters which

are not analysed in this paper.

2 Parareal for linear problems

Parareal [ 25] is a parallel-in-time integration method for an

initial value problem

˙u(t) = Au (t), u(0) = u

∈ C

, 0 ≤ t ≤ T . (1)

For the sake of simplicity we consider only the linear case

where the right hand side is given by a matrix A ∈ C

n,n

.To

parallelise integration of (1) in time, Parareal decomposes

the time interval [0, T ] into P time slices

[0, T ]=[0, T

) ∪[T

, T

) ∪···∪[T

P−1

, T ], (2)

with P indicating the number of processors. Denote as F

δt

and G

t

two “classical” time integration methods with time

steps of length δt and t (e.g. Runge–Kutta methods). For the

sake of simplicity, assume that all slice [T

j−1

, T

) have the

same length T and that this length is an integer multiple of

both δt and t so that T = N

t and T = N

δt.Below,

δt will always denote the time step size of the ﬁne method and

t the time step size of the coarse method, so that we omit

the indices and just write G and F to avoid clutter. Standard

serial time marching using the method denoted as F would

correspond to evaluating

= F(u

p−1

), p = 1,...,P, (3)

where u

≈ u(T

). Instead, after an initialisation procedure

to provide values u

—typically running the coarse method

once—Parareal computes the iteration

= G



p−1



+ F



k−1

p−1



− G



k−1

p−1



, p = 1,...,P

(4)

for k = 1,...,K where the computationally expensive

evaluation of the ﬁne method can be parallelised over P pro-

cessors. If the number of iterations K is small enough and

the coarse method much cheaper than the ﬁne, iteration (4)

can run in less wall clock time than serially computing (3).

2.1 The Parareal iteration in matrix form

As a ﬁrst step toward deriving Parareal’s dispersion relation

we will need to derive its stability function which will require

writing it in matrix form. Consider now the case where both

the coarse and the ﬁne integrator are one-step methods with

stability functions R

and R

. Then, G and F can be expressed

as matrices

= F(u

p−1

) = Fu

p−1

, u

= G(u

p−1

) = Gu

p−1

(5)

with F :=



(Aδt)



and G :=

(

(At)

)

. Denote

as u

= (u

,...,u

) ∈ R

(P+1)n

a vector that contains the

approximate solutions at all time points T

, j = 1,...,P

and the initial value u

. Simple algebra shows that one step

of iteration (4) is equivalent to the block matrix formulation



− M



k−1

+ b (6)

with matrices

⎡

⎢

⎣

−FI

⎤

⎥

⎦

∈ R

(P+1)n,(P+1)n

(7)

and

⎡

⎢

⎣

−GI

⎤

⎥

⎦

∈ R

(P+1)n,(P+1)n

(8)

and a vector b = (u

, 0,...,0) ∈ R

(P+1)n

. Formulation (6)

interpretes Parareal as a preconditioned linear iteration [1].

2.2 Stability function of Parareal

From the matrix formulation of a single Parareal iteration (6),

we can now derive its stability function, that is we can express

the update from the initial value u

to an approximation u

time T = T

using Parareal with K iterations as multiplica-

tion by a single matrix. The ﬁne propagator solution satisﬁes

= b (9)

123

Wave propagation characteristics of Parareal 3

and is a ﬁxed point of iteration (6). Therefore, propagation

of the error

:= u

− u

(10)

is governed by the matrix

E :=



I − M

−1



(11)

in the s ense that

= Ee

k−1

. (12)

Using this notation and applying (6) recursively, it is now

easy to show that

= Eu

k−1



j=0

−1

b. (13)

If, as is typically done, the start value u

for the iteration is

produced by a single run of the coarse method, that is if

= b, (14)

Equation (13) further simpliﬁes to

⎛

⎝



j=0

⎞

⎠

−1

b. (15)

The right hand side vector can be generated from t he initial

value u

via

b = C

(16)

by deﬁning

[

I;0

]

∈ R

(P+1)n,n

, I ∈ R

n,n

, 0 ∈ R

Pn,n

. (17)

Finally, denote as

[

0, I

]

, 0 ∈ R

n,Pn

, I ∈ R

n,n

, (18)

the matrix that selects the last n entries out of u

.Now,a

full Parareal update from some initial value u

to an approx-

imation u

using K iterations can be written compactly as

= C

⎛

⎝



j=0

⎞

⎠

−1

=: M

Parareal

. (19)

The stability matrix M

Parareal

∈ R

n,n

depends on K , T ,

T , P, t, δt, F, G and A. Note that Staff and Rønquist

derived the stability function for the scalar case using Pas-

cal’s tree [31].

2.3 Weak scaling versus longer simulation times

There are two different application scenarios for Parareal that

we can study when increasing the number of processors P.

If we ﬁx the ﬁnal time T , increasing P will lead to better

resolution since the coarse time step t cannot be larger

than the length of a time slice T —the coarse method has to

perform at least one step per time slice. In this scenario, more

processors are used to absorb the cost of higher temporal

resolution (“weak scaling”).

Alternatively, we can use additional processors to compute

until a later ﬁnal time T and this is the scenario investigated

here. Consequently, we study here the case where T and

P increase together and always assume that T = P, that

is each time slice has length one and increasing P means

parallelising over more time slices covering a longer time

interval. Since dispersion properties of numerical methods

are typically analysed for a unit interval, this causes some

issues that we resolve by “normalising” the Parareal stability

function, see Sect. 3.1.

2.4 Maximum singular value

The matrix E deﬁned in (11) determines how quickly Parareal

converges. Note that E is nil-potent with E

= 0, owing to

the fact that after P iterations Parareal will always reproduce

the ﬁne solution exactly. Therefore, all eigenvalues of E are

zero and the spectral radius is not useful to analyse conver-

gence. Below, to investigate convergence, we will therefore

compute the maximum singular value σ of E instead. Since

σ =



it follows from (12) that



≤





k−1



= σ



k−1



≤ σ



(20)

so that if σ<1 Parareal will converge monotonically with-

out stalling. In particular, this rules out behaviour as found by

Gander and Vandewalle for hyperbolic problems, where the

error would ﬁrst increase substantially over the ﬁrst P/2 iter-

ations before beginning to decrease [16]. However, achieving

fast convergence and good efﬁciency will typically require

σ  1. Note that if the coarse method is used to generate u

it follows from (9) and (14) that the initial error is

= u

− u



−1

− M

−1



b. (21)

The size of σ depends on the accuracy “gap” between the

coarse and ﬁne integrator and the wave number. Figure 1

shows σ for varying values of t when backward Euler is

used for both coarse and ﬁne method. Clearly, as the coarse

123

剩余16页未读，继续阅读

评论收藏

内容反馈

wushulincsdn

粉丝: 0

parallel-in-time algorithm: MGRIT

最新资源

parallel-in-time algorithm: MGRIT

Parallel-in-time algorithm: diagonalization technique

Parallel Algorithms

parallel-tasks-gradle-plugin:在同一模块中并发执行gradle任务

Algorithm-Bitonic-Sort：Algorithm :: Sort-使用Bitonic排序对数字进行排序这是Ken Batcher的Bitonic mergesort的Perl 5实现。

cypress-parallel-specs-locally:在本地并行执行 Cypress 规范的脚本

webpack-parallel-uglify-plugin：更快的uglifyjs插件

数学的英语单词(.doc

jmeter-parallel-0.9.jar

The efficient-parallel stripe noise removal algorithm with low resource

Dynamic-Parallel-Machine-Scheduling-with-Deep-Q-network:为了帮助其他研究人员重制或重用我们的工作，我们在github上共享了我们的代码

Parallel to MIPI CSI-2 TX Bridge

C-Sharp-Parallel-Programming:时间：2019-05-10标签：c＃paralelprogramlamaileyaptaptermörnekler

Parallel-DataLoader-in-TensorFlow:在TensorFlow中并行加载数据以提高整个系统效率

parallel-studio-xe-2019u4-install-guide-lin.pdf

前端开源库-webpack-parallel-uglify-plugin

oop-java-create-streams-OliverGrob:oop-java-create-streams-OliverGrob由GitHub Classroom创建

Smart-Stealing-for-Parallel-GC-in-JVM:智能窃取

divide-up-square-in-parallel-slices:将一个正方形分成平行的切片，其面积与数据成正比

bb-parallel-port-cape:BeagleBone的并行端口海角

各大磁共振公司的序列名词对比表MRI Acronyms

python-parallel-programming-cookbook-cn::open_book:《Python Parallel Programming Cookbook》中文版

Parallel-ForkManager-0.7.7

牛津高中英语模块总复习知识点大全PPT学习教案.pptx

matlab如何敲代码-matlab-parallel-server-on-aws:使用CloudFormation建立MATLABParal

parallel-supercomputing-in-SIMD-architectures

前端开源库-webpack-parallel-uglify-3-plugin

Algorithms Parallel and Sequential_2019.pdf

matlab分时代码-matlab-parallel-server-on-azure:使用Azure部署站立MATLABParallelSer

parallel-cucumber-failed-rerun:这是一个演示如何并行运行Cucumber功能以及重新运行失败的场景的演示。 分步教程在这里

Lab-NODE5-Using-the-Async-Series-and-Parallel-Modules:作业5

java基础知识-内部类

verilog语法实现同步FIFO设计及仿真代码

最新资源

parallel-cucumber-failed-rerun:这是一个演示如何并行运行Cucumber功能以及重新运行失败的场景的演示。分步教程在这里