Balancing domain decomposition for nonconforming plate elements

Summary. In this paper the balancing domain decomposition method is extended to nonconforming plate elements. The condition number of the preconditioned system is shown to be bounded by , where H measures the diameters of the subdomains, h is the mesh size of the triangulation, and the constant C is independent of H, h and the number of subdomains. Received August 14, 1997     

An additive Schwarz preconditioner for p-version boundary element approximation of the hypersingular operator in three dimensions

Summary. Additive Schwarz preconditioners are developed for the p-version of the boundary element method for the hypersingular integral equation on surfaces in three dimensions. The principal preconditioner consists of decomposing the subspace into local spaces associated with the element interiors supplemented with a wirebasket space associated with the the element interfaces. The wirebasket correction involves inverting a diagonal matrix. If exact solvers are used on the element interiors then theoretical analysis shows that growth of the condition number of the preconditioned system is bounded by for an open surface and for a closed surface. A modified form of the preconditioner only requires the inversion of a diagonal matrix but results in a further degradation of the condition number by a factor . Received December 15, 1998 / Revised version received March 26, 1999 / Published online March 16, 2000     

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     

A preconditioner for the h-p version of the finite element method in two dimensions

Summary. A preconditioner, based on a two-level mesh and a two-level orthogonalization, is proposed for the - version of the finite element method for two dimensional elliptic problems in polygonal domains. Its implementation is in parallel on the subdomain level for the linear or bilinear (nodal) modes, and in parallel on the element level for the high order (side and internal) modes. The condition number of the preconditioned linear system is of order , where is the diameter of the -th subdomain, and are the diameter of elements and the maximum polynomial degree used in the subdomain. This result reduces to well-known results for the -version (i.e. ) and the -version (i.e. ) as the special cases of the - version. Received August 15, 1995 / Revised version received November 13, 1995     

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     

Multigrid for the mortar element method for P1 nonconforming element

In this paper, a multigrid algorithm is presented for the mortar element method for P1 nonconforming element. Based on the theory developed by Bramble, Pasciak, Xu in [5], we prove that the W-cycle multigrid is optimal, i.e. the convergence rate is independent of the mesh size and mesh level. Meanwhile, a variable V-cycle multigrid preconditioner is constructed, which results in a preconditioned system with uniformly bounded condition number. Received May 11, 1999 / Revised version received April 1, 2000 / Published online October 16, 2000     

A robust hierarchical basis preconditioner on general meshes

Summary. In this paper, we introduce a multi-level direct sum space decomposition of general, possibly locally refined linear or multi-linear finite element spaces. The resulting additive Schwarz preconditioner is optimal for symmetric second order elliptic problems. Moreover, it turns out to be robust with respect to coefficient jumps over edges in the coarsest mesh, perturbations with positive zeroth order terms, and, after a further decomposition of the spaces, also with respect to anisotropy along the grid lines. Important for an efficient implementation is that stable bases of the subspaces defining our decomposition, consisting of functions having small supports can be easily constructed. Received September 8, 1995 / Revised version received October 31, 1996     

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     

Weighted max norms, splittings, and overlapping additive Schwarz iterations

Summary. Weighted max-norm bounds are obtained for Algebraic Additive Schwarz Iterations with overlapping blocks for the solution of Ax = b, when the coefficient matrix A is an M-matrix. The case of inexact local solvers is also covered. These bounds are analogous to those that exist using A-norms when the matrix A is symmetric positive definite. A new theorem concerning P-regular splittings is presented which provides a useful tool for the A-norm bounds. Furthermore, a theory of splittings is developed to represent Algebraic Additive Schwarz Iterations. This representation makes a connection with multisplitting methods. With this representation, and using a comparison theorem, it is shown that a coarse grid correction improves the convergence of Additive Schwarz Iterations when measured in weighted max norm. Received March 13, 1998 / Revised version received January 26, 1999     

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     

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     

Nonconforming finite elements and the cascadic multi-grid method

Summary. We derive sufficient conditions under which the cascadic multi-grid method applied to nonconforming finite element discretizations yields an optimal solver. Key ingredients are optimal error estimates of such discretizations, which we therefore study in detail. We derive a new, efficient modified Morley finite element method. Optimal cascadic multi-grid methods are obtained for problems of second, and using a new smoother, of fourth order as well as for the Stokes problem. Received February 12, 1998 / Revised version received January 9, 2001 / Published online September 19, 2001     

Schwarz methods with local refinement for the p-version finite element method

Summary. In some applications, the accuracy of the numerical solution of an elliptic problem needs to be increased only in certain parts of the domain. In this paper, local refinement is introduced for an overlapping additive Schwarz algorithm for the $-version finite element method. Both uniform and variable degree refinements are considered. The resulting algorithm is highly parallel and scalable. In two and three dimensions, we prove an optimal bound for the condition number of the iteration operator under certain hypotheses on the refinement region. This bound is independent of the degree $, the number of subdomains $ and the mesh size $. In the general two dimensional case, we prove an almost optimal bound with polylogarithmic growth in $. Received February 20, 1993 / Revised version received January 20, 1994     

A new superconvergence property of Wilson nonconforming finite element

Summary. In this paper the Wilson nonconforming finite element method is considered to solve a class of two-dimensional second-order elliptic boundary value problems. A new superconvergence property at the vertices and the midpoints of four edges of rectangular meshes is obtained. Received May 5, 1995 / Revised version received November 11, 1996     

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     

A two-level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems

Summary. We present a Lagrange multiplier based two-level domain decomposition method for solving iteratively large-scale systems of equations arising from the finite element discretization of high-frequency exterior Helmholtz problems. The proposed method is essentially an extension of the regularized FETI (Finite Element Tearing and Interconnecting) method to indefinite problems. Its two key ingredients are the regularization of each subdomain matrix by a complex interface lumped mass matrix, and the preconditioning of the interface problem by an auxiliary coarse problem constructed to enforce at each iteration the orthogonality of the residual to a set of carefully chosen planar waves. We show numerically that the proposed method is scalable with respect to the mesh size, the subdomain size, and the wavenumber. We report performance results for a submarine application that highlight the efficiency of the proposed method for the solution of high frequency acoustic scattering problems discretized by finite elements. Received March 17, 1998 / Revised version received June 7, 1999 / Published online January 27, 2000     

Overlapping Schwarz methods for Maxwell's equations in three dimensions

Summary. A two-level overlapping Schwarz method is considered for a Nédélec finite element approximation of 3D Maxwell's equations. For a fixed relative overlap, the condition number of the method is bounded, independently of the mesh size of the triangulation and the number of subregions. Our results are obtained with the assumption that the coarse triangulation is quasi-uniform and, for the Dirichlet problem, that the domain is convex. Our work generalizes well–known results for conforming finite elements for second order elliptic scalar equations. Numerical results for one and two-level algorithms are also presented. Received November 11, 1997 / Revised version received May 26, 1999 / Published online June 21, 2000     

Superconvergence analysis and error expansion for the Wilson nonconforming finite element

Summary. In this paper the Wilson nonconforming finite element is considered for solving a class of two-dimensional second-order elliptic boundary value problems. Superconvergence estimates and error expansions are obtained for both uniform and non-uniform rectangular meshes. A new lower bound of the error shows that the usual error estimates are optimal. Finally a discussion on the error behaviour in negative norms shows that there is generally no improvement in the order by going to weaker norms. Received July 5, 1993     

On the connection between some linear triangular Reissner-Mindlin plate bending elements

Summary. We consider three triangular plate bending elements for the Reissner-Mindlin model. The elements are the MIN3 element of Tessler and Hughes [19], the stabilized MITC3 element of Brezzi, Fortin and Stenberg [5] and the T3BL element of Xu, Auricchio and Taylor [2, 17, 20]. We show that the bilinear forms of the stabilized MITC3 and MIN3 elements are equivalent and that their implementation may be simplified by using numerical integration of reduced order. The T3BL element is shown to be essentially the same as the MIN3 and stabilized MITC3 elements with reduced integration. We finally introduce a general stabilized finite element formulation which covers all three methods. For this class of methods we prove the stability and optimal convergence properties. Received November 4, 1996 / Revised version received May 29, 1997 / Published online January 27, 2000     

Interior estimates for nonconforming finite element methods

Summary. Interior error estimates are derived for a wide class of nonconforming finite element methods for second order scalar elliptic boundary value problems. It is shown that the error in an interior domain can be estimated by three terms: the first one measures the local approximability of the finite element space to the exact solution, the second one measures the degree of continuity of the finite element space (the consistency error), and the last one expresses the global effect through the error in an arbitrarily weak Sobolev norm over a slightly larger domain. As an application, interior superconvergences of some difference quotients of the finite element solution are obtained for the derivatives of the exact solution when the mesh satisfies some translation invariant condition. Received December 29, 1994