A Cascadic Multigrid Algorithm for Semilinear Indefinite Elliptic Problems

We propose a cascadic multigrid algorithm for a semilinear indefinite elliptic problem. We use a standard finite element discretization with piecewise linear finite elements. The arising nonlinear equations are solved by a cascadic organization of Newton's method with frozen derivative on a sequence of nested grids. This gives a simple version of a multigrid method without projections on coarser grids. The cascadic multigrid algorithm starts on a comparatively coarse grid where the number of unknowns is small enough to obtain an approximate solution within sufficiently high precision without substantial computational effort. On each finer grid we perform exactly one Newton step taking the approximate solution from the coarsest grid as initial guess. The linear Newton systems are solved iteratively by a Jacobi-type iteration with special parameters using the approximate solution from the previous grid as initial guess. We prove that for a sufficiently fine initial grid and for a sufficiently good start approximation the algorithm yields an approximate solution within the discretization error on the finest grid and that the method has multigrid complexity with logarithmic multiplier. Received February 1999, revised July 13, 1999     

A Dynamic Method for Weighted Linear Least Squares Problems

A new method for solving the weighted linear least squares problems with full rank is proposed. Based on the theory of Liapunov's stability, the method associates a dynamic system with a weighted linear least squares problem, whose solution we are interested in and integrates the former numerically by an A-stable numerical method. The numerical tests suggest that the new method is more than comparative with current conventional techniques based on the normal equations. Received August 4, 2000; revised August 29, 2001 Published online April 25, 2002     

Incomplete Block Triangular Decompositions of Order l

In this paper, we present a special technique for improving the robustness of block triangular decompositions, for example those described in [1], that have proved their efficiency as preconditioners for the conjugate gradient method in a wide class of problems. The thorough theoretical analysis of this technique is carried out for the model problem, and the practical efficiency in the case of more complex problems is illustrated by numerical examples. Received August 2, 1999; revised September 21, 1999     

A Multigrid Method for Nonconforming FE-Discretisations with Application to Non-Matching Grids

Nonconforming finite element discretisations require special care in the construction of the prolongation and restriction in the multigrid process. In this paper, a general scheme is proposed, which guarantees the approximation property. As an example, the technique is applied to the discretisation by non-matching grids (mortar elements). Received: October 15, 1998     

Extension of the Thomas Algorithm to a Class of Algebraic Linear Equation Systems Involving Quasi-Block-Tridiagonal Matrices with Isolated Block-Pentadiagonal Rows, Assuming Variable Block Dimensions

Received July 17, 2000; revised January 31, 2001     

A Finite Element-Boundary Element Algorithm for Inhomogeneous Boundary Value Problems

Received January 25, 2001; revised July 17, 2001     

Variable Additive Preconditioning Procedures

Iterative methods with variable preconditioners of additive type are proposed. The scaling factors of each summand in the additive preconditioners are optimized within each iteration step. It is proved that the presented methods converge at least as fast as the Richardson's iterative method with the corresponding additive preconditioner with optimal scaling factors. In the presented numerical experiments the suggested methods need nearly the same number of iterations as the usual preconditioned conjugate gradient method with the corresponding additive preconditioner with numerically determined fixed optimal scaling factors. Received: June 10, 1998; revised October 16, 1998     

A Black-Box Iterative Solver Based on a Two-Level Schwarz Method

We propose a black-box parallel iterative method suitable for solving both elliptic and certain non-elliptic problems discretized on unstructured meshes. The method is analyzed in the case of the second order elliptic problems discretized on quasiuniform P1 and Q1 finite element meshes. The numerical experiments confirm the validity of the proved convegence estimate and show that the method can successfully be used for more difficult problems (e.g. plates, shells and Helmholtz equation in high-frequency domain.) Received: July 28, 1997; revised June 20, 1999     

On the Convergence of a Multigrid Method for Linear Reaction-Diffusion Problems

In this note we consider discrete linear reaction-diffusion problems. For the discretization a standard conforming finite element method is used. For the approximate solution of the resulting discrete problem a multigrid method with a damped Jacobi or symmetric Gauss-Seidel smoother is applied. We analyze the convergence of the multigrid V- and W-cycle in the framework of the approximation- and smoothing property. The multigrid method is shown to be robust in the sense that the contraction number can be bounded by a constant smaller than one which does not depend on the mesh size or on the diffusion-reaction ratio. Received June 15, 2000     

Descent Iterations for Improving Approximate Eigenpairs of Polynomial Eigenvalue Problems with General Complex Matrices

In this paper, we consider descent iterations with line search for improving an approximate eigenvalue and a corresponding approximate eigenvector of polynomial eigenvalue problems with general complex matrices, where an approximate eigenpair was obtained by some method. The polynomial eigenvalue problem is written as a system of complex nonlinear equations with nondifferentiable normalized condition. Convergence theorems for iterations are established. Finally, some numerical examples are presented to demonstrate the effectiveness of the iterative methods. Received April 9, 2001; revised October 2, 2001 Published online February 18, 2002     

A Robust Smoother for Convection-Diffusion Problems with Closed Characteristics

In this paper we analyze a model problem for the convection-diffusion equation where the reduced problem has closed characteristics. A full upwinding finite difference scheme is used to discretize the problem. Additionally to the strength of the convection, an arbitrary amount of crosswind-diffusion can be added on the discrete level. We present a smoother which is robust w.r.t. the strength of convection and the amount of crosswind-diffusion. It is of Gauss–Seidel type using a downwind ordering. To handle the cyclic dependencies a frequency-filtering algorithm is used. The algorithm is of nearly optimal complexity ?(n log n). It is proved that it fulfills a robust smoothing property.     

Condition Numbers of Approximate Schur Complements in Two- and Three-Dimensional Discretizations on Hierarchically Ordered Grids

We investigate multilevel incomplete factorizations of M-matrices arising from finite difference discretizations. The nonzero patterns are based on special orderings of the grid points. Hence, the Schur complements that result from block elimination of unknowns refer to a sequence of hierarchical grids. Having reached the coarsest grid, Gaussian elimination yields a complete decomposition of the last Schur complement. The main focus of this paper is a generalization of the recursive five-point/nine-point factorization method (which can be applied in two-dimensional problems) to matrices that stem from discretizations on three-dimensional cartesian grids. Moreover, we present a local analysis that considers fundamental grid cells. Our analysis allows to derive sharp bounds for the condition number associated with one factorization level (two-grid estimates). A comparison in case of the Laplace operator with Dirichlet boundary conditions shows: Estimating the relative condition number of the multilevel preconditioner by multiplying corresponding two-grid values gives the asymptotic bound O(h ^−0.347) for the two- respectively O(h ^−4/5) for the three-dimensional model problem. Received October 19, 1998; revised September 27, 1999     

Energy Optimization of Algebraic Multigrid Bases

We propose a fast iterative method to optimize coarse basis functions in algebraic multigrid by minimizing the sum of their energies, subject to the condition that linear combinations of the basis functions equal to given zero energy modes, and subject to restrictions on the supports of the coarse basis functions. For a particular selection of the supports, the first iteration gives exactly the same basis functions as our earlier method using smoothed aggregation. The convergence rate of the minimization algorithm is bounded independently of the mesh size under usual assumptions on finite elements. The construction is presented for scalar problems as well as for linear elasticity. Computational results on difficult industrial problems demonstrate that the use of energy minimal basis functions improves algebraic multigrid performance and yields a more robust multigrid algorithm than smoothed aggregation. Received: March 9, 1998; revised January 25, 1999     

Non-Nested Multi-Level Solvers for Finite Element Discretisations of Mixed Problems

We consider a general framework for analysing the convergence of multi-grid solvers applied to finite element discretisations of mixed problems, both of conforming and nonconforming type. As a basic new feature, our approach allows to use different finite element discretisations on each level of the multi-grid hierarchy. Thus, in our multi-level approach, accurate higher order finite element discretisations can be combined with fast multi-level solvers based on lower order (nonconforming) finite element discretisations. This leads to the design of efficient multi-level solvers for higher order finite element discretisations. Received May 17, 2001; revised February 2, 2002 Published online April 25, 2002     

Robust Multigrid Methods for Nearly Incompressible Elasticity

We consider multigrid methods for problems in linear elasticity which are robust with respect to the Poisson ratio. Therefore, we consider mixed approximations involving the displacement vector and the pressure, where the pressure is approximated by discontinuous functions. Then, the pressure can be eliminated by static condensation. The method is based on a saddle point smoother which was introduced for the Stokes problem and which is transferred to the elasticity system. The performance and the robustness of the multigrid method are demonstrated on several examples with different discretizations in 2D and 3D. Furthermore, we compare the multigrid method for the saddle point formulation and for the condensed positive definite system. Received February 5, 1999; revised October 5, 1999     

Nitsche Type Mortaring for some Elliptic Problem with Corner Singularities

The paper deals with Nitsche type mortaring as a finite element method (FEM) for treating non-matching meshes of triangles at the interface of some domain decomposition. The approach is applied to the Poisson equation with Dirichlet boundary conditions (as a model problem) under the aspect that the interface passes re-entrant corners of the domain. For such problems and non-matching meshes with and without local refinement near the re-entrant corner, some properties of the finite element scheme and error estimates are proved. They show that appropriate mesh grading yields convergence rates as known for the classical FEM in presence of regular solutions. Finally, a numerical example illustrates the approach and the theoretical results. Received July 5, 2001; revised February 5, 2002 Published online April 25, 2002     

A Coupled Multigrid Method for Nonconforming Finite Element Discretizations of the 2D-Stokes Equation

This paper investigates a multigrid method for the solution of the saddle point formulation of the discrete Stokes equation obtained with inf–sup stable nonconforming finite elements of lowest order. A smoother proposed by Braess and Sarazin (1997) is used and L ²-projection as well as simple averaging are considered as prolongation. The W-cycle convergence in the L ²-norm of the velocity with a rate independently of the level and linearly decreasing with increasing number of smoothing steps is proven. Numerical tests confirm the theoretically predicted results. Received January 19, 1999; revised September 13, 1999     

The Inf-Sup Condition for the Mapped Q k ?P k?1 disc Element in Arbitrary Space Dimensions

 One of the most popular pairs of finite elements for solving mixed formulations of the Stokes and Navier–Stokes problem is the Q _k −P _k−1 ^disc element. Two possible versions of the discontinuous pressure space can be considered: one can either use an unmapped version of the P _k−1 ^disc space consisting of piecewise polynomial functions of degree at most k−1 on each cell or define a mapped version where the pressure space is defined as the image of a polynomial space on a reference cell. Since the reference transformation is in general not affine but multilinear, the two variants are not equal on arbitrary meshes. It is well-known, that the inf-sup condition is satisfied for the first variant. In the present paper we show that the latter approach satisfies the inf-sup condition as well for k≥2 in any space dimension. Received January 31, 2001; revised May 2, 2002 Published online: July 26, 2002     

Multilevel Stabilization of Convection–Diffusion Problems by Variable-Order Inner Products

We are concerned with the task of stabilizing discrete approximations to convection–diffusion problems. We propose to consistently modify the exact variational formulation of the problem by adding a fractional order inner product, involving the residual of the equation. The inner product is expressed through a multilevel decomposition of its arguments, in terms of components along a multiscale basis. The order of the inner product locally varies from −1/2 to −1, depending on the value of a suitably-defined multiscale Péclet number. Numerical approximations obtained via the Galerkin method applied to the modified formulation are analyzed. Received January 1, 2000; revised November 2, 2000