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     

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     

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     

Adaptive finite element methods for elliptic equations with non-smooth coefficients

Summary. We consider a second-order elliptic equation with discontinuous or anisotropic coefficients in a bounded two- or three dimensional domain, and its finite-element discretization. The aim of this paper is to prove some a priori and a posteriori error estimates in an appropriate norm, which are independent of the variation of the coefficients. Received February 5, 1999 / Published online March 16, 2000     

Multiscale finite element for problems with highly oscillatory coefficients

Summary. In this paper, we study a multiscale finite element method for solving a class of elliptic problems with finite number of well separated scales. The method is designed to efficiently capture the large scale behavior of the solution without resolving all small scale features. This is accomplished by constructing the multiscale finite element base functions that are adaptive to the local property of the differential operator. The construction of the base functions is fully decoupled from element to element; thus the method is perfectly parallel and is naturally adapted to massively parallel computers. We present the convergence analysis of the method along with the results of our numerical experiments. Some generalizations of the multiscale finite element method are also discussed. Received April 17, 1998 / Revised version received March 25, 2000 / Published online June 7, 2001     

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     

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     

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     

Least-squares mixed finite element methods for non-selfadjoint elliptic problems: I. Error estimates

Summary. A least-squares mixed finite element method for general second-order non-selfadjoint elliptic problems in two- and three-dimensional domains is formulated and analyzed. The finite element spaces for the primary solution approximation and the flux approximation consist of piecewise polynomials of degree and respectively. The method is mildly nonconforming on the boundary. The cases and are studied. It is proved that the method is not subject to the LBB-condition. Optimal - and -error estimates are derived for regular finite element partitions. Numerical experiments, confirming the theoretical rates of convergence, are presented. Received October 15, 1993 / Revised version received August 2, 1994     

Asynchronous two-stage iterative methods

Summary. Parallel block two-stage iterative methods for the solution of linear systems of algebraic equations are studied. Convergence is shown for monotone matrices and for -matrices. Two different asynchronous versions of these methods are considered and their convergence investigated. Received September 7, 1993 / Revised version received April 21, 1994     

On the locking phenomenon for a class of elliptic problems

Summary. In this paper we study the numerical behaviour of elliptic problems in which a small parameter is involved and an example concerning the computation of elastic arches is analyzed using this mathematical framework. At first, the statements of the problem and its Galerkin approximations are defined and an asymptotic analysis is performed. Then we give general conditions ensuring that a numerical scheme will converge uniformly with respect to the small parameter. Finally we study an example in computation of arches working in linear elasticity conditions. We build one finite element scheme giving a locking behaviour, and another one which does not. Revised version received October 25, 1993     

Accelerated monotone iterative methods for finite difference equations of reaction-diffusion

This paper is concerned with numerical methods for a finite difference system of reaction-diffusion-convection equation under nonlinear boundary condition. Various monotone iterative methods are presented, and each of these methods leads to an existence-comparison theorem as well as a computational algorithm for numerical solutions. The monotone property of the iterations gives improved upper and lower bounds of the solution in each iteration, and the rate of convergence of the iterations is either quadratic or nearly quadratic depending on the property of the nonlinear function. Application is given to a model problem from chemical engineering, and some numerical results, including a test problem with known analytical solution, are presented to illustrate the various rates of convergence of the iterations. Received November 2, 1995 / Revised version received February 10, 1997     

On hybrid iterative methods for nonsymmetric systems of linear equations

Summary. Hybrid methods for the solution of systems of linear equations consist of a first phase where some information about the associated coefficient matrix is acquired, and a second phase in which a polynomial iteration designed with respect to this information is used. Most of the hybrid algorithms proposed recently for the solution of nonsymmetric systems rely on the direct use of eigenvalue estimates constructed by the Arnoldi process in Phase I. We will show the limitations of this approach and propose an alternative, also based on the Arnoldi process, which approximates the field of values of the coefficient matrix and of its inverse in the Krylov subspace. We also report on numerical experiments comparing the resulting new method with other hybrid algorithms. Received May 27, 1993 / Revised version received November 14, 1994     

A posteriori error estimation for fully discrete hierarchic models of elliptic boundary value problems on thin domains

Summary. A posteriori error estimators for fully discrete hierarchic modelling on thin domains are derived and are shown to provide computable upper bounds on the discretization error and on the total error. The estimators are shown to be robust and do not degenerate as the thickness of the domain tends to zero. If the discretization part of the error is negligible, the estimator for the modelling error reduces to the one recently obtained for semi-discrete hierarchical modelling by Babuska and Schwab. Received July 25, 1996 / Revised version received July 31, 1997     

Finite volume element methods for non-definite problems

Summary. The error estimates for finite volume element method applied to 2 and 3-D non-definite problems are derived. A simple upwind scheme is proven to be unconditionally stable and first order accurate. Received August 27, 1997 / Revised version received May 12, 1998     

A finite-element capacitance matrix method for exterior Helmholtz problems

Summary. We introduce an algorithm for the efficient numerical solution of exterior boundary value problems for the Helmholtz equation. The problem is reformulated as an equivalent one on a bounded domain using an exact non-local boundary condition on a circular artificial boundary. An FFT-based fast Helmholtz solver is then derived for a finite-element discretization on an annular domain. The exterior problem for domains of general shape are treated using an imbedding or capacitance matrix method. The imbedding is achieved in such a way that the resulting capacitance matrix has a favorable spectral distribution leading to mesh independent convergence rates when Krylov subspace methods are used to solve the capacitance matrix equation. Received May 2, 1995     

Block monotone iterative methods for numerical solutions of nonlinear elliptic equations

Summary. Two block monotone iterative schemes for a nonlinear algebraic system, which is a finite difference approximation of a nonlinear elliptic boundary-value problem, are presented and are shown to converge monotonically either from above or from below to a solution of the system. This monotone convergence result yields a computational algorithm for numerical solutions as well as an existence-comparison theorem of the system, including a sufficient condition for the uniqueness of the solution. An advantage of the block iterative schemes is that the Thomas algorithm can be used to compute numerical solutions of the sequence of iterations in the same fashion as for one-dimensional problems. The block iterative schemes are compared with the point monotone iterative schemes of Picard, Jacobi and Gauss-Seidel, and various theoretical comparison results among these monotone iterative schemes are given. These comparison results demonstrate that the sequence of iterations from the block iterative schemes converges faster than the corresponding sequence given by the point iterative schemes. Application of the iterative schemes is given to a logistic model problem in ecology and numerical ressults for a test problem with known analytical solution are given. Received August 1, 1993 / Revised version received November 7, 1994     

On the convergence of line iterative methods for cyclically reduced non-symmetrizable linear systems

Summary. We derive analytic bounds on the convergence factors associated with block relaxation methods for solving the discrete two-dimensional convection-diffusion equation. The analysis applies to the reduced systems derived when one step of block Gaussian elimination is performed on red-black ordered two-cyclic discretizations. We consider the case where centered finite difference discretization is used and one cell Reynolds number is less than one in absolute value and the other is greater than one. It is shown that line ordered relaxation exhibits very fast rates of convergence. Received March 3, 1992/Revised version received July 2, 1993     

Block triangular preconditioners for nonsymmetric saddle point problems: field-of-values analysis

A preconditioned minimal residual method for nonsymmetric saddle point problems is analyzed. The proposed preconditioner is of block triangular form. The aim of this article is to show that a rigorous convergence analysis can be performed by using the field of values of the preconditioned linear system. As an example, a saddle point problem obtained from a mixed finite element discretization of the Oseen equations is considered. The convergence estimates obtained by using a field–of–values analysis are independent of the discretization parameter h. Several computational experiments supplement the theoretical results and illustrate the performance of the method. Received March 20, 1997 / Revised version received January 14, 1998     

Mixed hp finite element methods for problems in elasticity and Stokes flow

Summary. We consider the mixed formulation for the elasticity problem and the limiting Stokes problem in , . We derive a set of sufficient conditions under which families of mixed finite element spaces are simultaneously stable with respect to the mesh size and, subject to a maximum loss of , with respect to the polynomial degree . We obtain asymptotic rates of convergence that are optimal up to in the displacement/velocity and up to in the "pressure", with arbitrary (both rates being optimal with respect to ). Several choices of elements are discussed with reference to properties desirable in the context of the -version. Received March 4, 1994 / Revised version received February 12, 1995