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     

Additive Schwarz algorithms for the p version of the Galerkin boundary element method

Summary. We study some additive Schwarz algorithms for the version Galerkin boundary element method applied to some weakly singular and hypersingular integral equations of the first kind. Both non-overlapping and overlapping methods are considered. We prove that the condition numbers of the additive Schwarz operators grow at most as independently of h, where p is the degree of the polynomials used in the Galerkin boundary element schemes and h is the mesh size. Thus we show that additive Schwarz methods, which were originally designed for finite element discretisation of differential equations, are also efficient preconditioners for some boundary integral operators, which are non-local operators. Received June 15, 1997 / Revised version received July 7, 1998 / Published online February 17, 2000     

Multilevel Schwarz methods

Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.This work was supported in part by the National Science Foundation under Grants NSF-CCR-8903003 at Courant Institute of Mathematical Sciences, New York University and NSF-ASC-8958544 at Department of Computer Science, University of Maryland.     

带非线性源项的变分不等式的区域分解法及其收敛速度分析

本文考虑一类带非线性源项的变化不等式。针对其有限元离散问题,我们构造了乘性与加性Ｓｃｈｗａｒｚ算法,其产生的上解序列或下解序列不仅单调收敛于有限元解,而且具有限元网格ｈ无关的收敛率．     

Multigrid in H (div) and H (curl)

Summary. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces and in three dimensions. We show that if appropriate finite element spaces and appropriate additive or multiplicative Schwarz smoothers are used, then the multigrid V-cycle is an efficient solver and preconditioner for the discrete operator. All results are uniform with respect to the mesh size, the number of mesh levels, and weights on the two terms in the inner products. Received June 12, 1998 / Revised version received March 12, 1999 / Published online January 27, 2000     

Schur complements on Hilbert spaces and saddle point systems

For any continuous bilinear form defined on a pair of Hilbert spaces satisfying the compatibility Ladyshenskaya–Babušca–Brezzi condition, symmetric Schur complement operators can be defined on each of the two Hilbert spaces. In this paper, we find bounds for the spectrum of the Schur operators only in terms of the compatibility and continuity constants. In light of the new spectral results for the Schur complements, we review the classical Babušca–Brezzi theory, find sharp stability estimates, and improve a convergence result for the inexact Uzawa algorithm. We prove that for any symmetric saddle point problem, the inexact Uzawa algorithm converges, provided that the inexact process for inverting the residual at each step has the relative error smaller than 1/3. As a consequence, we provide a new type of algorithm for discretizing saddle point problems, which combines the inexact Uzawa iterations with standard a posteriori error analysis and does not require the discrete stability conditions.     

Multilevel additive and multiplicative methods for orthogonal spline collocation problems

Summary. Multilevel preconditioners are proposed for the iterative solution of the discrete problems which arise when orthogonal spline collocation with piecewise Hermite bicubics is applied to the Dirichlet boundary value problem for a self-adjoint elliptic partial differential equation on a rectangle. Additive and multiplicative preconditioners are defined respectively as sums and products of independent operators on a sequence of nested subspaces of the fine partition approximation space. A general theory of additive and multiplicative Schwarz methods is used to prove that the preconditioners are spectrally equivalent to the collocation discretization of the Laplacian with the spectral constants independent of the fine partition stepsize and the number of levels. The preconditioned conjugate gradient and preconditioned Orthomin methods are considered for the solution of collocation problems. An implementation of the methods is discussed and the results of numerical experiments are presented. Received March 1, 1994 / Revised version received January 23, 1996     

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.

     

Additive Schwarz methods for thep-version finite element method

Summary In this paper, we study some additive Schwarz methods (ASM) for thep-version finite element method. We consider linear, scalar, self adjoint, second order elliptic problems and quadrilateral elements in the finite element discretization. We prove a constant bound independent of the degreep and the number of subdomainsN, for the condition number of the ASM iteration operator. This optimal result is obtained first in dimension two. It is then generalized to dimensionn and to a variant of the method on the interface. Numerical experiments confirming these results are reported. As is the case for other additive Schwarz methods, our algorithms are highly parallel and scalable.This work was supported in part by the Applied Math. Sci. Program of the U.S. Department of Energy under contract DE-FG02-88ER25053 and, in part, by the National Science Foundation under Grant NSF-CCR-9204255     

Two-level preconditioners for regularized inverse problems I: Theory

Summary. We compare additive and multiplicative Schwarz preconditioners for the iterative solution of regularized linear inverse problems, extending and complementing earlier results of Hackbusch, King, and Rieder. Our main findings are that the classical convergence estimates are not useful in this context: rather, we observe that for regularized ill-posed problems with relevant parameter values the additive Schwarz preconditioner significantly increases the condition number. On the other hand, the multiplicative version greatly improves conditioning, much beyond the existing theoretical worst-case bounds. We present a theoretical analysis to support these results, and include a brief numerical example. More numerical examples with real applications will be given elsewhere. Received May 28, 1998 / Published online: July 7, 1999     

Multilevel iterative methods for mixed finite element discretizations of elliptic problems

Summary For solving second order elliptic problems discretized on a sequence of nested mixed finite element spaces nearly optimal iterative methods are proposed. The methods are within the general framework of the product (multiplicative) scheme for operators in a Hilbert space, proposed recently by Bramble, Pasciak, Wang, and Xu [5,6,26,27] and make use of certain multilevel decomposition of the corresponding spaces for the flux variable.     

On the convergence of generalized Schwarz algorithms for solving obstacle problems with elliptic operators

In this paper, multiplicative and additive generalized Schwarz algorithms for solving obstacle problems with elliptic operators are developed and analyzed. Compared with the classical Schwarz algorithms, in which the subproblems are coupled by the Dirichlet boundary conditions, the generalized Schwarz algorithms use Robin conditions with parameters as the transmission conditions on the interface boundaries. As a result, the convergence rate can be speeded up by choosing Robin parameters properly. Convergence of the algorithms is established. This work was supported by 973 national project of China (2004CB719402) and by national nature science foundation of China (10671060).     

Comparisons between multiplicative and additive Schwarz iterations in domain decomposition methods

We consider the multiplicative and additive Schwarz methods for solving linear systems of equations and we compare their asymptotic rate of convergence. Moreover, we compare the multiplicative Schwarz method with the weighted restricted additive Schwarz method. We prove that the multiplicative Schwarz method is the fastest method among these three. Our comparisons can be done in the case of exact and inexact subspaces solves. In addition, we analyse two ways of adding a coarse grid correction – multiplicatively or additively. Mathematics Subject Classification (1991):65F10, 65F35, 65M55     

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     

Second-order methods for some quasivariational inequalities

For quasivariational inequalities of special form in a Hilbert space, we construct a continuous second-order method and a discrete version of this method, prove the strong convergence of these methods, and indicate the possibility of obtaining estimates for the convergence rate. We separately study the convergence of the continuous method under the assumption that the operators describing the quasivariational inequality to be solved are potential. We establish sufficient conditions for the unique solvability of the nonlinear problems determining these methods.     

A New Approach to Source Conditions in Regularization with General Residual Term

This article addresses Tikhonov-like regularization methods with convex penalty functionals for solving nonlinear ill-posed operator equations formulated in Banach or, more general, topological spaces. We present an approach for proving convergence rates that combines advantages of approximate source conditions and variational inequalities. Precisely, our technique provides both a wide range of convergence rates and the capability to handle general and not necessarily convex residual terms as well as nonsmooth operators. Initially formulated for topological spaces, the approach is extensively discussed for Banach and Hilbert space situations, showing that it generalizes some well-known convergence rates results.     

Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part II: Convergence theory

Summary In this paper we discuss bounds for the convergence rates of several domain decomposition algorithms to solve symmetric, indefinite linear systems arising from mixed finite element discretizations of elliptic problems. The algorithms include Schwarz methods and iterative refinement methods on locally refined grids. The implementation of Schwarz and iterative refinement algorithms have been discussed in part I. A discussion on the stability of mixed discretizations on locally refined grids is included and quantiative estimates for the convergence rates of some iterative refinement algorithms are also derived.Department of Mathematics, University of Wyoming, Laramie, WY 82071-3036. This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by NSF Grant ASC 9003002, while the author was a Visiting, Assistant Researcher at UCLA.     

An iterative substructuring method for the p-version of the boundary element method for hypersingular integral operators in three dimensions

Summary. We study preconditioners for the -version of the boundary element method for hypersingular integral equations in three dimensions. The preconditioners are based on iterative substructuring of the underlying ansatz spaces which are constructed by using discretely harmonic basis functions. We consider a so-called wire basket preconditioner and a non-overlapping additive Schwarz method based on the complete natural splitting, i.e. with respect to the nodal, edge and interior functions, as well as an almost diagonal preconditioner. In any case we add the space of piecewise bilinear functions which eliminate the dependence of the condition numbers on the mesh size. For all these methods we prove that the resulting condition numbers are bounded by . Here, is the polynomial degree of the ansatz functions and is a constant which is independent of and the mesh size of the underlying boundary element mesh. Numerical experiments supporting these results are reported. Received July 8, 1996 / Revised version received January 8, 1997     

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.     

New extragradient methods for solving variational inequality problems and fixed point problems

In this paper, we introduce two new iterative algorithms for finding a common element of the set of fixed points of a quasi-nonexpansive mapping and the set of solutions of the variational inequality problem with a monotone and Lipschitz continuous mapping in real Hilbert spaces, by combining a modified Tseng’s extragradient scheme with the Mann approximation method. We prove weak and strong convergence theorems for the sequences generated by these iterative algorithms. The main advantages of our algorithms are that the construction of solution approximations and the proof of convergence of the algorithms are performed without the prior knowledge of the Lipschitz constant of cost operators. Finally, we provide numerical experiments to show the efficiency and advantage of the proposed algorithms.