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.     

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.     

Overlapping Schwarz waveform relaxation method for the solution of the convection–diffusion equation

In this article we study the convergence of the overlapping Schwarz wave form relaxation method for solving the convection–diffusion equation over multi-overlapped subdomains. It is shown that the method converges linearly and superlinearly over long and short time intervals, and the convergence depends on the size of the overlap. Numerical results are presented from solving specific types of model problems to demonstrate the convergence and the role of the size of the overlap. Copyright © 2007 John Wiley & Sons, Ltd.     

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.     

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     

Overlapping Schwarz preconditioners for spectral element methods in nonstandard domains and heterogeneous media

Overlapping Schwarz preconditioners are constructed and numerically studied for Gauss-Lobatto-Legendre (GLL) spectral element discretizations of heterogeneous elliptic problems on nonstandard domains defined by Gordon-Hall transfinite mappings. The results of several test problems in the plane show that the proposed preconditioners retain the good convergence properties of overlapping Schwarz preconditioners for standard affine GLL spectral elements, i.e. their convergence rate is independent of the number of subdomains, of the spectral degree in the case of generous overlap and of the discontinuity jumps in the coefficients of the elliptic operator, while in the case of small overlap, the convergence rate depends on the inverse of the overlap size.     

利用自然边界归化求解平面弹性方程外边值问题的SCHWARZ算法

1引言平面弹性方程在水利土建等工程技术领域有着广泛应用．其中,孔边应力集中等问题,都是无界区域问题．我们可以通过各种实验手段研究上述问题．而随着计算机和有限元技术的迅猛发展,数值解法提供了一种研究上述问题的有效途径．对于有界区域上的平面弹性方程,我们可以直接利用有限元方法求解,对于其中的大规模问题可以利用区域分解和并行技术求解．但这些方法难以处理无界区域问题．虽然对于某些典型区域上的外问题（例如,圆孔外区域和＿些规则形状裂纹）可以针对具体情况利用复变函数论方法予以解决,但对于一般的无界区域问题广…     

无界区域上基于自然边界归化的双调和方程的一种重叠型区域分解法

1．引言双调和方程边值问题的一个力学背景是薄板弯曲问题．对于有界区域上的双调和方程，可以直接利用协调元和非协调元求解18，10］．我们考虑双调和方程Dirichlet外边值问题其中0是充分光滑闭曲线ro之外的无界区域，naro关于0的单位外法向量．引理1．且卜］．若。0EH’／‘（几），gEH‘／‘（fo），则问题（1．1）在W0z（fi）中有唯一解·这里由迹定理，可找到一个具有紧支集的函数识。。，g）E护（炉）满足可。0；g）【F。＝。0和则问题（1．1）等价于如下齐次边值问题其中f—一面‘B有紧支集．边值问题（工．2）又可转化为变分问…     

Méthodes de relaxation d'ondes (SWR) pour l'équation de la chaleur en dimension 1

We introduce Schwarz Waveform Relaxation algorithms (SWR) for the heat equation which have a much faster convergence rate than the classical one due to optimized transmission conditions between subdomains. We analyze the asymptotic dependence of the convergence rate with respect to the size of the overlap and the time step. To cite this article: M.J. Gander, L. Halpern, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

基于半平面上自然边界归化的无界区域上的Schwarz交替法及其离散化

In this paper,we discuss a Schwarz alternating method for a kind of unboundeddomains, which can be decomposed into a bounded domain and a half-planar domain. Finite Element Method and Natural Boudary Reduction are used alternatively. The uniform geometric convergence of both continuous and discrete problems is proved. The theoretical results as well as the numerical examples show thatthe convergence rate of this discrete Schwarz iteration is independent of the finiteelement mesh size, but dependent on the overlapping degree of subdomains.     

A feasible direction algorithm for convex optimization: Global convergence rates

At each iteration, the algorithm determines a feasible descent direction by minimizing a linear or quadratic approximation to the cost on the feasible set. The algorithm is easy to implement if the approximation is easy to minimize on the feasible set, which happens in some important cases. Convergence rate information is obtained, which is sufficient to enable deduction of the number of iterations needed to achieve a specified reduction in the distance from the optimum (measured in terms of the cost). Existing convergence rates for algorithms for solving such convex problems are either asymptotic (and so do not enable the required number of iterations to be deduced) or decrease as the number of constraints increases. The convergence rate information obtained here, however, is independent of the number of constraints. For the case where the quadratic approximation to the cost is not strictly convex (which includes the linear approximation case), the diameter is the only property of the feasible set which affects the convergence rate information. If the quadratic approximation is strictly convex, the convergence rate is independent of the size and geometry of the feasible set. An application to a control-constrained optimal control problem is outlined.     

A NON-OVERLAPPING DOMAIN DECOMPOSITION ALGORITHM BASED ON THE NATURAL BOUNDARY REDUCTION FOR WAVE EQUATIONS IN AN UNBOUNDED DOMAIN

In this paper, a new domain decomposition method based on the natural boundary reduction, which solves wave problems over an unbounded domain, is suggestted. An circular artificial boundary is introduced. The original unbounded domain is divided into two subdomains, an internal bounded region and external unbounded region outside the artificial boundary. A Dirichlet-Neumann(D-N) alternating iteration algorithm is constructed. We prove that the algorithm is equavilent to preconditional Richardson iteration method. Numerical studies are performed by finite element method. The numerical results show that the convergence rate of the discrete D-N iteration is independent of the finite element mesh size.     

Waveform relaxation methods for implicit differential equations

We apply a Runge-Kutta-based waveform relaxation method to initial-value problems for implicit differential equations. In the implementation of such methods, a sequence of nonlinear systems has to be solved iteratively in each step of the integration process. The size of these systems increases linearly with the number of stages of the underlying Runge-Kutta method, resulting in high linear algebra costs in the iterative process for high-order Runge-Kutta methods. In our earlier investigations of iterative solvers for implicit initial-value problems, we designed an iteration method in which the linear algebra costs are almost independent of the number of stages when implemented on a parallel computer system. In this paper, we use this parallel iteration process in the Runge-Kutta waveform relaxation method. In particular, we analyse the convergence of the method. The theoretical results are illustrated by a few numerical examples.     

Convergence properties of a class of boundary element approximations to linear diffusion problems with localized nonlinear reactions

We consider a boundary element (BE) Algorithm for solving linear diffusion desorption problems with localized nonlinear reactions. The proposed BE algorithm provides an elegant representation of the effect of localized nonlinear reactions, which enables the effects of arbitrarily oriented defect structures to be incorporated into BE models without having to perform severe mesh deformations. We propose a one-step recursion procedure to advance the BE solution of linear diffusion localized nonlinear reaction problems and investigate its convergence properties. The separation of the linear and nonlinear effects by the boundary integral formulation enables us to consider the convergence properties of approximations to the linear terms and nonlinear terms of the boundary integral equation separately. For the linear terms we investigate how the degree of piecewise polynomial collocation in space and the size of the spatial mesh relative to the time step affects the accumulation of errors in the one-step recursion scheme. We develop a novel convergence analysis that combines asymptotic methods with Lax's Equivalence Theorem. We identify a dimensionless meshing parameter θ whose magnitudé governs the performance of the one-step BE schemes. In particular, we show that piecewise constant (PWC) and piecewise linear (PWL) BE schemes are conditionally convergent, have lower asymptotic bounds placed on the size of time steps, and which display excess numerical diffusion when small time steps are used. There is no asymptotic bound on how large the tie steps can be–this allows the solution to be advanced in fewer, larger time steps. The piecewise quadratic (PWQ) BE scheme is shown to be unconditionally convergent; there is no asymptotic restriction on the relative sizes of the time and spatial meshing and no numerical diffusion. We verify the theoretical convergence properties in numerical examples. This analysis provides useful information about the appropriate degree of spatial piecewise polynomial and the meshing strategy for a given problem. For the nonlinear terms we investigate the convergence of an explicit algorithm to advance the solution at an active site forward in time by means of Caratheodory iteration combined with piecewise linear interpolation. We consider a model problem comprising a singular nonlinear Volterra equation that represents the effect of the term in the BE formulation that is due to a single defect. We prove the convergence of the piecewise linear Caratheodory iteration algorithm to a solution of the model problem for as long as such a solution can be shown to exist. This analysis provides a theoretical justification for the use of piecewise linear Caratheodory iterates for advancing the effects of localized reactions.     

Schwarz preconditioners for the spectral element discretization of the steady Stokes and Navier-Stokes equations

Summary. The - spectral element discretization of the Stokes equation gives rise to an ill-conditioned, indefinite, symmetric linear system for the velocity and pressure degrees of freedom. We propose a domain decomposition method which involves the solution of a low-order global, and several local problems, related to the vertices, edges, and interiors of the subdomains. The original system is reduced to a symmetric equation for the velocity, which can be solved with the conjugate gradient method. We prove that the condition number of the iteration operator is bounded from above by , where C is a positive constant independent of the degree N and the number of subdomains, and is the inf-sup condition of the pair -. We also consider the stationary Navier-Stokes equations; in each Newton step, a non-symmetric indefinite problem is solved using a Schwarz preconditioner. By using an especially designed low-order global space, and the solution of local problems analogous to those decribed above for the Stokes equation, we are able to present a complete theory for the method. We prove that the number of iterations of the GMRES method, at each Newton step, is bounded from above by . The constant C does not depend on the number of subdomains or N, and it does not deteriorate as the Newton iteration proceeds. Received March 2, 1998 / Revised version received October 12, 1999 / Published online March 20, 2001     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

无界区域上基于自然边界归化的一种重叠型区域分解法及其离散化

1．引言由于科学技术的迅猛发展，人们遇到许多大规模科学和工程计算问题．随着并行计算机的出现和应用，并行技术越来越得到人们的重视和研究．区域分解法成为并行计算和处理这类问题的主要方法之一．但是，对于无界区域上的椭圆边值问题，因进行区域分解后至少有一个区域仍为无界区域，故仅应用通常的区域分解算法求解是不够的．由于边界归化是处理无界区域问题的有效手段，通常采用边界元和有限元耦合的方法求解此类问题IZ，6。8。121．或片什适当的人工边界并在此边界上加近似边界条件，再在有限区域应用有限元方法求解【人习．近年来…     

Parallel split least‐squares mixed finite element method for parabolic problem

Based on overlapping domain decomposition, a new class of parallel split least‐squares (PSLS) mixed finite element methods is presented for solving parabolic problem. The algorithm is fully parallel. In the overlapping domains, the partition of unity is applied to distribute the corrections reasonably, which makes that the new method only needs one or two iteration steps to reach given accuracy at each time step while the classical Schwarz alternating methods need many iteration steps. The dependence of the convergence rate on the spacial mesh size, time increment, iteration times, and subdomains overlapping degree is analyzed. Some numerical results are reported to confirm the theoretical analysis.     

Balancing domain decomposition for problems with large jumps in coefficients

The Balancing Domain Decomposition algorithm uses in each iteration solution of local problems on the subdomains coupled with a coarse problem that is used to propagate the error globally and to guarantee that the possibly singular local problems are consistent. The abstract theory introduced recently by the first-named author is used to develop condition number bounds for conforming linear elements in two and three dimensions. The bounds are independent of arbitrary coefficient jumps between subdomains and of the number of subdomains, and grow only as the squared logarithm of the mesh size . Computational experiments for two- and three-dimensional problems confirm the theory.

     

Multipoint Boundary-Value Solution of Two-Point Boundary-Value Problems

An iterative scheme, in which two-point boundary-value problems (TPBVP) are solved as multipoint boundary-value problems (MPBVP), which are independent TPBVPs in each iteration and on each subdomain, is derived for second-order ordinary differential equations. Several equations are solved for illustration. In particular, the algorithm is described in detail for the first boundary-value problem (FBVP) and second boundary-value problem (SBVP). A possible extension to higher-order BVPs is discussed briefly. The procedure may be used when the original TPBVP cannot be solved (does not converge) in a single long domain. It is suitable for implementation on computers with parallel processing. However, that issue is beyond the scope of this paper. The long domain is cut into a large number of subdomains and, based on assumed boundary conditions at the interface points, the resulting local BVPs are solved by any convenient conventional method. The local solutions are then patched by using simple matching formulas, which are derived below, rather than solving large systems of algebraic equations, as it is done in similar existing methods. Assuming that the local solutions are obtained by the most efficient methods, the overall convergence speed depends on the speed of matching. The proposed matching algorithm is based on a fixed-point iteration and has only a linear convergence rate. The rate can be made quadratic by applying standard accelerating schemes, which is beyond the scope of this article.