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

Parallel two-level Schwarz methods for singularly perturbed elliptic problems

Schwarz domain decomposition methods are developed for the numerical solution of singularly perturbed elliptic problems. Three variants of a two-level Schwarz method with interface subproblems are investigated both theoretically and from the point of view of their computer realization on a distributed memory multiprocessor computer. Numerical experiments illustrate their parallel performance as well as their behavior with respect to the critical parameters such as the perturbation parameter, the size of the interface subdomains and the number of parallel processors. Application of one of the methods to a model problem with an interior layer of complex geometry is also discussed. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions

Summary. Multilevel Schwarz methods are developed for a conforming finite element approximation of second order elliptic problems. We focus on problems in three dimensions with possibly large jumps in the coefficients across the interface separating the subregions. We establish a condition number estimate for the iterative operator, which is independent of the coefficients, and grows at most as the square of the number of levels. We also characterize a class of distributions of the coefficients, called quasi-monotone, for which the weighted -projection is stable and for which we can use the standard piecewise linear functions as a coarse space. In this case, we obtain optimal methods, i.e. bounds which are independent of the number of levels and subregions. We also design and analyze multilevel methods with new coarse spaces given by simple explicit formulas. We consider nonuniform meshes and conclude by an analysis of multilevel iterative substructuring methods. Received April 6, 1994 / Revised version received December 7, 1994     

Schwarz methods of neumann-neumann type for three-dimensional elliptic finite element problems

Several domain decomposition methods of Neumann-Neumann type are considered for solving the large linear systems of algebraic equations that arise from discretizations of elliptic problems by finite elements. We will only consider problems in three dimensions. Several new variants of the basic algorithm are introduced in a Schwarz method framework that provides tools which have already proven very useful in the design and analysis of other domain decomposition and multi-level methods. The Neumann-Neumann algorithms have several advantages over other domain decomposition methods. The subregions, which define the subproblems, only share the boundary degrees of freedom with their neighbors. The subregions can also be of quite arbitrary shape and many of the major components of the preconditioner can be constructed from subprograms available in standard finite element program libraries. In its original form, however, the algorithm lacks a mechanism for global transportation of information and its performance therefore suffers when the number of subregions increases. In the new variants of the algorithms, considered in this paper, the preconditioners include global components, of low rank, to overcome this difficulty. Bounds are established for the condition number of the iteration operator, which are independent of the number of subregions, and depend only polylogarithmically on the number of degrees of freedom of individual local subproblems. Results are also given for problems with arbitrarily large jumps in the coefficients across the interfaces separating the subregions. ©1995 John Wiley & Sons, Inc.     

Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes

We give several additive Schwarz domain decomposition methods for solving finite element problems which arise from the discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Our theory requires no assumption (for the main results) on the substructures which constitute the whole domain, so each substructure can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved and both the coarse meshes and the fine meshes need not be quasi-uniform. In this general setting, our algorithms have the same optimal convergence rate of the usual domain decomposition methods on structured meshes. The condition numbers of the preconditioned systems depend only on the (possibly small) overlap of the substructures and the size of the coares grid, but is independent of the sizes of the subdomains.Revised version on Sept. 20, 1994. Original version: CAM Report 93-40, Dec. 1993, Dept. of Math., UCLA.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and ONR under contract ONR-N00014-92-J-1890.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and subcontract DAAL03-91-C-0047.     

Additive Schwarz methods for the Crouzeix-Raviart mortar finite element for elliptic problems with discontinuous coefficients

In this paper, we propose two variants of the additive Schwarz method for the approximation of second order elliptic boundary value problems with discontinuous coefficients, on nonmatching grids using the lowest order Crouzeix-Raviart element for the discretization in each subdomain. The overall discretization is based on the mortar technique for coupling nonmatching grids. The convergence behavior of the proposed methods is similar to that of their closely related methods for conforming elements. The condition number bound for the preconditioned systems is independent of the jumps of the coefficient, and depend linearly on the ratio between the subdomain size and the mesh size. The performance of the methods is illustrated by some numerical results. This work has been supported by the Alexander von Humboldt Foundation and the special funds for major state basic research projects (973) under 2005CB321701 and the National Science Foundation (NSF) of China (No.10471144) This work has been supported in part by the Bergen Center for Computational Science, University of Bergen     

Erratum to “Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes”

Communicated by C. Brezinski     

Nonstandard coarse spaces and Schwarz methods for elliptic problems with discontinuous coefficients using non-conforming elements

Summary. Two-level domain decomposition methods are developed for a simple nonconforming approximation of second order elliptic problems. A bound is established for the condition number of these iterative methods, that grows only logarithmically with the number of degrees of freedom in each subregion. This bound holds for two and three dimensions and is independent of jumps in the value of the coefficients and number of subregions. We introduce face coarse spaces, and isomorphisms to map between conforming and nonconforming spaces. ReceivedMarch 1, 1995 / Revised version received January 16, 1996     

On linear monotone iteration and Schwarz methods for nonlinear elliptic PDEs

Summary The Schwarz Alternating Method can be used to solve elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence of elliptic boundary value problems in each subdomain. In this paper, proofs of convergence of some Schwarz Alternating Methods for nonlinear elliptic problems which are known to have solutions by the monotone method (also known as the method of subsolutions and supersolutions) are given. In particular, an additive Schwarz method for scalar as well some coupled nonlinear PDEs are shown to converge to some solution on finitely many subdomains, even when multiple solutions are possible. In the coupled system case, each subdomain PDE is linear, decoupled and can be solved concurrently with other subdomain PDEs. These results are applicable to several models in population biology. This work was in part supported by a grant from the RGC of HKSAR, China (HKUST6171/99P)     

On the Meany inequality with applications to convergence analysis of several row-action iteration methods

The Meany inequality gives an upper bound in the Euclidean norm for a product of rank-one projection matrices. In this paper we further derive a lower bound related to this inequality. We discuss the internal relationship between the upper bounds given by the Meany inequality and by the inequality in Smith et al. (Bull Am Math Soc 83:1227–1270, 1977) in the finite dimensional real linear space. We also generalize the Meany inequality to the block case. In addition, by making use of the block Meany inequality, we improve existing results and establish new convergence theorems for row-action iteration schemes such as the block Kaczmarz and the Householder–Bauer methods used to solve large linear systems and least-squares problems.     

General convergence analysis for two-step projection methods and applications to variational problems

First a general model for two-step projection methods is introduced and second it has been applied to the approximation solvability of a system of nonlinear variational inequality problems in a Hilbert space setting. Let $H$ be a real Hilbert space and $K$ be a nonempty closed convex subset of $H$. For arbitrarily chosen initial points $x^0,y^0\in K$, compute sequences $\left\{x^k\right\}$ and $\left\{y^k\right\}$ such that $x^{k+1}=(1-a^k)x^k+a^k{P}_K[y^k-\rho T\left(y^k\right)]\text{for }\rho >0$$y^k=(1-b^k)x^k+b^k{P}_K[x^k-\eta T\left(x^k\right)]\text{for }\eta >0\text{,}$ where $T:K\to H$ is a nonlinear mapping on $K,P_K$ is the projection of $H$ onto $K$, and $0\le a^k,b^k\le 1$. The two-step model is applied to some variational inequality problems.     

On the convergence of quasi-newton methods for nonsmooth problems

We develop a theory of quasi-New ton and least-change update methods for solving systems of nonlinear equations F(x) = 0. In this theory, no differentiability conditions are necessary. Instead, we assume that Fcan be approximated, in a weak sense, by an affine function in a neighborhood of a solution. Using this assumption, we prove local and ideal convergence. Our theory can be applied to B-differentiable functions and to partially differentiable functions.     

Finite element methods and their convergence for elliptic and parabolic interface problems

In this paper, we consider the finite element methods for solving second order elliptic and parabolic interface problems in two-dimensional convex polygonal domains. Nearly the same optimal -norm and energy-norm error estimates as for regular problems are obtained when the interfaces are of arbitrary shape but are smooth, though the regularities of the solutions are low on the whole domain. The assumptions on the finite element triangulation are reasonable and practical. Received July 7, 1996 / Revised version received March 3, 1997     

Explicit forms of the Schwarz integral with applications for inverse boundary-value problems

We obtain new explicit forms of the Schwarz integral in the unit circle. By means of superpositions of logarithms we establish criteria for the appearance of singular boundary points and circles in inverse boundary-value problems.     

On the convergence of an inverse iteration method for nonlinear elliptic eigenvalue problems

Summary In recent years, a group of inverse iteration type algorithms have been developed for solving nonlinear elliptic eigenvalue problems in plasma physics [4]. Although these algorithms have been very successful in practice, no satisfactory theoretical justification of convergence has been available. The present paper fills this gap and proves for a large class of such problems and a simple version of such algorithms that linear convergence to a local maximum of a certain potential is obtained.This work was supported by the Deutsche Forschungsgemeinschaft, SFB 72 an der Universität Bonn     

Non-differentiable functionals and applications to elliptic problems with discontinuous nonlinearities

Multiple critical points theorems for non-differentiable functionals are established. Applications both to elliptic variational-hemivariational inequalities and eigenvalue problems with discontinuous nonlinearities are then presented.     

On the convergence of inexact augmented Lagrangian methods for problems with convex constraints

We consider the augmented Lagrangian method (ALM) for constrained optimization problems in the presence of convex inequality and convex abstract constraints. We focus on the case where the Lagrangian sub-problems are solved up to approximate stationary points, with increasing accuracy. We analyze two different criteria of approximate stationarity for the sub-problems and we prove the global convergence to stationary points of ALM in both cases.     

On convergence of iterative methods for maximal correlation problems

Several iterative methods for maximal correlation problems (MCPs) have been proposed in the literature. This paper deals with the convergence of these iterations and contains three contributions. Firstly, a unified and concise proof of the monotone convergence of these iterative methods is presented. Secondly, a starting point strategy is analysed. Thirdly, some error estimates are presented to test the quality of a computed solution. Both theoretical results and numerical tests suggest that combining with this starting point strategy these methods converge rapidly and are more likely converging to a global maximizer of MCP. Copyright © 2016 John Wiley & Sons, Ltd.