A domain decomposition algorithm for elliptic problems in three dimensions

Summary Most domain decomposition algorithms have been developed for problems in two dimensions. One reason for this is the difficulty in devising a satisfactory, easy-to-implement, robust method of providing global communication of information for problems in three dimensions. Several methods that work well in two dimension do not perform satisfactorily in three dimensions.A new iterative substructuring algorithm for three dimensions is proposed. It is shown that the condition number of the resulting preconditioned problem is bounded independently of the number of subdomains and that the growth is quadratic in the logarithm of the number of degrees of freedom associated with a subdomain. The condition number is also bounded independently of the jumps in the coefficients of the differential equation between subdomains. The new algorithm also has more potential parallelism than the iterative substructuring methods previously proposed for problems in three dimensions.This work was supported in part by the National Science Foundation under grant NSF-CCR-8903003 and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Convergence and optimization of the parallel method of simultaneous directions for the solution of elliptic problems

For the solution of elliptic problems, fractional step methods and in particular alternating directions (ADI) methods are iterative methods where fractional steps are sequential. Therefore, they only accept parallelization at low level. In [T. Lu, P. Neittaanmäki, X.C. Tai, A parallel splitting-up method for partial differential equations and its applications to Navier–Stokes equations, RAIRO Modél. Math. Anal. Numér. 26 (6) (1992) 673–708], Lu et al. proposed a method where the fractional steps can be performed in parallel. We can thus speak of parallel fractional step (PFS) methods and, in particular, simultaneous directions (SDI) methods. In this paper, we perform a detailed analysis of the convergence and optimization of PFS and SDI methods, complementing what was done in [T. Lu, P. Neittaanmäki, X.C. Tai, A parallel splitting-up method for partial differential equations and its applications to Navier–Stokes equations, RAIRO Modél. Math. Anal. Numér. 26 (6) (1992) 673–708]. We describe the behavior of the method and we specify the good choice of the parameters. We also study the efficiency of the parallelization. Some 2D, 3D and high-dimensional tests confirm our results.     

Preconditioning cubic spline collocation discretizations of elliptic equations

Summary. This work considers the uniformly elliptic operator defined by in (the unit square) with boundary conditions: on and on and its discretization based on Hermite cubic spline spaces and collocation at the Gauss points. Using an interpolatory basis with support on the Gauss points one obtains the matrix . We discuss the condition numbers and the distribution of -singular values of the preconditioned matrices where is the stiffness matrix associated with the finite element discretization of the positive definite uniformly elliptic operator given by in with boundary conditions: on on . The finite element space is either the space of continuous functions which are bilinear on the rectangles determined by Gauss points or the space of continuous functions which are linear on the triangles of the triangulation of using the Gauss points. When we obtain results on the eigenvalues of . In the general case we obtain bounds and clustering results on the -singular values of . These results are related to the results of Manteuffel and Parter [MP], Parter and Wong [PW], and Wong [W] for finite element discretizations as well as the results of Parter and Rothman [PR] for discretizations based on Legendre Spectral Collocation. Received January 1, 1994 / Revised version received February 7, 1995     

A domain decomposition discretization of parabolic problems

In recent years, domain decomposition methods have attracted much attention due to their successful application to many elliptic and parabolic problems. Domain decomposition methods treat problems based on a domain substructuring, which is attractive for parallel computation, due to the independence among the subdomains. In principle, domain decomposition methods may be applied to the system resulting from a standard discretization of the parabolic problems or, directly, be carried out through a discretization of parabolic problems. In this paper, a direct domain decomposition method is introduced to discretize the parabolic problems. The stability and convergence of this algorithm are analyzed. This work was supported in part by Polish Sciences Foundation under grant 2P03A00524. This work was supported in part by the US Department of Energy under Contracts DE-FG02-92ER25127 and by the Director, Office of Science, Advanced Scientific Computing Research, U.S. Department of Energy under contract DE-AC02-05CH11231.     

Local refinement techniques for elliptic problems on cell-centered grids

Summary Algebraic multilevel analogues of the BEPS preconditioner designed for solving discrete elliptic problems on grids with local refinement are formulated, and bounds on their relative condition numbers, with respect to the composite-grid matrix, are derived. TheV-cycle and, more generally,v-foldV-cycle multilevel BEPS preconditioners are presented and studied. It is proved that for 2-D problems theV-cycle multilevel BEPS is almost optimal, whereas thev-foldV-cycle algebraic multilevel BEPS is optimal under a mild restriction on the composite cell-centered grid. For thev-fold multilevel BEPS, the variational relation between the finite difference matrix and the corresponding matrix on the next-coarser level is not necessarily required. Since they are purely algebraically derived, thev-fold (v>1) multilevel BEPS preconditioners perform without any restrictionson the shape of subregions, unless the refinement is too fast. For theV-cycle BEPS preconditioner (2-D problem), a variational relation between the matrices on two consecutive grids is required, but there is no restriction on the method of refinement on the shape, or on the size of the subdomains.     

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.     

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     

A note on skewcirculant preconditioners for elliptic problems

In a recent paper Chan and Chan study the use of circulant preconditioners for the solution of elliptic problems. They prove that circulant preconditioners can be chosen so that the condition number of the preconditioned system can be reduced fromO(n ² ) toO(n). In addition, using the Fast Fourier Transform, the computation of the preconditioner is highly parallelizable. To obtain their result, Chan and Chan introduce a shift /p/n ² for some >0. The aim of this paper is to consider skewcirculant preconditioners, and to show that in this case the condition number ofO(n) can easily be shown without using the somewhat unsatisfactory shift /p/n ². Furthermore, our estimates are more precise.     

The cascadic multigrid method for elliptic problems

Summary. The paper deals with certain adaptive multilevel methods at the confluence of nested multigrid methods and iterative methods based on the cascade principle of [10]. From the multigrid point of view, no correction cycles are needed; from the cascade principle view, a basic iteration method without any preconditioner is used at successive refinement levels. For a prescribed error tolerance on the final level, more iterations must be spent on coarser grids in order to allow for less iterations on finer grids. A first candidate of such a cascadic multigrid method was the recently suggested cascadic conjugate gradient method of [9], in short CCG method, whichused the CG method as basic iteration method on each level. In [18] it has been proven, that the CCG method is accurate with optimal complexity for elliptic problems in 2D and quasi-uniform triangulations. The present paper simplifies that theory and extends it to more general basic iteration methods like the traditional multigrid smoothers. Moreover, an adaptive control strategy for the number of iterations on successive refinement levels for possibly highly non-uniform grids is worked out on the basis of a posteriori estimates. Numerical tests confirm the efficiency and robustness of the cascadic multigrid method. Received November 12, 1994 / Revised version received October 12, 1995     

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     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

Finite element approximation of multi-scale elliptic problems using patches of elements

In this paper we present a method for the numerical solution of elliptic problems with multi-scale data using multiple levels of not necessarily nested grids. The method consists in calculating successive corrections to the solution in patches whose discretizations are not necessarily conforming. This paper provides proofs of the results published earlier (see C. R. Acad. Sci. Paris, Ser. I 337 (2003) 679–684), gives a generalization of the latter to more than two domains and contains extensive numerical illustrations. New results including the spectral analysis of the iteration operator and a numerical method to evaluate the constant of the strengthened Cauchy-Buniakowski-Schwarz inequality are presented. Supported by CTI Project 6437.1 IWS-IW.     

An interpolation matched interface and boundary method for elliptic interface problems

An interpolation matched interface and boundary (IMIB) method with second-order accuracy is developed for elliptic interface problems on Cartesian grids, based on original MIB method proposed by Zhou et al. [Y. Zhou, G. Wei, On the fictious-domain and interpolation formulations of the matched interface and boundary method, J. Comput. Phys. 219 (2006) 228-246]. Explicit and symmetric finite difference formulas at irregular grid points are derived by virtue of the level set function. The difference scheme using IMIB method is shown to satisfy the discrete maximum principle for a certain class of problems. Rigorous error analyses are given for the IMIB method applied to one-dimensional (1D) problems with piecewise constant coefficients and two-dimensional (2D) problems with singular sources. Comparison functions are constructed to obtain a sharp error bound for 1D approximate solutions. Furthermore, we compare the ghost fluid method (GFM), immersed interface method (IIM), MIB and IMIB methods for 1D problems. Finally, numerical examples are provided to show the efficiency and robustness of the proposed method.     

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     

A p-version finite element method for nonlinear elliptic variational inequalities in 2D

This article introduces and analyzes a p-version FEM for variational inequalities resulting from obstacle problems for some quasi-linear elliptic partial differential operators. We approximate the solution by controlling the obstacle condition in images of the Gauss–Lobatto points. We show existence and uniqueness for the discrete solution u _p from the p-version for the obstacle problem. We prove the convergence of u _p towards the solution with respect to the energy norm, and assuming some additional regularity for the solution we derive an a priori error estimate. In numerical experiments the p-version turns out to be superior to the h-version concerning the convergence rate and the number of unknowns needed to achieve a certain exactness of the approximation.     

Robust iterative methods for elliptic problems with highly varying coefficients in thin substructures

Summary. In this paper we introduce a class of robust multilevel interface solvers for two-dimensional finite element discrete elliptic problems with highly varying coefficients corresponding to geometric decompositions by a tensor product of strongly non-uniform meshes. The global iterations convergence rate is shown to be of the order with respect to the number of degrees of freedom on the single subdomain boundaries, uniformly upon the coarse and fine mesh sizes, jumps in the coefficients and aspect ratios of substructures. As the first approach, we adapt the frequency filtering techniques [28] to construct robust smoothers on the highly non-uniform coarse grid. As an alternative, a multilevel averaging procedure for successive coarse grid correction is proposed and analyzed. The resultant multilevel coarse grid preconditioner is shown to have (in a two level case) the condition number independent of the coarse mesh grading and jumps in the coefficients related to the coarsest refinement level. The proposed technique exhibited high serial and parallel performance in the skin diffusion processes modelling [20] where the high dimensional coarse mesh problem inherits a strong geometrical and coefficients anisotropy. The approach may be also applied to magnetostatics problems as well as in some composite materials simulation. Received December 27, 1994     

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.     

On computation of solution curves for semilinear elliptic problems

We consider computation of solution curves for semilinear elliptic equations. In case solution is stable, we present an algorithm with monotone convergence, which is a considerable improvement of the corresponding schemes in [4] and [5]. For the unstable solutions, we show how to construct a fourth-order evolution equation, for which the same solution will be stable.