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 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     

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     

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     

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     

Tensor Product Multigrid for Maxwell's Equation with Aligned Anisotropy

When simulating electromagnetic phenomena in symmetric cavities, it is often possible to exploit the symmetry in order to reduce the dimension of the problem, thereby reducing the amount of work necessary for its numerical solution. Usually, this reduction leads not only to a much lower number of unknowns in the discretized system, but also changes the behaviour of the coefficients of the differential operator in an unfavourable way, usually leading to the transformed system being not elliptic with respect to norms corresponding to two-dimensional space, thus limiting the use of standard multigrid techniques. In this paper, we introduce a robust multigrid method for Maxwell's equation in two dimensions that is especially suited for coefficients resulting from coordinate transformations, i.e. that are aligned with the coordinate axes. Using a variant of the technique introduced in [5], we can prove robustness of the multigrid method for domains of tensor-product structure and coefficients depending on only one of the coordinates. Received July 17, 2000; revised October 27, 2000     

Homogenization and Multigrid

For elliptic partial differential equations with periodically oscillating coefficients which may have large jumps, we prove robust convergence of a two-grid algorithm using a prolongation motivated by the theory of homogenization. The corresponding Galerkin operator on the coarse grid turns out to be a discretization of a diffusion operator with homogenized coefficients obtained by solving discrete cell problems. This two-grid method is then embedded inside a multi-grid cycle extending over both the fine and the coarse scale. Received August 10, 1999; revised July 28, 2000     

A Subspace Cascadic Multigrid Method for Mortar Elements

A cascadic multigrid (CMG) method for elliptic problems with strong material jumps is proposed and analyzed. Non–matching grids at interfaces between subdomains are allowed and treated by mortar elements. The arising saddle point problems are solved by a subspace confined conjugate gradient method as smoother for the CMG. Details of algorithmic realization including adaptivity are elaborated. Numerical results illustrate the efficiency of the new subspace CMG algorithm. Received December 14, 2001; revised September 2, 2002 Published online: November 18, 2002     

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     

A Multigrid Approach for Minimizing a Nonlinear Functional for Digital Image Matching

In this paper, we consider a multigrid application in digital image processing. Here, the problem is to find a map, which transforms an image T into another image R such that the grey level of the different images are nearly equal in every picture-element. This problem arises in the investigation of human brains. The complete inverse problem is ill posed in the sense of Hadamard and nonlinear, so the numerical solution is quite difficult. We solve the inverse problem by a Landweber iteration. In each minimization step an approximate solution for the linearized problem is computed with a multigrid method as an inner iteration. Finally, we present some experimental results for synthetic and real images. Received December 30, 1998; revised August 16, 1999     

Semi-Unstructured Grids

We present a novel automatic grid generator for the finite element discretization of partial differential equations in 3D. The grids constructed by this grid generator are composed of a pure tensor product grid in the interior of the domain and an unstructured grid which is only contained in boundary cells. The unstructured component consists of tetrahedra, each of which satisfies a maximal interior angle condition. By suitable constructing the boundary cells, the number of types of boundary subcells is reduced to 12 types. Since this grid generator constructs large structured grids in the interior and small unstructured grids near the boundary, the resulting semi-unstructured grids have similar properties as structured tensor product grids. Some appealing properties of this method are computational efficiency and natural construction of coarse grids for multilevel algorithms. Numerical results and an analysis of the discretization error are presented. Received July 17, 2000; revised October 27, 2000     

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 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     

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     

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     

A Class of Smoothers for Saddle Point Problems

In this paper smoothing properties are shown for a class of iterative methods for saddle point problems with smoothing rates of the order 1/m, where m is the number of smoothing steps. This generalizes recent results by Braess and Sarazin, who could prove this rates for methods where, in the context of the Stokes problem, the pressure correction equation is solved exactly, which is not needed here. Received December 4, 1998; revised April 14, 2000     

High Accuracy Analysis of the Adini's Nonconforming Element

Received September 14, 2000; revised September 25, 2001     

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

Received January 25, 2001; revised July 17, 2001     

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.     

Problem Dependent Generalized Prewavelets

In this paper, we present a new approach to construct robust multilevel algorithms for elliptic differential equations. The multilevel algorithms consist of multiplicative subspace corrections in spaces spanned by problem dependent generalized prewavelets. These generalized prewavelets are constructed by a local orthogonalization of hierarchical basis functions with respect to a so-called local coarse-grid space. Numerical results show that the local orthogonalization leads to a smaller constant in strengthened Cauchy-Schwarz inequality than the original hierarchical basis functions. This holds also for several equations with discontinuous coefficients. Thus, the corresponding multilevel algorithm is a fast and robust iterative solver. Received November 13, 2001; revised October 21, 2002 Published online: December 12, 2002