Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains

Summary. Three iterative domain decomposition methods are considered: simultaneous updates on all subdomains (Additive Schwarz Method), flow directed sweeps and double sweeps. By using some techniques of formal language theory we obtain a unique criterion of convergence for the three methods. The convergence rate is a function of the criterion and depends on the algorithm. Received October 24, 1994 / Revised version received November 27, 1995     

Monotone multigrid methods for elliptic variational inequalities II

Summary. We derive globally convergent multigrid methods for discrete elliptic variational inequalities of the second kind as obtained from the approximation of related continuous problems by piecewise linear finite elements. The coarse grid corrections are computed from certain obstacle problems. The actual constraints are fixed by the preceding nonlinear fine grid smoothing. This new approach allows the implementation as a classical V-cycle and preserves the usual multigrid efficiency. We give estimates for the asymptotic convergence rates. The numerical results indicate a significant improvement as compared with previous multigrid approaches. Received March 26, 1994 / Revised version received September 22, 1994     

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     

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     

A numerical approach to variational problems subject to convexity constraint

Summary. We describe an algorithm to approximate the minimizer of an elliptic functional in the form on the set of convex functions u in an appropriate functional space X. Such problems arise for instance in mathematical economics [4]. A special case gives the convex envelope of a given function . Let be any quasiuniform sequence of meshes whose diameter goes to zero, and the corresponding affine interpolation operators. We prove that the minimizer over is the limit of the sequence , where minimizes the functional over . We give an implementable characterization of . Then the finite dimensional problem turns out to be a minimization problem with linear constraints. Received November 24, 1999 / Published online October 16, 2000     

On the use of rational iterations and domain decomposition methods for the Helmholtz problem

An iterative algorithm for the numerical solution of the Helmholtz problem is considered. It is difficult to solve the problem numerically, in particular, when the imaginary part of the wave number is zero or small. We develop a parallel iterative algorithm based on a rational iteration and a nonoverlapping domain decomposition method for such a non-Hermitian, non-coercive problem. Algorithm parameters (artificial damping and relaxation) are introduced to accelerate the convergence speed of the iteration. Convergence analysis and effective strategies for finding efficient algorithm parameters are presented. Numerical results carried out on an nCUBE2 are given to show the efficiency of the algorithm. To reduce the boundary reflection, we employ a hybrid absorbing boundary condition (ABC) which combines the first-order ABC and the physical $Q$ ABC. Computational results comparing the hybrid ABC with non-hybrid ones are presented. Received May 19, 1994 / Revised version received March 25, 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     

Multilevel ILU decomposition

Summary. In this paper, the multilevel ILU (MLILU) decomposition is introduced. During an incomplete Gaussian elimination process new matrix entries are generated such that a special ordering strategy yields distinct levels. On these levels, some smoothing steps are computed. The MLILU decomposition exists and the corresponding iterative scheme converges for all symmetric and positive definite matrices. Convergence rates independent of the number of unknowns are shown numerically for several examples. Many numerical experiments including unsymmetric and anisotropic problems, problems with jumping coefficients as well as realistic problems are presented. They indicate a very robust convergence behavior of the MLILU method. Received June 13, 1997 / Revised version received March 17, 1998     

An inexactQP-based method for nonlinear complementarity problems

Summary. We consider a quadratic programming-based method for nonlinear complementarity problems which allows inexact solutions of the quadratic subproblems. The main features of this method are that all iterates stay in the feasible set and that the method has some strong global and local convergence properties. Numerical results for all complementarity problems from the MCPLIB test problem collection are also reported. Received February 24, 1997 / Revised version received September 5, 1997     

Convergence of block two-stage iterative methods for symmetric positive definite systems

Summary. We study the convergence of two-stage iterative methods for solving symmetric positive definite (spd) systems. The main tool we used to derive the iterative methods and to analyze their convergence is the diagonally compensated reduction (cf. [1]). Received December 11, 1997 / Revised version received March 25, 1999 / Published online May 30, 2001     

Error estimate for a stabilised domain decomposition method with nonmatching grids

Summary. In this paper, we analyse a stabilisation technique for the so-called three-field formulation for nonoverlapping domain decomposition methods. The stabilisation is based on boundary bubble functions in each subdomain which are then eliminated by static condensation. The discretisation grids in the subdomains can be chosen independently as well as the grid for the final interface problem. We present the analysis of the method and we construct a set of bubble functions which guarantees the optimal rate of convergence. Received May 12, 1998 / Revised version received November 21, 2000 / Published online June 7, 2001     

Domain decomposition iterative procedures for solving scalar waves in the frequency domain

The propagation of dispersive waves can be modeled relevantly in the frequency domain. A wave problem in the frequency domain is difficult to solve numerically. In addition to having a complex–valued solution, the problem is neither Hermitian symmetric nor coercive in a wide range of applications in Geophysics or Quantum–Mechanics. In this paper, we consider a parallel domain decomposition iterative procedure for solving the problem by finite differences or conforming finite element methods. The analysis includes the decomposition of the domain into either the individual elements or larger subdomains ( of finite elements). To accelerate the speed of convergence, we introduce relaxation parameters on the subdomain interfaces and an artificial damping iteration. The convergence rate of the resulting algorithm turns out to be independent on the mesh size and the wave number. Numerical results carried out on an nCUBE2 parallel computer are presented to show the effectiveness of the method. Received October 30, 1995 / Revised version received January 10, 1997     

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     

On the numerical analysis of non-convex variational problems

Summary. We discuss a numerical method for finding Young-measure-valued minimizers of non-convex variational problems. To have any hope of a convergence theorem, one must work in a setting where the minimizer is unique and minimizing sequences converge strongly. This paper has two main goals: (i) we specify a method for producing strongly-convergent minimizing sequences, despite the failure of strict convexity; and (ii) we show how uniqueness of the Young measure can be parlayed into a numerical convergence theorem. The treatment of (ii) is done in the setting of two model problems, one involving scalar valued functions and a multiwell energy, the other from micromagnetics. Received July 29, 1995     

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     

Improved smoothing-type methods for the solution of linear programs

Summary. We consider a smoothing-type method for the solution of linear programs. Its main idea is to reformulate the primal-dual optimality conditions as a nonlinear and nonsmooth system of equations, and to apply a Newton-type method to a smooth approximation of this nonsmooth system. The method presented here is a predictor-corrector method, and is closely related to some methods recently proposed by Burke and Xu on the one hand, and by the authors on the other hand. However, here we state stronger global and/or local convergence properties. Moreover, we present quite promising numerical results for the whole netlib test problem collection. Received August 9, 2000 / Revised version received September 28, 2000 / Published online June 7, 2001     

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     

Multigrid methods for a parameter dependent problem in primal variables

Summary. In this paper we consider multigrid methods for the parameter dependent problem of nearly incompressible materials. We construct and analyze multilevel-projection algorithms, which can be applied to the mixed as well as to the equivalent, non-conforming finite element scheme in primal variables. For proper norms, we prove that the smoothing property and the approximation property hold with constants that are independent of the small parameter. Thus we obtain robust and optimal convergence rates for the W-cycle and the variable V-cycle multigrid methods. The numerical results pretty well conform the robustness and optimality of the multigrid methods proposed. Received June 17, 1998 / Revised version received October 26, 1998 / Published online September 7, 1999     

Strictly feasible equation-based methods for mixed complementarity problems

Summary.   We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively complicated subproblems (like quadratic programs or linear complementarity problems), or they have relatively simple subproblems (like linear systems of equations) but generate not necessarily feasible iterates. The method to be presented here combines the nice features of these two classes of methods: It has to solve only one linear system of equations (of reduced dimension) at each iteration, and it generates feasible (more precisely: strictly feasible) iterates. The new method has some nice global and local convergence properties. Some preliminary numerical results will also be given. Received August 26, 1999 / Revised version recived April 11, 2000 / Published online February 5, 2001