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     

A cascadic multigrid algorithm for the Stokes equations

A variant of multigrid schemes for the Stokes problem is discussed. In particular, we propose and analyse a cascadic version for the Stokes problem. The analysis of the transfer between the grids requires special care in order to establish that the complexity is the same as that for classical multigrid algorithms. Received September 10, 1997 / Revised version received February 20, 1998     

Numerical verification of solutions for variational inequalities

In this paper, we consider a numerical technique that enables us to verify the existence of solutions for variational inequalities. This technique is based on the infinite dimensional fixed point theorems and explicit error estimates for finite element approximations. Using the finite element approximations and explicit a priori error estimates for obstacle problems, we present an effective verification procedure that through numerical computation generates a set which includes the exact solution. Further, a numerical example for an obstacle problem is presented. Received October 28,1996 / Revised version received December 29,1997     

On constrained Newton linearization and multigrid for variational inequalities

Summary. We consider the fast solution of a class of large, piecewise smooth minimization problems. For lack of smoothness, usual Newton multigrid methods cannot be applied. We propose a new approach based on a combination of convex minization with constrained Newton linearization. No regularization is involved. We show global convergence of the resulting monotone multigrid methods and give polylogarithmic upper bounds for the asymptotic convergence rates. Efficiency is illustrated by numerical experiments. Received March 22, 1999 / Revised version received February 24, 2001 / Published online October 17, 2001     

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     

Rate of Convergence for some constraint decomposition methods for nonlinear variational inequalities

Summary. Some general subspace correction algorithms are proposed for a convex optimization problem over a convex constraint subset. One of the nontrivial applications of the algorithms is the solving of some obstacle problems by multilevel domain decomposition and multigrid methods. For domain decomposition and multigrid methods, the rate of convergence for the algorithms for obstacle problems is of the same order as the rate of convergence for jump coefficient linear elliptic problems. In order to analyse the convergence rate, we need to decompose a finite element function into a sum of functions from the subspaces and also satisfying some constraints. A special nonlinear interpolation operator is introduced for decomposing the functions. Received December 13, 2001 / Revised version received February 19, 2002 / Published online June 17, 2002 This work was partially supported by the Norwegian Research Council under projects 128224/431 and SEP-115837/431.     

Error estimates for the approximation of semicoercive variational inequalities

Summary. An abstract error estimate for the approximation of semicoercive variational inequalities is obtained provided a certain condition holds for the exact solution. This condition turns out to be necessary as is demonstrated analytically and numerically. The results are applied to the finite element approximation of Poisson's equation with Signorini boundary conditions and to the obstacle problem for the beam with no fixed boundary conditions. For second order variational inequalities the condition is always satisfied, whereas for the beam problem the condition holds if the center of forces belongs to the interior of the convex hull of the contact set. Applying the error estimate yields optimal order of convergence in terms of the mesh size . The numerical convergence rates observed are in good agreement with the predicted ones. Received August 16, 1993 / Revised version received March 21, 1994     

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     

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     

Fourier analysis of a robust multigrid method for convection-diffusion equations

Summary. We consider a two-grid method for solving 2D convection-diffusion problems. The coarse grid correction is based on approximation of the Schur complement. As a preconditioner of the Schur complement we use the exact Schur complement of modified fine grid equations. We assume constant coefficients and periodic boundary conditions and apply Fourier analysis. We prove an upper bound for the spectral radius of the two-grid iteration matrix that is smaller than one and independent of the mesh size, the convection/diffusion ratio and the flow direction; i.e. we have a (strong) robustness result. Numerical results illustrating the robustness of the corresponding multigrid -cycle are given. Received October 14, 1994     

Convergence of algebraic multigrid based on smoothed aggregation

Summary. We prove an abstract convergence estimate for the Algebraic Multigrid Method with prolongator defined by a disaggregation followed by a smoothing. The method input is the problem matrix and a matrix of the zero energy modes of the same problem but with natural boundary conditions. The construction is described in the case of a general elliptic system. The condition number bound increases only as a polynomial of the number of levels, and requires only a uniform weak approximation property for the aggregation operators. This property can be a-priori verified computationally once the aggregates are known. For illustration, it is also verified here for a uniformly elliptic diffusion equations discretized by linear conforming quasiuniform finite elements. Only very weak and natural assumptions on the hierarchy of aggregates are needed. Received March 1, 1998 / Revised version received January 28, 2000 / Published online: December 19, 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     

Multiple solutions of hemivariational inequalities with area-type term

Hemivariational inequalities containing both an area-type and a non-locally Lipschitz term are considered. Multiplicity results are obtained by means of techniques of nonsmooth critical point theory. Received: December 24, 1998 / Accepted: October 1, 1999     

Effect of numerical integration for elliptic obstacle problems

Summary. An elliptic obstacle problem is approximated by piecewise linear finite elements with numerical integration on the penalty and forcing terms. This leads to diagonal nonlinearities and thereby to a practical scheme. Optimal error estimates in the maximum norm are derived. The proof is based on constructing suitable super and subsolutions that exploit the special structure of the penalization, and using quite precise pointwise error estimates for an associated linear elliptic problem with quadrature via the discrete maximum principle. Received March 19, 1993     

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     

Wavelet adaptive method for second order elliptic problems: boundary conditions and domain decomposition

Summary. Wavelet methods allow to combine high order accuracy, multilevel preconditioning techniques and adaptive approximation, in order to solve efficiently elliptic operator equations. One of the main difficulty in this context is the efficient treatment of non-homogeneous boundary conditions. In this paper, we propose a strategy that allows to append such conditions in the setting of space refinement (i.e. adaptive) discretizations of second order problems. Our method is based on the use of compatible multiscale decompositions for both the domain and its boundary, and on the possibility of characterizing various function spaces from the numerical properties of these decompositions. In particular, this allows the construction of a lifting operator which is stable for a certain range of smoothness classes, and preserves the compression of the solution in the wavelet basis. An explicit construction of the wavelet bases and the lifting is proposed on fairly general domains, based on conforming domain decomposition techniques. Received November 2, 1998 / Published online April 20, 2000     

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     

Consistency,stability, a priori and a posteriori errors for Petrov-Galerkin methods applied to nonlinear problems

Summary. In an abstract framework we present a formalism which specifies the notions of consistency and stability of Petrov-Galerkin methods used to approximate nonlinear problems which are, in many practical situations, strongly nonlinear elliptic problems. This formalism gives rise to a priori and a posteriori error estimates which can be used for the refinement of the mesh in adaptive finite element methods applied to elliptic nonlinear problems. This theory is illustrated with the example: in a two dimensional domain with Dirichlet boundary conditions. Received June 10, 1992 / Revised version received February 28, 1994     

Finite element analysis of varitional crimes for a quasilinear elliptic problem in 3D

Summary. We examine a finite element approximation of a quasilinear boundary value elliptic problem in a three-dimensional bounded convex domain with a smooth boundary. The domain is approximated by a polyhedron and a numerical integration is taken into account. We apply linear tetrahedral finite elements and prove the convergence of approximate solutions on polyhedral domains in the -norm to the true solution without any additional regularity assumptions. Received May 23, 1997 / Published online December 6, 1999