On Schwarz's domain decomposition methods for elliptic boundary value problems

Summary. We study the additive and multiplicative Schwarz domain decomposition methods for elliptic boundary value problem of order 2 r based on an appropriate spline space of smoothness . The finite element method reduces an elliptic boundary value problem to a linear system of equations. It is well known that as the number of triangles in the underlying triangulation is increased, which is indispensable for increasing the accuracy of the approximate solution, the size and condition number of the linear system increases. The Schwarz domain decomposition methods will enable us to break the linear system into several linear subsystems of smaller size. We shall show in this paper that the approximate solutions from the multiplicative Schwarz domain decomposition method converge to the exact solution of the linear system geometrically. We also show that the additive Schwarz domain decomposition method yields a preconditioner for the preconditioned conjugate gradient method. We tested these methods for the biharmonic equation with Dirichlet boundary condition over an arbitrary polygonal domain using cubic spline functions over a quadrangulation of the given domain. The computer experiments agree with our theoretical results. Received December 28, 1995 / Revised version received November 17, 1998 / Published online September 24, 1999     

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     

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     

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     

Sharpened forms of the generalized Schwarz inequality on the boundary

In this paper, a boundary version of the Schwarz inequality is investigated. We obtain more general results at the boundary. If we know the second coefficient in the expansion of the function f(z) = 1 + c_pz^p + c_{p + 1}z^{p + 1}…, then we obtain new inequalities of the Schwarz inequality at boundary by taking into account c_{p + 1} and zeros of the function f(z) ? 1. The sharpness of these inequalities is also proved.     

Isoperimetric properties of Euclidean boundary moments of a simply connected domain

We consider integral functionals of a simply connected domain which depend on the distance to the domain boundary. We prove an isoperimetric inequality generalizing theorems derived by the Schwarz symmetrization method. For L ^p -norms of the distance function we prove an analog of the Payne inequality for the torsional rigidity of the domain. In compare with the Payne inequality we find new extremal domains different from a disk.     

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.     

Additive Schwarz method for the p-version of the boundary element method for the single layer potential operator on a plane screen

Summary. We analyze an additive Schwarz preconditioner for the p-version of the boundary element method for the single layer potential operator on a plane screen in the three-dimensional Euclidean space. We decompose the ansatz space, which consists of piecewise polynomials of degree p on a mesh of size h, by introducing a coarse mesh of size . After subtraction of the coarse subspace of piecewise constant functions on the coarse mesh this results in local subspaces of piecewise polynomials living only on elements of size H. This decomposition yields a preconditioner which bounds the spectral condition number of the stiffness matrix by . Numerical results supporting the theory are presented. Received August 15, 1998 / Revised version received November 11, 1999 / Published online December 19, 2000     

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     

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     

Pathwise uniqueness for stochastic heat equations with H?lder continuous coefficients: the white noise case

We prove pathwise uniqueness for solutions of parabolic stochastic pde??s with multiplicative white noise if the coefficient is H?lder continuous of index ?? > 3/4. The method of proof is an infinite-dimensional version of the Yamada?CWatanabe argument for ordinary stochastic differential equations.     

Noise sensitivity in continuum percolation

We prove that the Poisson Boolean model, also known as the Gilbert disc model, is noise sensitive at criticality. This is the first such result for a Continuum Percolation model, and the first which involves a percolation model with critical probability p _c ≠ 1/2. Our proof uses a version of the Benjamini-Kalai-Schramm Theorem for biased product measures. A quantitative version of this result was recently proved by Keller and Kindler. We give a simple deduction of the non-quantitative result from the unbiased version. We also develop a quite general method of approximating Continuum Percolation models by discrete models with p _c bounded away from zero; this method is based on an extremal result on non-uniform hypergraphs.     

Sous-groupes canoniques partiels

The reduction of Siegel varieties modulo a prime number p is stratified by the multiplicative rank of the p-divisible group of the universal abelian variety. For r ≥ 0, the maximal multiplicative subgroup of the restriction of the p-torsion group of the universal abelian variety to the r-th stratum lifts canonically to the tube of this stratum and defines a «partial canonical subgroup of rank r». We show that there exists a strict neighbourhood of the tube on which this subgroup extends in a finite flat way. On the ordinary stratum and its neighbourhood, we recover the usuel canonical subgroup studied by Abbes and Mokrane, and Andreatta and Gasbarri.     

Schwarz symmetrization and comparison results for nonlinear elliptic equations and eigenvalue problems

We compare the distribution function and the maximum of solutions of nonlinear elliptic equations defined in general domains with solutions of similar problems defined in a ball using Schwarz symmetrization. As an application, we prove the existence and bound of solutions for some nonlinear equation. Moreover, for some nonlinear problems, we show that if the first p-eigenvalue of a domain is big, the supremum of a solution related to this domain is close to zero. For that we obtain L ^∞ estimates for solutions of nonlinear and eigenvalue problems in terms of other L ^p norms.     

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.     

Nearly optimal convergence result for multigrid with aggressive coarsening and polynomial smoothing

We analyze a general multigrid method with aggressive coarsening and polynomial smoothing. We use a special polynomial smoother that originates in the context of the smoothed aggregation method. Assuming the degree of the smoothing polynomial is, on each level k, at least Ch _k+1/h _k , we prove a convergence result independent of h _k+1/h _k . The suggested smoother is cheaper than the overlapping Schwarz method that allows to prove the same result. Moreover, unlike in the case of the overlapping Schwarz method, analysis of our smoother is completely algebraic and independent of geometry of the problem and prolongators (the geometry of coarse spaces).     

Groups where each element is conjugate to its certain power

This paper deals with a rationality condition for groups. Let n be a fixed positive integer. Suppose every element g of the finite solvable group is conjugate to its nth power g ⁿ . Let p be a prime divisor of the order of the group. We conclude that the multiplicative order of n modulo p is small, or p is small.     

On reconstruction of multiplicative transformations of functions in anisotropic spaces

We construct a reconstruction operator for multiplicative transformations of functions in anisotropic spaces from their values at a given number of points. We show that the error of the reconstruction of a function in W _p ^α coincides in order with the corresponding orthodiameter.     

On the enumeration of finite Abelian and solvable groups

Let a(n) be the number of nonisomorphic abelian groups of order n. We obtain a short interval result for the local density of a(n). More generally, we get short interval version of results of Ivi? on the local density of prime independent multiplicative functions. Also we prove a short interval version of the theorem of Erdös and Szekeres on the summatory function of a(n) and the theorem of Greenberg and Newman on the enumeration of a certain type of finite solvable groups.     

Multiplicative character sums of Fermat quotients and pseudorandom sequences

We prove a bound on sums of products of multiplicative characters of shifted Fermat quotients modulo p. From this bound we derive results on the pseudorandomness of sequences of modular discrete logarithms of Fermat quotients modulo p: bounds on the well-distribution measure, the correlation measure of order ?, and the linear complexity.