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.     

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.

     

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.     

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.     

Waveform relaxation for reaction-diffusion equations

We report a new waveform relaxation (WR) algorithm for general semi-linear reaction-diffusion equations. The superlinear rate of convergence of the new WR algorithm is proved, and we also show the advantages of the new approach superior to the classical WR algorithms by the estimation on iteration errors. The corresponding discrete WR algorithm for reaction-diffusion equations is presented, and further the parallelism of the discrete WR algorithm is analyzed. Moreover, the new approach is extended to handle the coupled reaction-diffusion equations. Numerical experiments are carried out to verify the effectiveness of the theoretic work.     

Domain decomposition and splitting methods for Mortar mixed finite element approximations to parabolic equations

Summary We introduce in this article a new domain decomposition algorithm for parabolic problems that combines Mortar Mixed Finite Element methods for the space discretization with operator splitting schemes for the time discretization. The main advantage of this method is to be fully parallel. The algorithm is proven to be unconditionally stable and a convergence result in (Δt/h ^1/2) is presented.     

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.     

Neumann–Neumann waveform relaxation algorithm in multiple subdomains for hyperbolic problems in 1D and 2D

We present a Waveform Relaxation (WR) version of the Neumann–Neumann algorithm for the wave equation in space‐time. The method is based on a nonoverlapping spatial domain decomposition, and the iteration involves subdomain solves in space‐time with corresponding interface conditions, followed by a correction step. Using a Fourier‐Laplace transform argument, for a particular relaxation parameter, we prove convergence of the algorithm in a finite number of steps for the finite time intervals. The number of steps depends on the size of the subdomains and the time window length on which the algorithm is employed. We illustrate the performance of the algorithm with numerical results, followed by a comparison with classical and optimized Schwarz WR methods. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 514–530, 2017     

Nonlinear structural finite element analysis using the preconditioned Lanczos method on serial and parallel computers

The application of the Lanczos algorithm in Newton-like methods for solving non-linear systems of equations arising in nonlinear structural finite element analysis is presented. It is shown that with appropriate preconditioners iterative methods can be developed which are robust and efficient even for ill conditioned problems. Though the real advantage of iterative solvers seems to exist on distributed memory machines, even on serial machines the performance can be improved compared with direct solvers while saving memory capacity. With a specific modification of the Lanczos algorithm in combination with arc-length procedures a further speed-up of the nonlinear analysis can be achieved. For parallel implementations domain decomposition methods are used. A parallel preconditioning strategy based on an incomplete factorisation method is presented. An example is taken and the quality and efficiency of two different domain decomposition methods are discussed for a large shell structure. This work was supported by the BMBF (Bundesministerium für Bildung und Forschung) of Germany.     

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)     

Parallel domain decomposition procedures of improved D-D type for parabolic problems

Two parallel domain decomposition procedures for solving initial-boundary value problems of parabolic partial differential equations are proposed. One is the extended D-D type algorithm, which extends the explicit/implicit conservative Galerkin domain decomposition procedures, given in [5], from a rectangle domain and its decomposition that consisted of a stripe of sub-rectangles into a general domain and its general decomposition with a net-like structure. An almost optimal error estimate, without the factor H^−1/2 given in Dawson-Dupont’s error estimate, is proved. Another is the parallel domain decomposition algorithm of improved D-D type, in which an additional term is introduced to produce an approximation of an optimal error accuracy in L²-norm.     

Multi-grid dynamic iteration for parabolic equations

We study the method which is obtained when a multi-grid method (in space) is first applied directly to a parabolic intitial-boundary value problem, and discretization in time is done only afterwards. This approach is expected to be well-suited to parallel computation. Further, time marching can be done using different time step-sizes in different parts of the spatial domain.     

Fast parallel solvers for symmetric boundary element domain decomposition equations

Summary. The boundary element method (BEM) is of advantage in many applications including far-field computations in magnetostatics and solid mechanics as well as accurate computations of singularities. Since the numerical approximation is essentially reduced to the boundary of the domain under consideration, the mesh generation and handling is simpler than, for example, in a finite element discretization of the domain. In this paper, we discuss fast solution techniques for the linear systems of equations obtained by the BEM (BE-equations) utilizing the non-overlapping domain decomposition (DD). We study parallel algorithms for solving large scale Galerkin BE–equations approximating linear potential problems in plane, bounded domains with piecewise homogeneous material properties. We give an elementary spectral equivalence analysis of the BEM Schur complement that provides the tool for constructing and analysing appropriate preconditioners. Finally, we present numerical results obtained on a massively parallel machine using up to 128 processors, and we sketch further applications to elasticity problems and to the coupling of the finite element method (FEM) with the boundary element method. As shown theoretically and confirmed by the numerical experiments, the methods are of algebraic complexity and of high parallel efficiency, where denotes the usual discretization parameter. Received August 28, 1996 / Revised version received March 10, 1997     

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)     

On the use of rational iterations and domain decomposition methods for the Helmholtz problem

An iterative algorithm for the numerical solution of the Helmholtz problem is considered. It is difficult to solve the problem numerically, in particular, when the imaginary part of the wave number is zero or small. We develop a parallel iterative algorithm based on a rational iteration and a nonoverlapping domain decomposition method for such a non-Hermitian, non-coercive problem. Algorithm parameters (artificial damping and relaxation) are introduced to accelerate the convergence speed of the iteration. Convergence analysis and effective strategies for finding efficient algorithm parameters are presented. Numerical results carried out on an nCUBE2 are given to show the efficiency of the algorithm. To reduce the boundary reflection, we employ a hybrid absorbing boundary condition (ABC) which combines the first-order ABC and the physical $Q$ ABC. Computational results comparing the hybrid ABC with non-hybrid ones are presented. Received May 19, 1994 / Revised version received March 25, 1997     

A parallel four step domain decomposition scheme for coupled forward–backward stochastic differential equations

Motivated by the idea of imposing paralleling computing on solving stochastic differential equations (SDEs), we introduce a new domain decomposition scheme to solve forward–backward stochastic differential equations (FBSDEs) parallel. We reconstruct the four step scheme in Ma et al. (1994) [1] and then associate it with the idea of domain decomposition methods. We also introduce a new technique to prove the convergence of domain decomposition methods for systems of quasilinear parabolic equations and use it to prove the convergence of our scheme for the FBSDEs.     

Parallel defect control

How can small-scale parallelism best be exploited in the solution of nonstiff initial value problems? It is generally accepted that only modest gains inefficiency are possible, and it is often the case that “fast” parallel algorithms have quite crude error control and stepsize selection components. In this paper we consider the possibility of using parallelism to improvereliability andfunctionality rather than efficiency. We present an algorithm that can be used with any explicit Runge-Kutta formula. The basic idea is to take several smaller substeps in parallel with the main step. The substeps provide an interpolation facility that is essentially free, and the error control strategy can then be based on a defect (residual) sample. If the number of processors exceeds (p ? 1)/2, wherep is the order of the Runge-Kutta formula, then the interpolant and the error control scheme satisfy very strong reliability conditions. Further, for a given orderp, the asymptotically optimal values for the substep lengths are independent of the problem and formula and hence can be computed a priori. Theoretical comparisons between the parallel algorithm and optimal sequential algorithms at various orders are given. We also report on numerical tests of the reliability and efficiency of the new algorithm, and give some parallel timing statistics from a 4-processor machine.     

Domain decomposition iterative procedures for solving scalar waves in the frequency domain

The propagation of dispersive waves can be modeled relevantly in the frequency domain. A wave problem in the frequency domain is difficult to solve numerically. In addition to having a complex–valued solution, the problem is neither Hermitian symmetric nor coercive in a wide range of applications in Geophysics or Quantum–Mechanics. In this paper, we consider a parallel domain decomposition iterative procedure for solving the problem by finite differences or conforming finite element methods. The analysis includes the decomposition of the domain into either the individual elements or larger subdomains ( of finite elements). To accelerate the speed of convergence, we introduce relaxation parameters on the subdomain interfaces and an artificial damping iteration. The convergence rate of the resulting algorithm turns out to be independent on the mesh size and the wave number. Numerical results carried out on an nCUBE2 parallel computer are presented to show the effectiveness of the method. Received October 30, 1995 / Revised version received January 10, 1997     

A parallel algorithm for large systems of Volterra integral equations of Abel type

A significative number of recent applications require numerical solution of large systems of Abel–Volterra integral equations. Here we propose a parallel algorithm to numerically solve a class of these systems, designed for a distributed-memory MIMD architecture. In order to achieve a good efficiency we employ a fully parallel and fast convergent waveform relaxation (WR) method and evaluate the lag term by using FFT techniques. To accelerate the convergence of the WR method and to best exploit the parallel architecture we develop special strategies. The performances of the resulting code, NSWR4, are illustrated on some examples.     

Coupling methods for heat transfer and heat flow: Operator splitting and the parareal algorithm

We propose an operator splitting method for coupling heat transfer and heat flow equations. This work is motivated by the need to couple independent industrial heat transfer solvers (e.g., the Aura-Fluid software package) and heat flow solvers (e.g., Openfoam). Such packages are often used to simulate the influence of solar heat in car bodies and are coupled by A-B splitting techniques. The main goal of this work is the acceleration of the coupled software system by iterative operator splitting methods and additional time-parallelism using the parareal algorithm. We present these new splitting techniques along with some novel convergence results and test the splitting-parareal combination on various numerical problems.