Skip to main content



A robust preconditioner based on algebraic substructuring and two-level grids

A domain decomposition method is used to construct a new type of block matrix incomplete factorization method. The properties of this method are such that it can be used as an efficient (i.e. with low computational complexity) and robust, corrector on a coarse mesh. Since the cost of it is of optimal order of computational complexity there is no need to use any further levels of grids as it is in a classical multigrid method. Combined with a smoother on the fine mesh the method turns out to perform as well on difficult problems as on model type problems and with a complexity about as low as that for a classical multigrid method on the model problems. The method is well suited for vector- and parallel Computers. The smoothing-correction forms a V-cycle step which can be used as a preconditioner for a conjugate gradient method, thus guaranteeing convergence. However, the method is so efficient that there is rarely any need for convergence acceleration.
O. Axelsson, B. Polman

Adaptive Multigrid Solution of the Convection-Diffusion Equation on the Dirmu Multiprocessor

The two-dimensional convection-diffusion equation is solved using a nested iteration multigrid scheme with local grid refinement on a parallel Computer with distributed shared memory. The adaptive grid refinement is based on estimates of local truncation errors. An array of processors is used; the grids on all levels are subdivided equally amongst all processors. The parallel efficiencies obtained range from 57% to 81%.
P. Bastian, J. H. Ferziger, G. Horton, J. Volkert

Finite Volume Multigrid Solutions of the Two-Dimensional Incompressible Navier-Stokes-Equations

A multigrid scheme for solving the two-dimensional, laminar, incompressible Navier-Stokes equations is presented. It uses V-cycles in a nested iteration scheme and full approximation storage. The iterative SIMPLE algorithm is employed to relax the coupled momentum and continuity equations. Within the SIMPLE algorithm, linear Systems are solved with an ILU factorization method. The multigrid scheme is extended to handle local grid refinement, with the refinement based on estimates of local truncation errors. Results are reported for backward facing step flows at various Reynolds numbers.
C. Becker, J. H. Ferziger, M. Perić, G. Scheuerer

Concepts for a Dimension Independent Application of Multigrid Algorithms to Semiconductor Device Simulation

The Solution of semiconductor device equations requires fast and flexible numerical algorithms. It is shown that a program construction based on multigrid methods combined with structured programming techniques helps to overcome the computational bottleneck apparent in 3 dimensional problems. In our approach, modified classical multigrid methods have been incorporated into a program using a tree structured data Organization. Thus, a space dimension independent formulation of grid transfer Operations and adaptive grid refinement techniques can be introduced. The program code is independent of the domain configuration as well as the problem dimension. This flexibility is inherent in the underlying data structure which is operated and manipulated by the program.
P. Conradi, D. Schröder

Algebraic Multigrid Methods and the Schur Complement

In this paper we propose and discuss a general purely algebraic framework for multilevel iterative schemes for solving linear Systems where the role of the ‘coarse grid’ Operators is played by Schur complements.
Wolfgang Dahmen, Ludwig Elsner

A Multigrid Method for Steady Euler Equations, Based on Flux-Difference Splitting with Respect to Primitive Variables

A flux-difference Splitting method for steady Euler equations, resulting in a Splitting with respect to primitive variables is introduced. This Splitting is applied to finite volumes centered around the vertices of the computational grid. The discrete set of equations is both conservative and positive.
Due to the positivity, the solution can be obtained by collective variants of relaxation methods, that can be brought into multigrid form. Two full multigrid methods are presented. As restriction operator, both use full weighting within the flow field and injection at the boundaries. Bilinear interpellation is used as prolongation. The cycle is of V7-type. The first method uses symmetric successive underrelaxation, while the second uses Jacobi-iteration. In terms of cycles, the successive formulation is the most efficient while in terms of computer time, due to the vectorizability the second formulation is most efficient.
Due to the conservativity, the algebraically exact flux-difference splitting and the positivity, the solution for transonic flow shows shocks represented as sharp discontinuities, without wiggles.
E. Dick

Treatment of Singular Perturbation Problems with Multigrid Methods

The combination of several components of multigrid algorithms has been tested for the Solution of singular perturbation problems. 1- and 2-dimensional linear problems were considered. An algorithm has been found heuristically for which the usual lower bound for the spectral radius of the iteration matrix of 1/2 does not hold. Artificial viscosity is used to obtain a stable discretisation. The algorithm is discussed and numerical results are presented.
Joachim H. Dörfer

The Frequency Decomposition Multi-Grid Algorithm

Multi-grid methods are known as very fast solvers of a large class of discretised partial differential equations. However, the multi-grid method cannot be understood as a fixed algorithm. Usually, the components of the multi-grid iteration have to be adapted to the given problem and sometimes the problems are modified into those acceptable for multi-grid methods. In particular, the smoothing iteration is the most delicate part of the multi-grid process.
An iteration is called a robust one, if it works for a sufficiently large class of problems. Attempts have been made to construct robust multi-grid iterations by means of sophisticated smoothing processes (cf. Wesseling [6], [3, p.222]). In particular, robust methods should be able to solve singular perturbation problems. Examples of such problems are the anisotropic equations of the next subsection, the convection-diffusion equation and others (cf. Hackbusch [3,§10]).
To overcome the problem of robustness we propose a new multi-grid is called the frequency decomposition multi-grid algorithm since different parts of the frequency spectrum are treated by different respective coarse-grid corrections. This explains that we need more than one coarse grid and further prolongations and restrictions. It is to be emphasized that the smoothing procedure may be very simple (e.g. the GauB-Seidel iteration). Nevertheless, we claim that the resulting multi-grid algorithm is suited not only to the anisotropic equations described below but also for many other singular perturbation problems. We describe the application to the anisotropic problem since this simplifies the choice of the prolongations and restrictions. Other applications possibly require the matrix-dependent prolongation (cf. Hackbusch[3,§10.31)
Wolfgang Hackbusch

On Global Multigrid Convergence for Nonlinear Problems

We present a modification of the Nonlinear Multigrid Method. This new algorithm converges globally for nonlinear problems that result from finite element discretization of some class of nonlinear boundary value problems.
W. Hackbusch, A. Reusken

Multigrid Methods for the Solution of the Compressible Navier-Stokes Equations

The numerical Solution of the Navier-Stokes equations requires a large amount of computational work, much more than a corresponding inviscid Solution does. The reason for this is the more complex structure of the Navier-Stokes equations, and mainly the existence of different characteristic length scales which have to be resolved. In the past years a large number of so-called high resolution schemes for the Solution of the Euler equations have been developed and later adjusted to the Navier-Stokes equations e. g. [1, 2, 3]. In general they result in an improved accuracy and efficiency. Nevertheless, for complex viscous flow problems further concepts have to be investigated to improve the convergence. One promising concept is the multigrid method of which the fundamentals were formulated by Brandt [4]. This idea was taken up by many authors for the Solution of the Euler and Navier-Stokes equations as well. Examples for multigrid applications in explicit and implicit Euler Solutions are given by Cima, Johnson [5], Ni [6], Jameson [7] and by Hemker[8], Mulder[9] and others. Navier-Stokes applications can be found e. g. in the paper of Shaw, Wesseling [10], Thomas et al [11] and Schröder, Hänel [12].
D. Hänel, W. Schröder, G. Seider

On Multigrid Methods of the First Kind for Symmetric Boundary Integral Equations of Nonnegative Order

Multigrid methods of the first kind are applied for solving iteratively some Symmetric algebraic Systems that oeeur in the numerical treatment of Symmetrie and strongly elliptic boundary integral eguations of nonnegative order. Using a damped Jacobi relaxation scheine, the iterative method proves to be unconditionally convergent in case of smooth boundaries and, moreover, convergent for a sufficiently large number of smoothing steps in case of general Lipschitz boundaries. As a numerical example, the Neumann problem of the Laplacean is treated by the “first kind” boundary element approach.
F. K. Hebeker

Effective Preconditioning for Spectral Multigrid Methods

Spectral methods employ global polynomials for the approximation of elliptic problems. They give very accurate approximations for smooth Solutions with relatively few degrees of freedom. On the other hand, the matrices involed are full and yield high condition numbers, growing as O(N4) (for polynomials of degree ≤N in each variable). Never-theless the spectral Systems can be efficiently solved using spectral multigrid (SMG) methods. Utilizing FFTs only 0(N2lnN) Operations are necessary for the evaluation of the spectral residual. We investigate effective preconditioners for SMG based on line relaxation techniques and show the robustness of minimal residual relaxation. We also present numerical results for L-shaped regions where the Schwarz alternating procedure has been used.
Wilhelm Heinrichs

Numerical Solution of Transonic Potential Flow in 2D Compressor Cascades using Multi-Grid Techniques

The paper deals with numerical Solution of transonic potential flow in two-dimensional compressor cascades. The governing equation is full potential equation in non-conservative form. The work considers a weak formulation of the probiem; for numerical Solution modified Jameson’s rotated difference scheine is used and to simplify periodical conditions we used the locally disturbance form of the governing equation. The resulting algebraic system of difference equations is solved by:
SLOR method
line relaxation method in three grid-levels
FAS and CS-algorithm using full weighting of non--conservative residue.
Some applications of these several methods applied to transonic cascade flows are compared to other numerical and experimental results
M. Huněk, K. Kozel, M. Vavřincová

Local Mode Smoothing Analysis of Various Incomplete Factorization Iterative Methods

By local mode analysis an infinite domain we can assess the smoothing efficiency of iterative methods based on incomplete factorizations. Our analysis consists of an analytic and numerical study of a simple two-dimensional problem: -εuxx - uyy = f discretized by finite differences. This analysis is done for pointwise and blockwise incomplete factorizations. This study show how this analysis is helpful to obtain simple expressions for the smoothing factors and to introduce new smoothers.
M. Khalil

Multigrid and Defect Correction for the Steady Navier-Stokes Equations

Theoretical and experimental convergence results are presented for multigrid and iterative defect correction applied to finite volume discretizations of the steady, 2D, compressible Navier-Stokes equations. Iterative defect correction is introduced for circumventing the difficulty in finding a soiution of discretized equations with a second- or higher-order accurate convective pari As a smoothing -echnique, use is made of point Gauss-Seidel relaxation with inside the latter, Newton iteration as a basic Solution method. The multigrid echnique appears to be very efficient for smooth as well as non-smooth problems. Iterative defect correction appears to be very efficient for smooth problems only, though still reasonably efficient for non-smooth Problems.
Barry Koren

Towards Multigrid Acceleration of 2D Compressible Navier-Stokes Finite Volume Implicit Schemes

A multigrid Solution of the twodimensional compressible Navier-Stokes equations is described. The method rests on the non linear FAS multigrid procedure. Implicit upwind schemes are used as relaxation schemes. This method allows the computation of oscillation-free shocks without the need of introducing artiticial viscosity. Results are presented on the GAMM double-throat nozzte contlguration 1.
Y. Marx, J. Piquet

Multigrid with ILU-smoothing: systematic tests and improvements

Robustness is an important requirement for multigrid methods. In Standard multigrid methods, the smoothing process is usually the most crucial component. In particular, the robustness of a multigrid method and that of the underlying smoother are closely related. ILU is generally considered to provide a particularly robust smoothing process. Although often more robust than Standard relaxation methods, ILU is not really robust in a strict sense. This can be seen by applying a corresponding multigrid method to certain “limit cases” of typical model problems.
Two possibilities are presented which substantially improve the robustness of multi-grid methods with ILU-smoothing. One is based on a modification of the ILU-decompo-sition, while the other uses alternating ILU-smoothing. A smoothing process which turns out to be robust for all kinds of anisotropic model problems is obtained by combining both techniques: the alternating modified ILU-smoothing.
Klaus-Dieter Oertel, Klaus Stüben

Multilevel Preconditioning Matrices and Multigrid V-Cycle Methods

The relationship between the multilevel preconditioning matrices and a natural multigrid method is outlined. The multilevel preconditioning matrices are derived by an approximate block-factorization of the stiffness matrix computed by piecewise linear nodal basis functions. The block ordering of the nodes corresponds to a certain refining procedure, which starting with a coarse triangulation of the considered plane polygonal region generates successively refined triangulations. At each step of this refining procedure we add a new group of nodes which give the corresponding block of nodes in our multilevel ordering of the final nodal set. Under this multilevel block ordering, starting from the top level our stiffness matrix is factorized approximately, where any successive Schur complement is replaced (approximated) by the stiffness matrix of the current level. Another alternative is to view this method in the framework of the classical multigrid method of V-cycle type. For this natural multigrid method it is enough to use the corresponding two-level ordering of the stiffness matrix at each discretization level. Then the smoothing procedure is naturally derived from the stiffness matrix. The main computational task in performing one smoothing step is Solution of problems, on the current level, with a matrix (the first pivot block of the stiffness matrix in the two-level ordering) , which has a condition number bounded independently on the number of levels used. The convergence properties of these iterative methods are compared.
AMS Subject Classifications: 65F10, 65N20, 65N30
Panayot Vassilevski

Two Remarks on Multigrid Methods

This paper consists of two parts. In the first part, a partially successful attempt is made to extend multigrid theory to the case of a discontinuous coefficient, and an open problem is formulated. In the second part a non-recursive formulation of the fundamental multigrid algorithm is presented that contains only one goto Statement, and is better structured than the usual formulation.
P. Wesseling

On the Robustness of ILU-Smoothing

In the present paper we give a detailed analysis of a multi-grid method with ILU-smoother applied to singularly perturbed problems. Based on the analysis of a simple anisotropic model problem we introduce a variant of the usual incomplete LU-factorization, which is especially suited as robust smoother. For this variant we give a detailed analysis and a proof of robustness. Further, we explain some contradictions between the smoothingrates predicted by local Fourier analysis and the practically observed convergence factors,(see [7], [ 13], [ 19]). The theoretical results are confirmed by numerical tests.
Gabriel Wittum


Weitere Informationen