An additive Schwarz method for variational inequalities

This paper proposes an additive Schwarz method for variational inequalities and their approximations by finite element methods. The Schwarz domain decomposition method is proved to converge with a geometric rate depending on the decomposition of the domain. The result is based on an abstract framework of convergence analysis established for general variational inequalities in Hilbert spaces.

     

Squared polynomial extrapolation methods with cycling: an application to the positron emission tomography problem

Roland and Varadhan (Appl. Numer. Math., 55:215–226, 2005) presented a new idea called “squaring” to improve the convergence of Lemaréchal’s scheme for solving nonlinear fixed-point problems. Varadhan and Roland (Squared extrapolation methods: A new class of simple and efficient numerical schemes for accelerating the convergence of the EM algorithm, Department of Biostatistics Working Paper. Johns Hopkins University, , 2004) noted that Lemaréchal’s scheme can be viewed as a member of the class of polynomial extrapolation methods with cycling that uses two fixed-point iterations per cycle. Here we combine these two ideas, cycled extrapolation and squaring, and construct a new class of methods, called squared polynomial methods (SQUAREM), for accelerating the convergence of fixed-point iterations. Our main goal is to evaluate whether the squaring device is effective in improving the rate of convergence of cycled extrapolation methods that use more than two fixed-point iterations per cycle. We study the behavior of the new schemes on an image reconstruction problem for positron emission tomography (PET) using simulated data. Our numerical experiments show the effectiveness of first- and higher-order squared polynomial extrapolation methods in accelerating image reconstruction, and also their relative superiority compared to the classical, “unsquared” vector polynomial methods.     

On the geometric convergence of optimized Schwarz methods with applications to elliptic problems

The Schwarz method can be used for the iterative solution of elliptic boundary value problems on a large domain Ω. One subdivides Ω into smaller, more manageable, subdomains and solves the differential equation in these subdomains using appropriate boundary conditions. Optimized Schwarz Methods use Robin conditions on the artificial interfaces for information exchange at each iteration, and for which one can optimize the Robin parameters. While the convergence theory of classical Schwarz methods (with Dirichlet conditions on the artificial interface) is well understood, the overlapping Optimized Schwarz Methods still lack a complete theory. In this paper, an abstract Hilbert space version of the Optimized Schwarz Method (OSM) is presented, together with an analysis of conditions for its geometric convergence. It is also shown that if the overlap is relatively uniform, these convergence conditions are met for Optimized Schwarz Methods for two-dimensional elliptic problems, for any positive Robin parameter. In the discrete setting, we obtain that the convergence factor ρ(h) varies like a polylogarithm of h. Numerical experiments show that the methods work well and that the convergence factor does not appear to depend on h.     

Convergence estimates for an optimized Schwarz method for PDEs with discontinuous coefficients

Optimized Schwarz methods form a class of domain decomposition methods for the solution of elliptic partial differential equations. When the subdomains are overlapping or nonoverlapping, these methods employ the optimal value of parameter(s) in the boundary condition along the artificial interface to accelerate its convergence. In the literature, the analysis of optimized Schwarz methods rely mostly on Fourier analysis and so the domains are restricted to be regular (rectangular). As in earlier papers, the interface operator can be expressed in terms of Poincaré–Steklov operators. This enables the derivation of an upper bound for the spectral radius of the interface operator on essentially arbitrary geometry. The problem of interest here is a PDE with a discontinuous coefficient across the artificial interface. We derive convergence estimates when the mesh size h along the interface is small and the jump in the coefficient may be large. We consider two different types of Robin transmission conditions in the Schwarz iteration: the first one leads to the best estimate when h is small, whereas for the second type, we derive a convergence estimate inversely proportional to the jump in the coefficient. This latter result improves upon the rate of popular domain decomposition methods such as the Neumann–Neumann method or FETI-DP methods, which was shown to be independent of the jump. In memory of Gene Golub.     

A new class of asynchronous iterative algorithms with order intervals

This paper deals with a new class of parallel asynchronous iterative algorithms for the solution of nonlinear systems of equations. The main feature of the new class of methods presented here is the possibility of flexible communication between processors. In particular partial updates can be exchanged. Approximation of the associated fixed point mapping is also considered. A detailed convergence study is presented. A connection with the Schwarz alternating method is made for the solution of nonlinear boundary value problems. Computational results on a shared memory multiprocessor IBM 3090 are briefly presented.

     

On the performance of the algebraic optimized Schwarz methods with applications

We investigate the performance of algebraic optimized Schwarz methods used as preconditioners for the solution of discretized differential equations. These methods consist on modifying the so-called transmission blocks. The transmission blocks are replaced by new blocks in order to improve the convergence of the corresponding iterative algorithms. In the optimal case, convergence in two iterations can be achieved. We are also interested in the behavior of the algebraic optimized Schwarz methods with respect to changes in the problems parameters. We focus on constructing preconditioners for different numerically challenging differential problems such as: Periodic and Torus problems; Meshfree problems; Three-dimensional problems. We present different numerical simulations corresponding to different type of problems in two- and three-dimensions.     

On the abstract theory of additive and multiplicative Schwarz algorithms

Summary. In recent years, it has been shown that many modern iterative algorithms (multigrid schemes, multilevel preconditioners, domain decomposition methods etc.) for solving problems resulting from the discretization of PDEs can be interpreted as additive (Jacobi-like) or multiplicative (Gauss-Seidel-like) subspace correction methods. The key to their analysis is the study of certain metric properties of the underlying splitting of the discretization space into a sum of subspaces and the splitting of the variational problem on into auxiliary problems on these subspaces. In this paper, we propose a modification of the abstract convergence theory of the additive and multiplicative Schwarz methods, that makes the relation to traditional iteration methods more explicit. The analysis of the additive and multiplicative Schwarz iterations can be carried out in almost the same spirit as in the traditional block-matrix situation, making convergence proofs of multilevel and domain decomposition methods clearer, or, at least, more classical. In addition, we present a new bound for the convergence rate of the appropriately scaled multiplicative Schwarz method directly in terms of the condition number of the corresponding additive Schwarz operator. These results may be viewed as an appendix to the recent surveys [X], [Ys]. Received February 1, 1994 / Revised version received August 1, 1994     

Fourier analysis of schwarz alternating methods for piecewise hermite bicubic orthogonal spline collocation

The rates of convergence of two Schwarz alternating methods are analyzed for the iterative solution of a discrete problem which arises when orthogonal spline collocation with piecewise Hermite bicubics is applied to the Dirichlet problem for Poisson's equation on a rectangle. In the first method, the rectangle is divided into two overlapping subrectangles, while three overlapping subrectangles are used in the second method. Fourier analysis is used to obtain explicit formulas for the convergence factors by which theH ¹-norm of the errors is reduced in one iteration of the Schwarz methods. It is shown numerically that while these factors depend on the size of overlap, they are independent of the partition stepsize. Results of numerical experiments are presented which confirm the established rates of convergence of the Schwarz methods.This research was supported in part by funds from the National Science Foundation grant CCR-9103451.     

Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

自适应间断Galerkin 有限元的多水平方法

本文讨论在自适应网格上间断Galerkin 有限元离散系统的局部多水平算法. 对于光滑系数和间断系数情形, 利用Schwarz 理论分析了算法的收敛性. 理论和数值试验均说明算法的收敛率与网格层数以及网格尺寸无关. 对强间断系数情形算法是拟最优的, 即收敛率仅与网格层数有关.     

A comparison of some domain decomposition and ILU preconditioned iterative methods for nonsymmetric elliptic problems

In recent years, competitive domain-decomposed preconditioned iterative techniques of Krylov-Schwarz type have been developed for nonsymmetric linear elliptic systems. Such systems arise when convection-diffusion-reaction problems from computational fluid dynamics or heat and mass transfer are linearized for iterative solution. Through domain decomposition, a large problem is divided into many smaller problems whose requirements for coordination can be controlled to allow effective solution on parallel machines. A central question is how to choose these small problems and how to arrange the order of their solution. Different specifications of decomposition and solution order lead to a plethora of algorithms possessing complementary advantages and disadvantages. In this report we compare several methods, including the additive Schwarz algorithm, the classical multiplicative Schwarz algorithm, an accelerated multiplicative Schwarz algorithm, the tile algorithm, the CGK algorithm, the CSPD algorithm, and also the popular global ILU-family of preconditioners, on some nonsymmetric or indefinite elliptic model problems discretized by finite difference methods. The preconditioned problems are solved by the unrestarted GMRES method. A version of the accelerated multiplicative Schwarz method is a consistently good performer.     

Semismooth Newton Schwarz iterative methods for the linear complementarity problem

Semismooth Newton method is an effective method for solving a nonsmooth equation, which arises from a reformulation of the complementarity problem. Under appropriate conditions, we verify the monotone convergence of the method. We also present semismooth Newton Schwarz iterative methods for the nonsmooth equation. Under suitable conditions, the methods exhibit monotone and superlinear convergence properties.     

关于Schwarz交替法的拟边界松弛方法

§1.松弛方法 我们讨论二阶自共轭椭圆型方程的Dirichlet问题.设Ω?R~2为一多边形区域. a(u,v)=(f,v),v∈H_0~1(Ω),f∈H~(-1)(Ω), u∈H_0~1(Ω)是定义在其上的边值问题的变分形式,这里取齐次边界条件仅为叙述问题方便.双线性型a(·,·)满足:     

基于半平面上自然边界归化的无界区域上的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 convergence theory of multilevel additive Schwarz methods on unstructured meshes

We develop a convergence theory for two level and multilevel additive Schwarz domain decomposition methods for elliptic and parabolic problems on general unstructured meshes in two and three dimensions. The coarse and fine grids are assumed only to be shape regular, and the domains formed by the coarse and fine grids need not be identical. In this general setting, our convergence theory leads to completely local bounds for the condition numbers of two level additive Schwarz methods, which imply that these condition numbers are optimal, or independent of fine and coarse mesh sizes and subdomain sizes if the overlap amount of a subdomain with its neighbors varies proportionally to the subdomain size. In particular, we will show that additive Schwarz algorithms are still very efficient for nonselfadjoint parabolic problems with only symmetric, positive definite solvers both for local subproblems and for the global coarse problem. These conclusions for elliptic and parabolic problems improve our earlier results in [12, 15, 16]. Finally, the convergence theory is applied to multilevel additive Schwarz algorithms. Under some very weak assumptions on the fine mesh and coarser meshes, e.g., no requirements on the relation between neighboring coarse level meshes, we are able to derive a condition number bound of the orderO(² L ²), where = max₁lL(h _l +_l– 1)/ _l,h _l is the element size of thelth level mesh, _l the overlap of subdomains on thelth level mesh, andL the number of mesh levels.The work was partially supported by the NSF under contract ASC 92-01266, and ONR under contract ONR-N00014-92-J-1890. The second author was also partially supported by HKRGC grants no. CUHK 316/94E and the Direct Grant of CUHK.     

指标-2微分-代数系统的连续扩展Runge-Kutta迭代方法

1引言微分-代数系统包括具有约束条件的微分方程和奇异隐式微分方程,在实际应用中,如:约束力学系统、流体动力学、化学反应动力学、电子网络模拟、控制工程和机器人技术等领域就产生了诸多问题需要求解．近年来,微分-代数系统已极大地引起了许多工程师和数学工作者的关注,开展了众多相关问题的探讨,提出了许多新的算法理论[1-3]．在本文中我们对指标-2的微分-代数方程利用Runge-Kutta方法进行时间的离散和动力学迭代,研究离散迭代系统的收敛性．     

A Survey of Algebraic Multilevel Iteration (AMLI) Methods

For the solution by preconditioned conjugate gradient methods of symmetric positive definite equations as arising in boundary value problems we consider preconditioning methods of AMLI type. Particular attention is devoted to providing methods of optimal order of computational complexity which in addition promise to be robust, i.e. with a convergence rate which is bounded above independently of size of discretization parameter h, jumps in problem coefficients, and shape of finite elements or, equivalently, anisotropy of problem coefficients. In addition, the computational cost per iteration step must have optimal order.New results on upper bounds of one of the important parameters in the methods, the Cauchy—Bunyakowski—Schwarz constant are given and an algebraic method how to improve its value is presented.This revised version was published online in October 2005 with corrections to the Cover Date.     

线性块SOR二级迭代法的收敛性质

内迭代次数充分大时,求解非奇异线性方程组的块SOR二级迭代法与经典的块SOR方法有相同的收敛性和大致相等的收敛速度.因此,用于块SOR方法有效的松弛因子,同样可有效地用于块SOR二级迭代法.     

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.     

Convergence of Three-Step Taylor Galerkin Finite Element Scheme Based Monotone Schwarz Iterative Method for Singularly Perturbed Differential-Difference Equation

Monotone Schwarz iterative methods for parabolic partial differential equations are well known for their advantage of eliminating the search for an initial solution. In this article, we propose a monotone Schwarz iterative method for singularly perturbed parabolic retarded differential-difference equations based on a three-step Taylor Galerkin finite element scheme. The stability and ε-uniform convergence of the three-step Taylor Galerkin finite element method have been discussed. Further, by using maximum principle and induction hypothesis, the convergence of the proposed monotone Schwarz iterative method has been established.