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.     

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

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

Robin型离散Schwarz波形松弛算法的收敛性分析

Schwarz波形松弛(Schwarz waveform relaxation,SWR)是一种新型区域分解算法,是当今并行计算研究领域的焦点之一,但针对该算法的收敛性分析基本上都停留在时空连续层面.从实际计算角度看,分析离散SWR算法的收敛性更重要.本文考虑SWR研究领域中非常流行的Robin型人工边界条件,分析时空离散参数t和x、模型参数等因素对算法收敛速度的影响.Robin型人工边界条件中含有一个自由参数p,可以用来优化算法的收敛速度,但最优参数的选取却需要求解一个非常复杂的极小-极大问题.本文对该极小-极大问题进行深入分析,给出最优参数的计算方法.本文给出的数值实验结果表明所获最优参数具有以下优点:(1)相比连续情形下所获最优参数,利用离散情形下获得的参数可以进一步提高Robin型SWR算法在实际计算中的收敛速度,当固定t或x而令另一个趋于零时,利用离散情形下所获参数可以使算法的收敛速度具有鲁棒性(即收敛速度不随离散参数的减小而持续变慢).(2)相比连续情形下所获收敛速度估计,离散情形下获得的收敛速度估计可以更加准确地预测算法的实际收敛速度.     

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 forward–backward heat equation

In this article we analyzed the convergence of the Schwarz waveform relaxation method for solving the forward–backward heat equation. Numerical results are presented for a specific type of model problem.     

A two-level additive Schwarz method for the Morley nonconforming element approximation of a nonlinear biharmonic equation

In this paper, we consider the well known Morley nonconformingelement approximation of a nonlinear biharmonic equation whichis related to the well-known two-dimensional Navier–Stokesequations. Firstly, optimal energy and H¹-norm estimates areobtained. Secondly, a two-level additive Schwarz method is presentedfor the discrete nonlinear algebraic system. It is shown thatif the Reynolds number is sufficiently small, the two-levelSchwarz method is optimal, i.e. the convergence rate of theSchwarz method is independent of the mesh size and the numberof subdomains.     

Existence and uniqueness of entire solutions for a reaction-diffusion equation

We consider entire solutions of u_t=u_xx-f(u), i.e. solutions that exist for all (x,t)∈R², where f(0)=f(1)=0<f^′(0). In particular, we are interested in the entire solutions which behave as two opposite wave fronts of positive speed(s) approaching each other from both sides of the x-axis and then annihilating in a finite time. In the case f^′(1)>0, we show that such entire solution exists and is unique up to space-time translations. In the case f^′(1)<0, we derive two families of such entire solutions. In the first family, one cannot be any space-time translation of the other. Yet all entire solutions in the second family only differ by a space-time translation.     

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 preconditioners for indefinite time harmonic Maxwell equations

Time harmonic Maxwell equations in lossless media lead to a second order differential equation for the electric field involving a differential operator that is neither elliptic nor definite. A Galerkin method using Nedelec spaces can be employed to get approximate solutions numerically. The problem of preconditioning the indefinite matrix arising from this method is discussed here. Specifically, two overlapping Schwarz methods will be shown to yield uniform preconditioners.

     

Fourier-Laplace analysis of the multigrid waveform relaxation method for hyperbolic equations

The multigrid waveform relaxation (WR) algorithm has been fairly studied and implemented for parabolic equations. It has been found that the performance of the multigrid WR method for a parabolic equation is practically the same as that of multigrid iteration for the associated steady state elliptic equation. However, the properties of the multigrid WR method for hyperbolic problems are relatively unknown. This paper studies the multigrid acceleration to the WR iteration for hyperbolic problems, with a focus on the convergence comparison between the multigrid WR iteration and the multigrid iteration for the corresponding steady state equations. Using a Fourier-Laplace analysis in two case studies, it is found that the multigrid performance on hyperbolic problems no longer shares the close resemblance in convergence factors between the WR iteration for parabolic equations and the iteration for the associated steady state equations.     

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

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

A Schwarz-based domain decomposition method for the dispersion equation

We propose a Schwarz-based domain decomposition method for solving a dispersion equation consisting on the linearized KdV equation without the advective term, using simple interface operators based on the exact transparent boundary conditions for this equation. An optimization process is performed for obtaining the approximation that provides the method with the fastest convergence to the solution of the monodomain problem.     

On Schwarz Alternating Methods for the Subsonic Full Potential Equation

The Schwarz alternating method can be used to solve elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence of elliptic boundary value problems in each of the subdomains. The full potential equation is derived from the Navier–Stokes equations assuming the fluid is compressible, inviscid, irrotational and isentropic. It is being used by the aircraft industry to model flow over an airfoil or even an entire aircraft. This paper shows that the additive and multiplicative versions of the Schwarz alternating method, when applied to the full potential equation in three dimensions, converge to the true solution geometrically. The assumptions are that the initial guess and the true solution are everywhere subsonic. We use the convergence proof by Tai and Xu and modify it for certain closed convex subsets.     

A note on the small-time development of the solution to a scalar, non-linear, singular reaction-diffusion equation

In this note, we consider a class of scalar, non-linear, singular (in the sense that the reaction terms in the equation are not Lipschitz continuous) reaction-diffusion equations with positive initial data being of (a) O(x^–) or (b) O(x^–e^{– x}) at large x (dimensionless distance), where , > 0 and are constants. We establish, by developing the small–t (dimensionless time) asymptotic structure of the solution, that the support of the solution becomes finite in infinitesimal time in both cases (a) and (b) above. The asymptotic form for the location of the edge of the support as t 0 is given in both cases.Received: June 6, 2002; revised: May 6 and June 4, 2003     

A note on the H 1-convergence of the overlapping Schwarz waveform relaxation method for the heat equation

The overlapping Schwarz waveform relaxation method is a parallel iterative method for solving time-dependent PDEs. Convergence of the method for the linear heat equation has been studied under infinity norm but it was unknown under the energy norm at the continuous level. The question is interesting for applications concerning fluxes or gradients of the solutions. In this work, we show that the energy norm of the errors of iterates is bounded by their infinity norm. Therefore, we give an affirmative answer to this question for the first time.     

Existence and uniqueness of the solution of a space-time periodic reaction-diffusion equation

This paper is concerned with the study of the periodic solutions and the entire solutions of the equation:

(1)     

Remarks on the optimal convolution kernel for CSOR waveform relaxation

The convolution SOR waveform relaxation method is a numerical method for solving large-scale systems of ordinary differential equations on parallel computers. It is similar in spirit to the SOR acceleration method for solving linear systems of algebraic equations, but replaces the multiplication with an overrelaxation parameter by a convolution with a time-dependent overrelaxation function. Its convergence depends strongly on the particular choice of this function. In this paper, an analytic expression is presented for the optimal continuous-time convolution kernel and its relation to the optimal kernel for the discrete-time iteration is derived. We investigate whether this analytic expression can be used in actual computations. Also, the validity of the formulae that are currently used to determine the optimal continuous-time and discrete-time kernels is extended towards a larger class of ODE systems.     

A comparison result for multisplittings and waveform relaxation methods

We show that certain multisplitting iterative methods based on overlapping blocks yield faster convergence than corresponding nonoverlapping block iterations, provided the coefficient matrix is an M-matrix. This result can be used to compare variants of the waveform relaxation algorithm for solving initial value problems. The methods under consideration use the same discretization technique, but are based on multisplittings with different overlaps. Numerical experiments on the Intel iPSC/860 hypercube are included.