Multigrid Waveform Relaxation for Anisotropic Partial Differential Equations

Multigrid waveform relaxation provides fast iterative methods for the solution of time-dependent partial differential equations. In this paper we consider anisotropic problems and extend multigrid methods developed for the stationary elliptic case to waveform relaxation methods for the time-dependent parabolic case. We study line-relaxation, semicoarsening and multiple semicoarsening multilevel methods. A two-grid Fourier–Laplace analysis is used to estimate the convergence of these methods for the rotated anisotropic diffusion equation. We treat both continuous time and discrete time algorithms. The results of the analysis are confirmed by numerical experiments.     

Approximation and numerical realization of an optimal design welding problem

In this article, we deal with the approximation of an optimal shape design approach for a free boundary problem modeling a welding process. We consider discretization of this problem based on linear finite elements. We prove the existence of discrete optimal solutions. This allows us to show the convergence result of a sequence of discrete solutions to the continuous one. Finally, methods for numerical realization are described and several examples have been carried out to illustrate the efficiency of the proposed approach. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

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...     

Relaxation of Minimax Optimal Control Problems with Infinite Horizon

A minimax optimal control problem with infinite horizon is studied. We analyze a relaxation of the controls, which allows us to consider a generalization of the original problem that not only has existence of an optimal control but also enables us to approximate the infinite-horizon problem with a sequence of finite-horizon problems. We give a set of conditions that are sufficient to solve directly, without relaxation, the infinite-horizon problem as the limit of finite-horizon problems.     

Stability and robustness of collocation methods for Abel-type integral equations

Summary We study stability aspects of collocation methods for Abel-type integral equations of the first kind using piecewise polynomials. These collocation methods may be formulated as projection methods. Stability is defined as the boundedness of the sequence of projectors in their natural setting. Robustness is essentially the optimal asymptotic insensitivity to perturbations in the data. We show that stability and robustness are equivalent for the above collocation methods. This allows us to obtain optimal error estimates for some methods that are well-known to be robust. We also present numerical results for some methods which appear to be robust.Research supported in part by the United States Army under Contract No. DAAG 29-83-K-0109     

波形松弛算法及其在计算流体力学中的应用

本文介绍求解线性常系数微分代数方程组的波形松弛算法, 基于Laplace积分变换得到该算法新的收敛理论. 进一步将波形松弛算法应用于求解非定常Stokes方程, 介绍并讨论了连续时间波形松弛算法CABSOR算法和离散时间波形松弛算法DABSOR算法.     

Hybrid finite element methods for the Signorini problem

We study three mixed linear finite element methods for the numerical simulation of the two-dimensional Signorini problem. Applying Falk's Lemma and saddle point theory to the resulting discrete mixed variational inequality allows us to state the convergence rate of each of them. Two of these finite elements provide optimal results under reasonable regularity assumptions on the Signorini solution, and the numerical investigation shows that the third method also provides optimal accuracy.

     

WAVEFORM RELAXATION METHODS OF NONLINEAR INTEGRAL-DIFFERENTIAL-ALGEBRAIC EQUATIONS

In this paper we consider continuous-time and discrete-time waveform relaxation meth-ods for general nonlinear integral-differential-algebraic equations. For the continuous-time case we derive the convergence condition of the iterative methods by invoking the spec-tral theory on the resulting iterative operators. By use of the implicit difference forms,namely the backward-differentiation formulae, we also yield the convergence condition of the discrete waveforms. Numerical experiments are provided to illustrate the theoretical work reported here.     

一类求解反应扩散方程的Newton波形松弛方法

对反应扩散方程提出一种新型的Newton波形松弛方法,并给出此方法的误差估计式.通过与传统的波形松弛方法比较,这种Newton波形松弛方法有更快的收敛性,且收敛速度不随网格加密而减慢.这种方法可以保持传统波形松弛方法可并行的特点.最后通过数值算例验证这种方法的有效性.     

ON THE CONVERGENCE OF WAVEFORM RELAXATION METHODS FOR LINEAR INITIAL VALUE PROBLEMS

We study a class of blockwise waveform relaxation methods,and investigate its con-vergence properties in both asymptotic and monotone senses.In addition,the monotoneconvergence rates between different pointwise/blockwise waveform relaxation methods re-sulted from different matrix splittings,and those between the pointwise and blockwisewaveform relaxation methods are discussed in depth.     

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

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

线性随机微分方程的离散波形松弛方法的几乎必然收敛性

提出了随机微分方程的离散型波形松弛方法,证明了它是几乎必然收敛的.此外,通过数值实验验证了所得结果.     

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.     

带松弛因子的Schwarz交替方法

§1.引言 Schwarz交替方法的收敛速度,依赖于子区域重迭部分的大小,重迭部分越大,收敛越快。然而重迭部分增大,必将引起计算量的增大,因此,在重迭部分不变的情况下,如何改善Schwarz交替过程的收敛速度,已成为人们感兴趣的问题。关于Schwarz算法收敛速度的讨论,许多文章都是对具体类型的微分方程展开的。     

Negative norm least‐squares methods for the velocity‐vorticity‐pressure Navier–Stokes equations

We develop and analyze a least‐squares finite element method for the steady state, incompressible Navier–Stokes equations, written as a first‐order system involving vorticity as new dependent variable. In contrast to standard L² least‐squares methods for this system, our approach utilizes discrete negative norms in the least‐squares functional. This allows us to devise efficient preconditioners for the discrete equations, and to establish optimal error estimates under relaxed regularity assumptions. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 237–256, 1999     

A combinatorial property of the maximum round robin tournament problem

We prove a new combinatorial property of the maximum round robin tournament (MRRT) problem. This property allows us to answer negatively the question of Briskorn, whether the optimal objective value of the MRRT problem and that of its conventional linear relaxation always coincide.     

Optimal Stopping Time Formulation of Adaptive Image Filtering

This paper presents an approach to image filtering based on an optimal stopping time problem for the evolution equation describing the filtering kernel. This approach allows us to obtain easily an adaptivity of the filter with respect to the noise level. Well-posedness of the problem and convergence of fully discrete approximations are proved and numerical examples are presented and discussed. Accepted 25 October 2000. Online publication 9 April 2001.     

Discrete location for bundled demand points

This paper considers a discrete location problem where the demand points are grouped. We propose a formulation, an enforcement for it, and an associated Lagrangian relaxation, and then we build feasible solutions to the problem from the optimal solutions to the relaxed subproblems. Valid inequalities for the formulation are also identified and added to the set of relaxed constraints. This method produces good feasible solutions and enables us to address large instances of the problem. Computational experiments have been performed with benchmark instances from the literature on related problems.     

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.

     

Mixed methods with dynamic finite-element spaces for miscible displacement in porous media

Miscible displacement in porous media is modeled by a nonlinear coupled system of two partial differential equations. We approximate the pressure equation, which is elliptic, and the concentration equation, which is parabolic but normally convection-dominated, by the mixed methods with dynamic finite-element spaces, i.e., different number of elements and different basis functions are adopted at different time levels; and the approximate concentration is projected onto the next finite-element space in weighted L²-norm for starting a new time step. This allows us to make local grid refinements or unrefinements and basis function improvements. Two fully discrete schemes are presented and analysed. Error estimates show that these methods have optimal convergent rate in some sense. The efficiency and capability of the dynamic finite-element method are commented for accurately solving time-dependent problems with localized phenomena, such as fronts, shocks, and boundary layers.