Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

The Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods are nonoverlapping spatial domain decomposition methods to solve evolution problems, while the parareal algorithm is in time parallel fashion. Based on the combinations of these space and time parallel strategies, we present and analyze two parareal algorithms based on the Dirichlet-Neumann and the Neumann-Neumann waveform relaxation method for the heat equation by choosing Dirichlet-Neumann/Neumann-Neumann waveform relaxation as two new kinds of fine propagators instead of the classical fine propagator. Both new proposed algorithms could be viewed as a space-time parallel algorithm, which increases the parallelism both in space and in time. We derive for the heat equation the convergence results for both algorithms in one spatial dimension. We also illustrate our theoretical results with numerical experiments finally.

     

A parareal waveform relaxation algorithm for semi-linear parabolic partial differential equations

We report a new parallel iterative algorithm for semi-linear parabolic partial differential equations (PDEs) by combining a kind of waveform relaxation (WR) techniques into the classical parareal algorithm. The parallelism can be simultaneously exploited by WR and parareal in different directions. We provide sharp error estimations for the new algorithm on bounded time domain and on unbounded time domain, respectively. The iterations of the parareal and the WR are balanced to optimize the performance of the algorithm. Furthermore, the speedup and the parallel efficiency of the new approach are analyzed. Numerical experiments are carried out to verify the effectiveness of the theoretic work.     

CONVERGENCE ANALYSIS OF PARAREAL ALGORITHM BASED ON MILSTEIN SCHEME FOR STOCHASTIC DIFFERENTIAL EQUATIONS

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 propagator. The convergence order of the proposed algorithm is analyzed under some regular assumptions. Finally, numerical experiments are dedicated to illustrating the convergence and the convergence order with respect to the iteration number $k$, which show the efficiency of the proposed method.     

抛物型时间周期问题的Schwarz波形松驰方法

周期稳态是科学和工程系统中一类重要的运行状态,其计算复杂度远高于相应的初值问题,因此有更迫切的并行计算需要.我们提出了计算抛物型方程时间周期解的并行方法—基于区域分解(又称Schwarz方法)的波形松驰方法,该方法只需在子区域上求解较低维的周期问题.我们分析了两种不同的传输条件下方法的收敛性,并用数值实验支持了理论结果.     

Résolution d'EDP par un schéma en temps «pararéel »

The purpose of this Note is to propose a time discretization of a partial differential evolution equation that allows for parallel implementations. The method, based on an Euler scheme, combines coarse resolutions and independent fine resolutions in time in the same spirit as standard spacial approximations. The resulting parallel implementation is done in the non standard time direction. Its main goal concerns real time problems, hence the proposed terminology of “parareal” algorithm.     

Parareal in time approximation of the Korteveg-deVries-Burgers' equations

The parareal in time algorithm is a predictor corrector method that allows to get parallelisation through the time. It consists in segmenting the interval of time integration into slabs, then propose iteratively seed values at the left hand side of each of the slabs. The derivation of the seed values is done sequentially and involves propagator that should mimic the equation to be solved but should be very cheap and parallel accurate propagations of each seed value over each slab. Various approaches have been proposed to get the coarse propagator, in this paper, we use the averaging approach developed by Barenblatt and Chorin for the Korteveg-deVries-Burgers' equations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A parareal approach of semi‐linear parabolic equations based on general waveform relaxation

We present a parareal approach of semi‐linear parabolic equations based on general waveform relaxation (WR) at the partial differential equation (PDE) level. An algorithm for initial‐boundary value problem and two algorithms for time‐periodic boundary value problem are constructed. The convergence analysis of three algorithms are provided. The results show that the algorithm for initial‐boundary value problem is superlinearly convergent while both algorithms for the time‐periodic boundary value problem linearly converge to the exact solutions at most. Numerical experiments show that the parareal algorithms based on general WR at the PDE level, compared with the parareal algorithm based on the classical WR at the ordinary differential equations (ODEs) level (the PDEs is discretized into ODEs), require much fewer number of iterations to converge.     

THE REDUCED BASIS TECHNIQUE AS A COARSE SOLVER FOR PARAREAL IN TIME SIMULATIONS

In this paper, we extend the reduced basis methods for parameter dependent problems to the parareal in time algorithm introduced by Lions et al. [12] and solve a nonlinear evolutionary parabolic partial differential equation. The fine solver is based on the finite element method or spectral element method in space and a semi-implicit Runge-Kutta scheme in time. The coarse solver is based on a semi-implicit scheme in time and the reduced basis approximation in space. Of[line-online procedures are developed, and it is proved that the computational complexity of the on-line stage depends only on the dimension of the reduced basis space （typically small）. Parareal in time algorithms based on a multi-grids finite element method and a multi-degrees finite element method are also presented. Some numerical results are reported.     

Parareal Algorithms Applied to Stochastic Differential Equations with Conserved Quantities

In this paper, we couple the parareal algorithm with projection methods of the trajectory on a specific manifold, defined by the preservation of some conserved quantities of stochastic differential equations. First, projection methods are introduced as the coarse and fine propagators. Second, we apply the projection methods for systems with conserved quantities in the correction step of original parareal algorithm. Finally, three numerical experiments are performed by different kinds of algorithms to show the property of convergence in iteration, and preservation in conserved quantities of model systems.     

一种新的局部时间积分的区域分解波形松弛算法

提出一种新的区域分解波形松弛算法, 使得可以在不同的子域采用不同的时间步长来并行求解线性抛物方程的初边值问题. 与传统的区域分解波形松弛算法相比, 该算法可以通过预条件子来加快收敛速度, 并且对内存的需求大大降低. 给出了局部时间步长一种具体的实现方法, 证明了离散解的存在唯一性, 并在时间连续水平分析了预条件系统. 数值实验显示了新算法的有效性.     

Analysis of the parareal approach based on discontinuous Galerkin method for time-dependent Stokes equations

This paper analyzes a parareal approach based on discontinuous Galerkin (DG) method for the time-dependent Stokes equations. A class of primal discontinuous Galerkin methods, namely variations of interior penalty methods, are adopted for the spatial discretization in the parareal algorithm (we call it parareal DG algorithm). We study three discontinuous Galerkin methods for the time-dependent Stokes equations, and the optimal continuous in time error estimates for the velocities and pressure are derived. Based on these error estimates, the proposed parareal DG algorithm is proved to be unconditionally stable and bounded by the error of discontinuous Galerkin discretization after a finite number of iterations. Finally, some numerical experiments are conducted which confirm our theoretical results, meanwhile, the efficiency of the parareal DG algorithm can be seen through a parallel experiment.     

Absorbing boundary conditions for the wave equation and parallel computing

Absorbing boundary conditions have been developed for various types of problems to truncate infinite domains in order to perform computations. But absorbing boundary conditions have a second, recent and important application: parallel computing. We show that absorbing boundary conditions are essential for a good performance of the Schwarz waveform relaxation algorithm applied to the wave equation. In turn this application gives the idea of introducing a layer close to the truncation boundary which leads to a new way of optimizing absorbing boundary conditions for truncating domains. We optimize the conditions in the case of straight boundaries and illustrate our analysis with numerical experiments both for truncating domains and the Schwarz waveform relaxation algorithm.

     

The parareal algorithm as a new approach for numerical integration of ODEs in real-time simulations in automotive industry

In the automotive industry, there is a growing demand for real-time simulation of dynamic physical models. This work investigates the capability of the parareal algorithm to meet these requirements for those physical models that are described by a system of ODEs. For this purpose, it is investigated in numerical simulations how different choices for some of the degrees of freedom arising in the implementation of parareal affect the accuracy and run time of the numerical integration in case of a benchmark task. Furthermore, the stability of the parareal scheme is investigated theoretically in case that the coarse stage uses a simplified model. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Overlapping Schwarz Waveform Relaxation for the Heat Equation in N Dimensions

We analyze overlapping Schwarz waveform relaxation for the heat equation in n spatial dimensions. We prove linear convergence of the algorithm on unbounded time intervals and superlinear convergence on bounded time intervals. In both cases the convergence rates are shown to depend on the size of the overlap. The linear convergence result depends also on the number of subdomains because it is limited by the classical steady state result of overlapping Schwarz for elliptic problems. However the superlinear convergence result is independent of the number of subdomains. Thus overlapping Schwarz waveform relaxation does not need a coarse space for robust convergence independent of the number of subdomains, if the algorithm is in the superlinear convergence regime. Numerical experiments confirm our analysis. We also briefly describe how our results can be extended to more general parabolic problems.     

Convergence of Parareal with spatial coarsening

The effect is investigated of using a reduced spatial resolution in the coarse propagator of the time-parallel Parareal method for a finite difference discretization of the linear advection-diffusion equation. It is found that convergence can critically depend on the order of the interpolation used to transfer the coarse propagator solution to the fine mesh in the correction step. The effect also strongly depends on the employed spatial and temporal resolution. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Parallel Schwarz waveform relaxation method for a semilinear heat equation in a cylindrical domain

We present here a proof of well-posedness and convergence for the parallel Schwarz waveform relaxation algorithm adapted to the semilinear heat equation in a cylindrical domain. It relies on a careful estimate of a local time of existence thanks to the Banach theorem in a well chosen metric space, together with new cylindrical error estimates.     

Discretized Multisplitting AOR Waveform Relaxation Algorithms for Initial Value Problem of Systems of ODEs

1.IntroductionInthedevelopmentofnewelectricalcircuits,thesimulationofthebehaviourofthecircuithasbecomeanessentialtoolforelectricalengineers.Fromthelayoutofthecircuitanonlinearsystemofordinarydifferentialequationsisgeneratedwhichdescribesthedynamicalbehaviourofthecircuit.Inthesimulationofverylargescaleintegrated(VLSI)circuitsthedimensionofthesystemofODEscanbecomeverylarge.Moreoversincethesystemisstiff,solvingthesesystemsisaverycomputionallyintensivetaskandtheuseofsupercomputersbecomesin-evit…     

Parallel solution of elasticity problems using overlapping aggregations

The finite element (FE) solution of geotechnical elasticity problems leads to the solution of a large system of linear equations. For solving the system, we use the preconditioned conjugate gradient (PCG) method with two-level additive Schwarz preconditioner. The preconditioning is realised in parallel. A coarse space is usually constructed using an aggregation technique. If the finite element spaces for coarse and fine problems on structural grids are fully compatible, relations between elements of matrices of the coarse and fine problems can be derived. By generalization of these formulae, we obtain an overlapping aggregation technique for the construction of a coarse space with smoothed basis functions. The numerical tests are presented at the end of the paper.     

Local and parallel finite element algorithm based on the partition of unity method for the incompressible MHD flow

Based on the partition of unity method (PUM), a local and parallel finite element method is designed and analyzed for solving the stationary incompressible magnetohydrodynamics (MHD). The key idea of the proposed algorithm is to first solve the nonlinear system on a coarse mesh, divide the globally fine grid correction into a series of locally linearized residual problems on some subdomains derived by a class of partition of unity, then compute the local subproblems in parallel, and obtain the globally continuous finite element solution by assembling all local solutions together by the partition of unity functions. The main feature of the new method is that the partition of unity provide a flexible and controllable framework for the domain decomposition. Finally, the efficiency of our theoretical analysis is tested by numerical experiments.     

Local and Parallel Finite Element Algorithms for Eigenvalue Problems

Abstract Some new local and parallel finite element algorithms are proposed and analyzed in this paper foreigenvalue problems.With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced tothe solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraicsystems on fine grid by using some local and parallel procedure.A theoretical tool for analyzing these algorithmsis some local error estimate that is also obtained in this paper for finite element approximations of eigenvectorson general shape-regular grids.