Quasi-optimized Schwarz methods for reaction diffusion equations with time delay

In this paper, we investigate the convergence behavior of the Schwarz waveform relaxation (SWR) algorithms for solving PDEs with time delay. We choose the reaction diffusion equations with a constant time delay as the underlying model problem and try to derive optimized transmission conditions of Robin type. To this end, we propose a new method to get quasi-optimized parameter involved in the transmission conditions and it is shown that this method is essentially different from the existing ones. Moreover, when the situation is reduced into the heat equations with a constant delay, we show that this method results in a more efficient quasi-optimized parameter. Numerical results are provided to validate our theoretical results.     

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.     

Additive Schwarz algorithms for parabolic convection-diffusion equations

Summary In this paper, we consider the solution of linear systems of algebraic equations that arise from parabolic finite element problems. We introduce three additive Schwarz type domain decomposition methods for general, not necessarily selfadjoint, linear, second order, parabolic partial differential equations and also study the convergence rates of these algorithms. The resulting preconditioned linear system of equations is solved by the generalized minimal residual method. Numerical results are also reported.This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003 at the Courant Institute, New York University and in part by the National Science Foundation under contract number DCR-8521451 and ECS-8957475 at Yale University     

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

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

Absorbing boundary conditions and optimized Schwarz waveform relaxation

The numerical evaluation of the transforms in the title, and their inverses, is considered, using a variety of decomposition, truncation, and quadrature methods. Extensive numerical testing is provided and an application given to the numerical evaluation of the kernel of a Fredholm integral equation of interest in mixed boundary value problems on wedge-shaped domains. AMS subject classification (2000) 44A15, 65D30, 65R10     

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.     

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

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

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.     

SCHWARZ TYPE DOMAIN DECOMPOSITION ALGORITHMS FOR PARABOLIC EQUATIONS AND ERROR ESTIMATES

1.IntroductionTheSchwarzalternatingmethodwasintroducedbyH.A.SchWarz(1870)120yearsagoasatechniqueforprovingtheexistenceofsolutionstocertainellipticproblemsdefinedonadomainofcomplicatedgeometries.Sincethenthemethodhasbeenextendedtononlinearproblemsandhasbeenproventobeasuitabledivideandconquertechniquetosolveawideclassofproblems,forinstance,see[2,3,8--10].Inthispaperweareinterestedinsolvingtheparabolicproblemsbyusingimplicitschemes,suchasbackwardEulerschemeinthetimevariable.Ateachfixedtimeleve…     

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.     

Discrete time waveform relaxation method for stochastic delay differential equations

We propose in this paper the discrete time waveform relaxation method for the stochastic delay differential equations and prove that it is convergent in the mean square sense. In addition, the results obtained are supported by numerical experiments.     

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.     

反应扩散方程的奇摄动

§ 1　 IntroductionThe nonlinearsingularly perturbed problem is a very attractive subjectof study in theinternational academic circles[1 ] .During the past decade many approximate methods havebeen developed and refined,including the method of average,boundary layer method,matched asymptotic expansions,and multiple scales.Recently,many scholars,for example,Bohé[2 ] ,Butuzov and Smurov[3] ,O Malley[4] ,Butuzov,Nefedov and Schneider[5] ,Kelley[6]and so on did a great deal of work.Mo consider…     

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.     

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.     

On convergence conditions of waveform relaxation methods for linear differential-algebraic equations

For linear constant-coefficient differential-algebraic equations, we study the waveform relaxation methods without demanding the boundedness of the solutions based on infinite time interval. In particular, we derive explicit expression and obtain asymptotic convergence rate of this class of iteration schemes under weaker assumptions, which may have wider and more useful application extent. Numerical simulations demonstrate the validity of the theory.     

Fast solution algorithms for exponentially tempered fractional diffusion equations

In this article, a fast‐iterative method and a fast‐direct method is proposed for solving one‐dimensional and two‐dimensional tempered fractional diffusion equations with constant coefficients. The proposed iterative method is accelerated by circulant preconditioning which is shown to converge superlinearly while the proposed direct method is based on circulant and skew‐circulant representation for Toeplitz matrix inversion. In one‐dimensional case, the operation cost of the proposed methods are both shown to be with memory requirement in each time step, where is the number of spatial nodes. With the alternating direction implicit method, it is proven that the proposed fast solution algorithms can be extended to handle two‐dimensional tempered fractional diffusion equations with operation cost and memory requirement in each time step, where the number of spatial nodes in ‐direction and ‐direction both equal to . Numerical examples are provided to illustrate the effectiveness and efficiency of the proposed methods.     

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.     

Computing periodic solutions of linear differential-algebraic equations by waveform relaxation

We propose an algorithm, which is based on the waveform relaxation (WR) approach, to compute the periodic solutions of a linear system described by differential-algebraic equations. For this kind of two-point boundary problems, we derive an analytic expression of the spectral set for the periodic WR operator. We show that the periodic WR algorithm is convergent if the supremum value of the spectral radii for a series of matrices derived from the system is less than 1. Numerical examples, where discrete waveforms are computed with a backward-difference formula, further illustrate the correctness of the theoretical work in this paper.