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     

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)     

Domain decomposition for multiscale PDEs

We consider additive Schwarz domain decomposition preconditioners for piecewise linear finite element approximations of elliptic PDEs with highly variable coefficients. In contrast to standard analyses, we do not assume that the coefficients can be resolved by a coarse mesh. This situation arises often in practice, for example in the computation of flows in heterogeneous porous media, in both the deterministic and (Monte–Carlo simulated) stochastic cases. We consider preconditioners which combine local solves on general overlapping subdomains together with a global solve on a general coarse space of functions on a coarse grid. We perform a new analysis of the preconditioned matrix, which shows rather explicitly how its condition number depends on the variable coefficient in the PDE as well as on the coarse mesh and overlap parameters. The classical estimates for this preconditioner with linear coarsening guarantee good conditioning only when the coefficient varies mildly inside the coarse grid elements. By contrast, our new results show that, with a good choice of subdomains and coarse space basis functions, the preconditioner can still be robust even for large coefficient variation inside domains, when the classical method fails to be robust. In particular our estimates prove very precisely the previously made empirical observation that the use of low-energy coarse spaces can lead to robust preconditioners. We go on to consider coarse spaces constructed from multiscale finite elements and prove that preconditioners using this type of coarsening lead to robust preconditioners for a variety of binary (i.e., two-scale) media model problems. Moreover numerical experiments show that the new preconditioner has greatly improved performance over standard preconditioners even in the random coefficient case. We show also how the analysis extends in a straightforward way to multiplicative versions of the Schwarz method. We would like to thank Bill McLean for very useful discussions concerning this work. We would also like to thank Maksymilian Dryja for helping us to improve the result in Theorem 4.3.     

Two-level additive Schwarz preconditioners for C 0 interior penalty methods

We study two-level additive Schwarz preconditioners that can be used in the iterative solution of the discrete problems resulting from C⁰ interior penalty methods for fourth order elliptic boundary value problems. We show that the condition number of the preconditioned system is bounded by C(1+(H³/δ³)), where H is the typical diameter of a subdomain, δ measures the overlap among the subdomains and the positive constant C is independent of the mesh sizes and the number of subdomains. This work was supported in part by the National Science Foundation under Grant No. DMS-03-11790.     

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     

Convergence estimates for an higher order optimized Schwarz method for domains with an arbitrary interface

Optimized Schwarz methods form a class of domain decomposition methods for the solution of elliptic partial differential equations. Optimized Schwarz methods employ a first or higher order boundary condition along the artificial interface to accelerate convergence. In the literature, the analysis of optimized Schwarz methods relies on Fourier analysis and so the domains are restricted to be regular (rectangular). In this paper, we express the interface operator of an optimized Schwarz method in terms of Poincare-Steklov operators. This enables us to derive an upper bound of the spectral radius of the operator arising in this method of 1−O(h^1/4) on a class of general domains, where h is the discretization parameter. This is the predicted rate for a second order optimized Schwarz method in the literature on rectangular subdomains and is also the observed rate in numerical simulations.     

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.     

Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part I: Algorithms and numerical results

Summary We describe sequential and parallel algorithms based on the Schwarz alternating method for the solution of mixed finite element discretizations of elliptic problems using the Raviart-Thomas finite element spaces. These lead to symmetric indefinite linear systems and the algorithms have some similarities with the traditional block Gauss-Seidel or block Jacobi methods with overlapping blocks. The indefiniteness requires special treatment. The sub-blocks used in the algorithm correspond to problems on a coarse grid and some overlapping subdomains and is based on a similar partition used in an algorithm of Dryja and Widlund for standard elliptic problems. If there is sufficient overlap between the subdomains, the algorithm converges with a rate independent of the mesh size, the number of subdomains and discontinuities of the coefficients. Extensions of the above algorithms to the case of local grid refinement is also described. Convergence theory for these algorithms will be presented in a subsequent paper.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 the Army Research Office under Grant DAAL 03-91-G-0150, while the author was a Visiting Assistant Researcher at UCLA     

Superlinearly convergent PCG algorithms for some nonsymmetric elliptic systems

A preconditioned conjugate gradient method is applied to finite element discretizations of some nonsymmetric elliptic systems. Mesh independent superlinear convergence is proved, which is an extension of a similar earlier result from a single equation to systems. The proposed preconditioning method involves decoupled preconditioners, which yields small and parallelizable auxiliary problems.     

Multilevel preconditioning for partition of unity methods: some analytic concepts

This paper is concerned with the construction and analysis of multilevel Schwarz preconditioners for partition of unity methods applied to elliptic problems. We show under which conditions on a given multilevel partition of unity hierarchy (MPUM) one even obtains uniformly bounded condition numbers and how to realize such requirements. The main anlytical tools are certain norm equivalences based on two-level splits providing frames that are stable under taking subsets. This work has been supported in part by the European Community’s Human Potential Programme under contract HPRN-CT-202-00286 (BREAKING COMPLEXITY), by the Leibniz-Programme of the German Research Foundation (DFG), and by the SFB 401 funded by DFG.     

On additive Schwarz preconditioners for sparse grid discretizations

Summary Based on the framework of subspace splitting and the additive Schwarz scheme, we give bounds for the condition number of multilevel preconditioners for sparse grid discretizations of elliptic model problems. For a BXP-like preconditioner we derive an estimate of the optimal orderO(1) and for a HB-like variant we obtain an estimate of the orderO(k ² ·2 ^k/2 ), wherek denotes the number of levels employed. Furthermore, we confirm these results by numerically computed condition numbers.     

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.     

Preconditioners for spectral element methods for elliptic and parabolic problems

In this paper we propose preconditioners for spectral element methods for elliptic and parabolic problems. These preconditioners are constructed using separation of variables and are easy to invert. Moreover they are spectrally equivalent to the quadratic forms which they are used to approximate.     

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     

Two-level Additive Schwarz Preconditioners for Nonconforming Finite Element Methods

Two-level additive Schwarz preconditioners are developed for the nonconforming P1 finite element approximation of scalar second-order symmetric positive definite elliptic boundary value problems, the Morley finite element approximation of the biharmonic equation, and the divergence-free nonconforming P1 finite element approximation of the stationary Stokes equations. The condition numbers of the preconditioned systems are shown to be bounded independent of mesh sizes and the number of subdomains in the case of generous overlap.

     

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.     

Automatic domain decomposition on unstructured grids (DOUG)

This paper describes a parallel iterative solver for finite element discretisations of elliptic partial differential equations on 2D and 3D domains using unstructured grids. The discretisation of the PDE is assumed to be given in the form of element stiffness matrices and the solver is automatic in the sense that it requires minimal additional information about the PDE and the geometry of the domain. The solver parallelises matrix–vector operations required by iterative methods and provides parallel additive Schwarz preconditioners. Parallelisation is implemented through MPI. The paper contains numerical experiments showing almost optimal speedup on unstructured mesh problems on a range of four platforms and in addition gives illustrations of the use of the package to investigate several questions of current interest in the analysis of Schwarz methods. The package is available in public domain from the home page http://www.maths.bath.ac.uk/^∼mjh/. This revised version was published online in August 2006 with corrections to the Cover Date.     

Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids

Summary. We consider two level overlapping Schwarz domain decomposition methods for solving the finite element problems that arise from discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Standard finite element interpolation from the coarse to the fine grid may be used. Our theory requires no assumption on the substructures that constitute the whole domain, so the substructures 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 neither the coarse mesh nor the fine mesh need be quasi-uniform. In addition, the domains defined by the fine and coarse grid need not be identical. The one important constraint is that the closure of the coarse grid must cover any portion of the fine grid boundary for which Neumann boundary conditions are given. In this general setting, our algorithms have the same optimal convergence rate as the usual two level overlapping domain decomposition methods on structured meshes. The condition number of the preconditioned system depends only on the (possibly small) overlap of the substructures and the size of the coarse grid, but is independent of the sizes of the subdomains. Received March 23, 1994 / Revised version received June 2, 1995     

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