Analysis of a new parareal algorithm based on waveform relaxation method for time-periodic problems

We present a new parallel algorithm for time-periodic problems by combining the waveform relaxation method and the parareal algorithm, which performs the parallelism both in sub-systems and in time. In the new algorithm, the waveform relaxation propagator is chosen as a new fine propagator instead of the classical fine propagator. And because of the characteristic of time-periodic problems, the new parareal waveform relaxation algorithm needs to solve a periodic coarse problem at the coarse level in each iteration. The new algorithm is proved to converge linearly at most. Then the theoretic parallel efficiency of the new algorithm is also considered. Numerical experiments confirm our analysis finally.     

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.     

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.     

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.     

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.     

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.     

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.     

Optimization of Schwarz waveform relaxation over short time windows

Schwarz waveform relaxation algorithms (SWR) are naturally parallel solvers for evolution partial differential equations. They are based on a decomposition of the spatial domain into subdomains, and a partition of the time interval of interest into time windows. On each time window, an iteration, during which subproblems are solved in space-time subdomains, is then used to obtain better and better approximations of the overall solution. The information exchange between subdomains in space-time is performed through classical or optimized transmission conditions (TCs). We analyze in this paper the optimization problem when the time windows are short. We use as our model problem the optimized SWR algorithm with Robin TCs applied to the heat equation. After a general convergence analysis using energy estimates, we prove that in one spatial dimension, the optimized Robin parameter scales like the inverse of the length of the time window, which is fundamentally different from the known scaling on general bounded time windows, which is like the inverse of the square root of the time window length. We illustrate our analysis with a numerical experiment.     

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.     

Multigrid Waveform Relaxation for Anisotropic Partial Differential Equations

Multigrid waveform relaxation provides fast iterative methods for the solution of time-dependent partial differential equations. In this paper we consider anisotropic problems and extend multigrid methods developed for the stationary elliptic case to waveform relaxation methods for the time-dependent parabolic case. We study line-relaxation, semicoarsening and multiple semicoarsening multilevel methods. A two-grid Fourier–Laplace analysis is used to estimate the convergence of these methods for the rotated anisotropic diffusion equation. We treat both continuous time and discrete time algorithms. The results of the analysis are confirmed by numerical experiments.     

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.

     

Preconditioning waveform relaxation iterations for differential systems

We discuss preconditioning and overlapping of waveform relaxation methods for sparse linear differential systems. It is demonstrated that these techniques significantly improve the speed of convergence of the waveform relaxation iterations resulting from application of various modes of block Gauss-Jacobi and block Gauss-Seidel methods to differential systems. Numerical results are presented for linear systems resulting from semi-discretization of the heat equation in one and two space variables. It turns out that overlapping is very effective for the system corresponding to the one-dimensional heat equation and preconditioning is very effective for the system corresponding to the two-dimensional case.The work of the second author was supported by the National Science Foundation under grant NSF DMS 92-08048.     

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.     

Semi-discrete Schwarz waveform relaxation algorithms for reaction diffusion equations

For time dependent problems, the Schwarz waveform relaxation (SWR) algorithm can be analyzed both at the continuous and semi-discrete level. For consistent space discretizations, one would naturally expect that the semi-discrete algorithm performs as predicted by the continuous analysis. We show in this paper for the reaction diffusion equation that this is not always the case. We consider two space discretization methods—the 2nd-order central finite difference method and the 4th-order compact finite difference method, and for each method we show that the semi-discrete SWR algorithm with Dirichlet transmission condition performs as predicted by the continuous analysis. However, for Robin transmission condition the semi-discrete SWR algorithm performs worse than predicted by the continuous analysis. For each type of transmission conditions, we show that the convergence factors of the semi-discrete SWR algorithm using the two space discretization methods are (almost) equal. Numerical results are presented to validate our conclusions.     

Piecewise homotopy analysis method and convergence analysis for formally well-posed initial value problems

In this paper, we apply the Schwarz waveform relaxation (SWR) method to the one-dimensional Schrödinger equation with a general linear or a nonlinear potential. We propose a new algorithm for the Schrödinger equation with time-independent linear potential, which is robust and scalable up to 500 subdomains. It reduces significantly computation time compared with the classical algorithms. Concerning the case of time-dependent linear potential or the nonlinear potential, we use a preprocessed linear operator for the zero potential case as a preconditioner which leads to a preconditioned algorithm. This ensures high scalability. In addition, some newly constructed absorbing boundary conditions are used as the transmission conditions and compared numerically.     

Spectral collocation and waveform relaxation methods for nonlinear delay partial differential equations

We investigate Chebyshev spectral collocation and waveform relaxation methods for nonlinear delay partial differential equations. Waveform relaxation methods allow to replace the system of nonlinear differential equations resulting from the application of spectral collocation methods by a sequence of linear problems which can be effectively integrated in a parallel computing environment by highly stable implicit methods. The effectiveness of this approach is illustrated by numerical experiments on the Hutchinson's equation. The boundedness of waveform relaxation iterations is proved for the Hutchinson's equation. This result is used in the proof of the superlinear convergence of the iterations.     

The performance of preconditioned waveform relaxation techniques for pseudospectral methods

Waveform relaxation techniques for the pseudospectral solution of the heat conduction problem are discussed. The pseudospectral operator occurring in the equation is preconditioned by transformations in both space and time. In the spatial domain, domain stretching is used to more equally distribute the grid points across the domain, and hence improve the conditioning of the differential operator. Preconditioning in time is achieved either by an exponential or a polynomial transformation. Block Jacobi solutions of the systems are obtained and compared. The preconditioning in space by domain stretching determines the effectiveness of waveform relaxation in this case. Preconditioning in time is also effective in reducing the number of iterations required for convergence. The polynomial transformation is preferred, because it removes the requirement of a matrix exponential calculation in the time-stepping schemes and, at the same time, is no less effective than the direct exponential preconditioning. © 1996 John Wiley & Sons, Inc.     

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

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

Comparison of time and spatial collocation methods for the heat equation

We combine a high-order compact finite difference scheme to approximate the spatial derivatives and collocation techniques for the time component to numerically solve the two-dimensional heat equation. We use two approaches to implement the time collocation methods. The first one is based on an explicit computation of the coefficients of polynomials and the second one relies on differential quadratures. We also implement a spatial collocation method where differential quadratures are utilized for spatial derivatives and an implicit scheme for marching in time. We compare all the three techniques by studying their merits and analyzing their numerical performance. Our experiments show that all of them achieve high-accurate approximate solution but the time collocation method with differential quadrature offers (with respect to the one with explicit polynomials) less computational complexity and a better efficiency. All our computations, based on parallel algorithms, are carried out on the CRAY SV1.     

Overlapping Schwarz waveform relaxation method for the solution of the reaction-diffusion equation

We are interested in solving time dependent problems using domain decomposition methods. In the classical approach, one discretizes first the time dimension and then one solves a sequence of steady problems by a domain decomposition method. In this article, we treat directly the time dependent problem and we study a Schwarz waveform relaxation algorithm for the convection diffusion equation. We study the convergence of the overlapping Schwarz waveform relaxation method for solving the reaction-diffusion equation over multi-overlapped subdomains. Also we will show that the method converges linearly and superlinearly over long and short time intervals, and the convergence depends on the size of overlap. Numerical results are presented from solutions of a specific model problems to demonstrate the convergence, linear and superlinear, and the role of the overlap size.