Convergence analysis of waveform relaxation methods for neutral differential-functional systems

In this paper, the problems of convergence and superlinear convergence of continuous-time waveform relaxation method applied to Volterra type systems of neutral functional-differential equations are discussed. Under a Lipschitz condition with time- and delay-dependent right-hand side imposed on the so-called splitting function, more suitable conditions about convergence and superlinear convergence of continuous-time WR method are obtained. We also investigate the initial interval acceleration strategy for the practical implementation of the continuous-time waveform relaxation method, i.e., discrete-time waveform relaxation method. It is shown by numerical results that this strategy is efficacious and has the essential acceleration effect for the whole computation process.     

Convergence of discrete time waveform relaxation methods

Numerical Algorithms - This paper concerns the discrete time waveform relaxation (DWR) methods for ordinary differential equations (ODEs). We present a general algorithm of constructing the DWR...     

非线性刚性微分-代数系统的波形松弛离散法

研究基于Runge-Kutta方法的波形松弛离散过程,得到新的刚性微分-代数系统的收敛理论,及该类系统解的存在性和惟一性,并用具体算例测试该理论的有效实用性.     

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.     

Methods for parallel integration of stiff systems of odes

This paper presents a class of parallel numerical integration methods for stiff systems of ordinary differential equations which can be partitioned into loosely coupled sub-systems. The formulas are called decoupled backward differentiation formulas, and they are derived from the classical formulas by restricting the implicit part to the diagnonal sub-system. With one or several sub-systems allocated to each processor, information only has to be exchanged after completion of a step but not during the solution of the nonlinear algebraic equations.The main emphasis is on the formula of order 1, the decoupled implicit Euler formula. It is proved that this formula even for a wide range of multirate formulations has an asymptotic global error expansion permitting extrapolation. Besides, sufficient conditions for absolute stability are presented.     

Discrete-time waveform relaxation Volterra-Runge-Kutta methods: Convergence analysis

The discrete-time relaxation methods based on Volterra-Runge-Kutta methods for solving large system of second-kind Volterra integral equations are proposed. Convergence of the discrete-time iteration process with particular attention to parallel methods is investigated.     

Convergence of relaxation schemes for hyperbolic conservation laws with stiff source terms

We focus in this study on the convergence of a class of relaxation numerical schemes for hyperbolic scalar conservation laws including stiff source terms. Following Jin and Xin, we use as approximation of the scalar conservation law, a semi-linear hyperbolic system with a second stiff source term. This allows us to avoid the use of a Riemann solver in the construction of the numerical schemes. The convergence of the approximate solution toward a weak solution is established in the cases of first and second order accurate MUSCL relaxed methods.

     

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

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

Nonstrictly hyperbolic systems with stiff relaxation terms

In this paper, a zero factor idea is introduced to extend the convergence framework in [G.-Q. Chen, C.D. Levermore, T.-P. Liu, Hyperbolic conservation laws with stiff relaxation terms and entropy, Comm. Pure Appl. Math. 47 (1994) 787-830] for the singular limits of stiff relaxation from general 2×2 hyperbolic conservation systems to nonstrictly hyperbolic systems and an application of this framework on the so-called system of extended traffic flow is obtained.     

GPU-acceleration of waveform relaxation methods for large differential systems

It is the purpose of this paper to provide an acceleration of waveform relaxation (WR) methods for the numerical solution of large systems of ordinary differential equations. The introduced technique is based on the employ of graphics processing units (GPUs) in order to speed-up the numerical integration process. A CUDA solver based on WR-Picard, WR-Jacobi and red-black WR-Gauss-Seidel iterations is presented and some numerical experiments realized on a multi-GPU machine are provided.     

Remarks on the convergence of waveform relaxation method

The paper contains some convergence results in uniform norms for the WR-like iteration method when appHed to a nonlinear stiff system which models MOS circuits. The discretization methods discussed include e.g. the backward differentiation methods of order ≤ 5.     

Convergence of the cyclical relaxation method for linear inequalities

The relaxation method for linear inequalities is studied and new bounds on convergence obtained. An asymptotically tight estimate is given for the case when the inequalities are processed in a cyclical order. An improvement of the estimate by an order of magnitude takes place if strong underrelaxation is used. Bounds on convergence usually involve the so-called condition number of a system of linear inequalities, which we estimate in terms of their coefficient matrix. Paper presented at the XI. International Symposium on Mathematical Programming, Bonn, August 23–27, 1982.     

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.     

High order implicit method for odes stiff systems

This paper presents a new difference scheme for numerical solution of stiff systems of ODE’s. The present study is mainly motivated to develop an absolutely stable numerical method with a high order of approximation. In this work a double implicit A-stable difference scheme with the sixth order of approximation is suggested. Another purpose of this study is to introduce automatic choice of the integration step size of the difference scheme which is derived from the proposed scheme and the one step scheme of the fourth order of approximation. The algorithm was tested by means of solving the Kreiss problem and a chemical kinetics problem. The behavior of the gas explosive mixture (H ₂ + O₂) in a closed space with a mobile piston is considered in test problem 2. It is our conclusion that a hydrogen-operated engine will permit to decrease the emitted levels of hazardous atmospheric pollutants.     

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.     

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.     

Convergence analysis of the parallel multisplitting TOR method

In this paper, we propose the parallel multisplitting TOR method, for solving a large nonsingular systems of linear equations Ax = b. These new methods are a generalization and an improvement of the relaxed parallel multisplitting method (Formmer and Mager, 1989) and parallel multisplitting AOR Algorithm (Wang Deren, 1991). The convergence theorem of this new algorithm is established under the condition that the coefficient matrix A of linear systems is an H-matrix. Some results also yield new convergence theorem for TOR method.     

Remarks on waveform relaxation method with overlapping splittings

By studying the superlinear convergence of waveform relaxation method on finite time intervals, it has formerly been shown, by using the theory of quasinilpotent operators, that the convergence properties are largely determined by the graph properties of the splitting. In this paper, we show how the directed graphs associated to the decomposition are modified when overlapping splittings are used. In particular, we explain how overlapping should be used in order to best accelerate convergence of the iteration method.     

A unsplitting finite volume method for models with stiff relaxation source terms

We developed an unsplitting finite volume scheme to account the delicate nonlinear balance between numerical approximations of the hyperbolic flux function and the source linked to balance laws. The method is Riemann-solver-free and no upwinding technique is used. By means of this new approach, we conducted an analysis for two new models of balance laws linked to compositional and thermal flow in porous media problems, under and without a thermodynamic equilibrium hypothesis. For concreteness, we adopt the nitrogen and steam injection models in a porous media. To this model we found an interesting behavior linked to the relaxation term, which is the existence of a non-monotonic traveling wave. We applied this numerical technique to others well-known differential models with relaxation terms available in the literature. Qualitatively we were able to reproduce the expected results.