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.     

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.     

An additive Schwarz preconditioner for the FETI method

Summary.  A new additive Schwarz preconditioner for the Finite Element Tearing and Interconnecting (FETI) method is analyzed in this paper. This preconditioner has the unique feature that the coefficient matrix of its ``coarse grid' problem is mesh independent. For a model second order heterogeneous elliptic boundary value problem in two dimensions, the condition number of the preconditioned system is shown to be bounded by C[1+ln(H/h)]², where h is the mesh size, H is the typical diameter of the subdomains, and the constant C is independent of h, H, the number of subdomains and the coefficients of the boundary value problem. Received May 8, 2000 / Revised version received January 2, 2002 / Published online July 18, 2002 Mathematics Subject Classification (1991): 65N55, 65N30     

Spectral stability of the Robin Laplacian

We consider the Robin Laplacian in two bounded regions Ω₁ and Ω₂ of ℝ ^N with Lipschitz boundaries and such that Ω₂ ⊂ Ω₁, and we obtain two-sided estimates for the eigenvalues λ _n,2 of the Robin Laplacian in Ω₂ via the eigenvalues λ _{n, 1} of the Robin Laplacian in Ω₁. Our estimates depend on the measure of the set difference Ω\Ω₂ and on suitably defined characteristics of vicinity of the boundaries ∂Ω₁ and ∂Ω₂, and of the functions defined on ∂Ω₁ and on ∂Ω₂ that enter the Robin boundary conditions.     

A spectral method for elliptic equations: the Neumann problem

Let Ω be an open, simply connected, and bounded region in ℝ ^d , d ≥ 2, and assume its boundary ∂Ω is smooth. Consider solving the elliptic partial differential equation − Δu + γu = f over Ω with a Neumann boundary condition. The problem is converted to an equivalent elliptic problem over the unit ball B, and then a spectral method is given that uses a special polynomial basis. In the case the Neumann problem is uniquely solvable, and with sufficiently smooth problem parameters, the method is shown to have very rapid convergence. Numerical examples illustrate exponential convergence.     

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.     

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

An approach combining the Ritz-Galerkin and finite difference methods

The nonconforming combination of Ritz-Galerkin and finite difference methods is presented for solving elliptic boundary value problems with singularities. The Ritz-Galerkin method is used in the subdomains including singularities, the finite difference method is used in the rest of the solution domain. Moreover, on the common boundary of two regions where two different methods are used, the continuity conditions are constrained only on the nodes of difference grids. Theoretical analysis and numerical experiments have shown that average errors of numerical solutions and their generalized derivatives can reach the convergence rate O(h^2-δ), where h is the mesh spacing of uniform difference grids, and δ is an arbitrarily small, positive number. This convergence rate is better than O(h), obtained by the nonconforming combination of the Ritz-Galerkin and finite element methods.     

Exponential decay bounds for nonlinear heat problems with Robin boundary conditions

We investigate the behavior of the solution of a nonlinear heat problem, when Robin conditions are prescribed on the boundary ∂Ω × (t > 0), Ω a bounded R ² domain. We determine conditions on the geometry and data sufficient to preclude the blow up of the solution and to obtain an exponential decay bound for the solution and its gradient.     

Analysis of FETI methods for multiscale PDEs

In this paper, we study a variant of the finite element tearing and interconnecting (FETI) method which is suitable for elliptic PDEs with highly heterogeneous (multiscale) coefficients α(x); in particular, coefficients with strong variation within subdomains and/or jumps that are not aligned with the subdomain interfaces. Using energy minimisation and cut-off arguments we can show rigorously that for an arbitrary (positive) coefficient function the condition number of the preconditioned FETI system can be bounded by C(α) (1 + log(H/h))² where H is the subdomain diameter and h is the mesh size, and where the function C(α) depends only on the coefficient variation in the vicinity of subdomain interfaces. In particular, if varies only mildly in a layer Ω _i,η of width η near the boundary of each of the subdomains Ω _i , then , independent of the variation of α in the remainder Ω _i \Ω _i,η of each subdomain and independent of any jumps of α across subdomain interfaces. The quadratic dependence of C(α) on H/η can be relaxed to a linear dependence under stronger assumptions on the behaviour of α in the interior of the subdomains. Our theoretical findings are confirmed in numerical tests. C. Pechstein was supported by the Austrian Science Funds (FWF) under grant F1306.     

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.     

Solvability of inhomogeneous boundary-value problems for fourth-order differential equations

We consider a Cauchy-type boundary-value problem, a problem with three boundary conditions, and the Dirichlet problem for a general typeless fourth-order differential equation with constant complex coefficients and nonzero right-hand side in a bounded domain Ω ⊂ R ² with smooth boundary. By the method of the Green formula, the theory of extensions of differential operators, and the theory of L-traces (i.e., traces associated with the differential operation L), we establish necessary and sufficient (for elliptic operators) conditions of the solvability of each of these problems in the space H ^m (Ω), m ≥ 4.     

Exponential decay bounds for nonlinear heat problems with Robin boundary conditions

We investigate the behavior of the solution of a nonlinear heat problem, when Robin conditions are prescribed on the boundary ∂Ω × (t > 0), Ω a bounded R ² domain. We determine conditions on the geometry and data sufficient to preclude the blow up of the solution and to obtain an exponential decay bound for the solution and its gradient. Supported by the University of Cagliari.     

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)     

Two-layer muti-parameterized Schwarz Alternating Method

The convergence rate of a numerical procedure based on Schwarz Alternating Method (SAM) for solving elliptic boundary value problems (BVP’s) depends on the selection of the interface conditions applied on the interior boundaries of the overlapping subdomains. It has been observed that theRobin condition(mixed interface condition), controlled by a parameter, can optimize SAM’s convergence rate. Since the convergence rate is very sensitive to the parameter, Tang[17] suggested another interface condition calledover- determined interface condition. Based on the over-determined interface condition, we formulate thetwo-layer multi-parameterized SAM. For the SAM and the one-dimensional elliptic model BVP’s, we determine analytically the optimal values of the parameters. For the two-dimensional elliptic BVP’s, we also formulate the two-layer multiparameterized SAM and suggest a choice of multi-parameter to produce good convergence rate.     

Algebraic theory of multiplicative Schwarz methods

The convergence of multiplicative Schwarz-type methods for solving linear systems when the coefficient matrix is either a nonsingular M-matrix or a symmetric positive definite matrix is studied using classical and new results from the theory of splittings. The effect on convergence of algorithmic parameters such as the number of subdomains, the amount of overlap, the result of inexact local solves and of “coarse grid” corrections (global coarse solves) is analyzed in an algebraic setting. Results on algebraic additive Schwarz are also included.     

Sunyer-i-Balaguer’s almost elliptic functions and Yosida’s normal functions

We study the properties of two classes of meromorphic functions in the complex plane. The first one is the class of almost elliptic functions in the sense of Sunyer-i-Balaguer. This is the class of meromorphic functions f such that the family {f(z + h)} _h∈ℂ is normal with respect to the uniform convergence in the whole complex plane. Given two sequences of complex numbers, we provide sufficient conditions for themto be zeros and poles of some almost elliptic function. These conditions enable one to give (for the first time) explicit non-trivial examples of almost elliptic functions. The second class was introduced by K. Yosida, who called it the class of normal functions of the first category. This is the class of meromorphic functions f such that the family {f(z + h)} _h∈ℂ is normal with respect to the uniform convergence on compacta in the complex plane and no limit point of the family is a constant function. We give necessary and sufficient conditions for two sequences of complex numbers to be zeros and poles of some normal function of the first category and obtain a parametric representation for this class in terms of zeros and poles.     

Irreducibility and Mixed Boundary Conditions

In this paper we consider positive semigroups on L^p(Ω) generated by elliptic operators A subject to mixed Dirichlet-Neumann boundary conditions on non-smooth domains Ω. We show in particular that these semigroups as well as those generated by multiplicative perturbations bA of A are irreducible, provided b ∈ L^∞(Ω) is real and satisfies b ≥ δ for some δ > 0. In memoriam Helmut H. Schaefer     

Asymptotic analysis of a parabolic semilinear problem with nonlinear boundary multiphase interactions in a perforated domain

We consider a parabolic semilinear problem with rapidly oscillating coefficients in a domain Ω_ε that is ε-periodically perforated by small holes of size O\mathcal {O}(ε). The holes are divided into two ε-periodical sets depending on the boundary interaction at their surfaces, and two different nonlinear Robin boundary conditions σ_ε(u _ε) + εκ _m (u _ε) = εg ^(m) _ε, m = 1, 2, are imposed on the boundaries of holes. We study the asymptotics as ε → 0 and establish a convergence theorem without using extension operators. An asymptotic approximation of the solution and the corresponding error estimate are also obtained. Bibliography: 60 titles. Illustrations: 1 figure.     

On Schwarz Alternating Methods for the Subsonic Full Potential Equation

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 of the subdomains. The full potential equation is derived from the Navier–Stokes equations assuming the fluid is compressible, inviscid, irrotational and isentropic. It is being used by the aircraft industry to model flow over an airfoil or even an entire aircraft. This paper shows that the additive and multiplicative versions of the Schwarz alternating method, when applied to the full potential equation in three dimensions, converge to the true solution geometrically. The assumptions are that the initial guess and the true solution are everywhere subsonic. We use the convergence proof by Tai and Xu and modify it for certain closed convex subsets.