In this paper, we consider the problem of accelerating the numerical simulation of time dependent problems involving a multi-step time scheme by the parareal algorithm. The parareal method is based on combining predic...
详细信息
In this paper, we consider the problem of accelerating the numerical simulation of time dependent problems involving a multi-step time scheme by the parareal algorithm. The parareal method is based on combining predictions made by a coarse and cheap propagator, with corrections computed with two propagators: the previous coarse and a precise and expensive one used in a parallel way over the time windows. A multi-step time scheme can potentially bring higher approximation orders than plain one-step methods but the initialisation of each time window needs to be appropriately chosen. Our main contribution is the design and analysis of an algorithm adapted to this type of discretisation without being too much intrusive in the coarse or fine propagators. At convergence, the parareal algorithm provides a solution that coincides with the solution of the fine solver. In the classical version of parareal, the local initial condition of each time window is corrected at every iteration. When the fine and/or coarse propagators is a multi-step time scheme, we need to choose a consistent approximation of the solutions involved in the initialisation of the fine solver at each time windows. Otherwise, the initialisation error will prevent the parareal algorithm to converge towards the solution with fine solver's accuracy. In this paper, we develop a variant of the algorithm that overcome this obstacle. Thanks to this, the parareal algorithm is more coherent with the underlying time scheme and we recover the properties of the original version. We show both theoretically and numerically that the accuracy and convergence of the multi-step variant of parareal algorithm are preserved when we choose carefully the initialisation of each time window.
The influence of time-integrator on the convergence rate of the parallel-in-time algorithmparareal has been extensively studied in literature, but the effect of space discretization was only rarely considered. In thi...
详细信息
The influence of time-integrator on the convergence rate of the parallel-in-time algorithmparareal has been extensively studied in literature, but the effect of space discretization was only rarely considered. In this paper, using the advection-diffusion equation parametrized by a diffusion coefficient nu > 0 as the model, we show that the space discretization indeed has a non-negligible effect on the convergence rate, especially when nu is small. In particular, for two space discretizations-the centered FD (finite difference) method and a Compact FD method of order 4, we show that the algorithm converges with very different rates, even though both the coarse and fine solvers of the algorithm are strongly stable under these two space discretizations. Numerical results for one-dimensional and two-dimensional cases are presented to validate the theoretical predictions.
In this paper, we study the convergence properties of the parareal algorithm with uniform coarse time grid and arbitrarily distributed (nonuniform) fine time grid, which may be changed at each iteration. We employ the...
详细信息
In this paper, we study the convergence properties of the parareal algorithm with uniform coarse time grid and arbitrarily distributed (nonuniform) fine time grid, which may be changed at each iteration. We employ the backward-Euler method as the coarse propagator and a general single-step time-integrator as the fine propagator. Specifically, we consider two implementations of the coarse grid correction: the standard time-stepping mode and the parallel mode via the so-called diagonalization technique. For both cases, we prove that under certain conditions of the stability function of the fine propagator, the convergence factor of the parareal algorithm is not larger than that of the associated algorithm with a uniform fine time grid. Furthermore, we show that when such conditions are not satisfied, one can indeed observe degenerations of the convergence rate. The model that is used for performing the analysis is the Dahlquist test equation with nonnegative parameter, and the numerical results indicate that the theoretical results hold for nonlinear ODEs and linear ODEs where the coefficient matrix has complex eigenvalues.
The classical parareal algorithm for time-periodic problems, solving a periodic-like coarse problem, called the periodic parareal algorithm with periodic coarse problem (PP-PC), usually converges slowly. In this paper...
详细信息
The classical parareal algorithm for time-periodic problems, solving a periodic-like coarse problem, called the periodic parareal algorithm with periodic coarse problem (PP-PC), usually converges slowly. In this paper, we present a new parallel-in-time algorithm for time-periodic problems based on the classical PP-PC algorithm and the Krylov subspace method. In this new algorithm, a new propagator derived by the Krylov subspace is chosen as the coarse propagator instead of the classical coarse propagator in the PP-PC algorithm. And because of the special characteristic of time-periodic problems, the Krylov subspace enhanced PP-PC algorithm needs to solve a periodic coarse problem on the coarse time grid on each iteration. We provide two different kinds of theoretical bounds under different assumptions for the proposed algorithm. Numerical results illustrate our analysis with two effective theoretical bounds for the heat equation, the wave equation, and the viscous Burgers equation, where we could also find that the new proposed algorithm converges faster than the classical PP-PC algorithm.
This paper presents a parareal algorithm with parameterized propagators for linear parametric differential equations over a wide range of parameters. Through transforming the initial value problem into nonparametric O...
详细信息
This paper presents a parareal algorithm with parameterized propagators for linear parametric differential equations over a wide range of parameters. Through transforming the initial value problem into nonparametric ODEs based on Taylor series, we construct the general parameterized fine and coarse propagators for the parareal algorithm in each time subinterval. Furthermore, to accelerate the convergence of the algorithm, the coarse propagator based on the waveform relaxation method is proposed. By analysing the computational complexity of the WR propagator and the general coarse propagator, we find these two propagators are appropriate for the different situations. Finally, the convergence analysis of the parareal algorithm with these propagators is presented and our analysis is illustrated with two numerical experiments.
In this paper, we introduce a new strategy for solving highly oscillatory two-dimensional Vlasov-Poisson systems by means of a specific version of the parareal algorithm. The novelty consists in using reduced models, ...
详细信息
In this paper, we introduce a new strategy for solving highly oscillatory two-dimensional Vlasov-Poisson systems by means of a specific version of the parareal algorithm. The novelty consists in using reduced models, obtained from the two-scale convergence theory, for the coarse solving. The reduced models are useful to approximate the original Vlasov-Poisson model at a low computational cost since they are free of high oscillations. Both models are numerically solved in a particle-in-cell framework. We illustrate this strategy with numerical experiments based on long time simulations of a charged beam in a focusing channel and under the influence of a rapidly oscillating external electric field. On the basis of computing times, we provide an analysis of the efficiency of the parareal algorithm in terms of speedup.
We study in this paper the parareal (parallel-in-time) algorithm for the linear switched systems (LSS) on the basis of two coarse time subinterval divisions: the parareal algorithm based on the original switching time...
详细信息
We study in this paper the parareal (parallel-in-time) algorithm for the linear switched systems (LSS) on the basis of two coarse time subinterval divisions: the parareal algorithm based on the original switching time subinterval of the LSS (PLSS algorithm), and the parareal algorithm based on the new time subinterval division (NPLSS algorithm) for making the computation time of each processor well-balanced. These two proposed algorithms are able to compute the LSS with high-frequency oscillatory and discontinuous input efficiently. Besides, the convergence analysis of the two algorithms is provided. (C) 2021 Elsevier Ltd. All rights reserved.
We present a new parareal algorithm based on a diagonalization technique proposed recently. The algorithm uses a single implicit Runge-Kutta method with the same small step-size for both the F and G propagators in par...
详细信息
We present a new parareal algorithm based on a diagonalization technique proposed recently. The algorithm uses a single implicit Runge-Kutta method with the same small step-size for both the F and G propagators in parareal and would thus converge in one iteration when used directly like this, without, however, any speedup due to the sequential way parareal uses G. We then approximate G with a head-tail coupled condition such that G can be parallelized using diagonalization in time. We show that with a suitable choice of the parameter in the head-tail condition, our new parareal algorithm converges very rapidly, both for parabolic and hyperbolic problems, even in the nonlinear case. We illustrate our new algorithm with numerical experiments.
In this paper,we propose a parareal algorithm for stochastic differential equations(SDEs),which proceeds as a two-level temporal parallelizable integrator with the Milstein scheme as the coarse propagator and the exac...
详细信息
In this paper,we propose a parareal algorithm for stochastic differential equations(SDEs),which proceeds as a two-level temporal parallelizable integrator with the Milstein scheme as the coarse propagator and the exact solution as the fine *** convergence order of the proposed algorithm is analyzed under some regular ***,numerical experiments are dedicated to illustrate the convergence and the convergence order with respect to the iteration number k,which show the efficiency of the proposed method.
The time parallel solution of optimality systems arising in PDE constrained optimization could be achieved by simply applying any time parallel algorithm, such as parareal, to solve the forward and backward evolution ...
详细信息
The time parallel solution of optimality systems arising in PDE constrained optimization could be achieved by simply applying any time parallel algorithm, such as parareal, to solve the forward and backward evolution problems arising in the optimization loop. We propose here a different strategy by devising directly a new time parallel algorithm, which we call ParaOpt, for the coupled forward and backward nonlinear partial differential equations. ParaOpt is inspired by the parareal algorithm for evolution equations and thus is automatically a two-level method. We provide a detailed convergence analysis for the case of linear parabolic PDE constraints. We illustrate the performance of ParaOpt with numerical experiments for both linear and nonlinear optimality systems.
暂无评论