Optimization of the multigrid-convergence rate on semi-structured meshes by local Fourier analysis

In this paper a local Fourier analysis for multigrid methods on tetrahedral grids is presented. Different smoothers for the discretization of the Laplace operator by linear finite elements on such grids are analyzed. A four-color smoother is presented as an efficient choice for regular tetrahedral grids, whereas line and plane relaxations are needed for poorly shaped tetrahedra. A novel partitioning of the Fourier space is proposed to analyze the four-color smoother. Numerical test calculations validate the theoretical predictions. A multigrid method is constructed in a block-wise form, by using different smoothers and different numbers of pre- and post-smoothing steps in each tetrahedron of the coarsest grid of the domain. Some numerical experiments are presented to illustrate the efficiency of this multigrid algorithm.     

Adaptive multigrid for finite element computations in plasticity

The solution of the system of equilibrium equations is the most time-consuming part in large-scale finite element computations of plasticity problems. The development of efficient solution methods are therefore of utmost importance to the field of computational plasticity. Traditionally, direct solvers have most frequently been used. However, recent developments of iterative solvers and preconditioners may impose a change. In particular, preconditioning by the multigrid technique is especially favorable in FE applications.The multigrid preconditioner uses a number of nested grid levels to improve the convergence of the iterative solver. Prolongation of fine-grid residual forces is done to coarser grids and computed corrections are interpolated to the fine grid such that the fine-grid solution successively is improved. By this technique, large 3D problems, invincible for solvers based on direct methods, can be solved in acceptable time at low memory requirements. By means of a posteriori error estimates the computational grid could successively be refined (adapted) until the solution fulfils a predefined accuracy level. In contrast to procedures where the preceding grids are erased, the previously generated grids are used in the multigrid algorithm to speed up the solution process.The paper presents results using the adaptive multigrid procedure to plasticity problems. In particular, different error indicators are tested.     

Multigrid for Discrete Differential Forms on Sparse Grids

Discrete differential forms are a generalization of the common H¹()-conforming Lagrangian elements. For the latter, Galerkin schemes based on sparse grids are well known, and so are fast iterative multilevel solvers for the discrete Galerkin equations. We extend both the sparse grid idea and the design of multilevel methods to arbitrary discrete differential forms. The focus of this presentation will be on issues of efficient implementation and numerical studies of convergence of multigrid solvers.     

An algorithm for ideal multigrid convergence for the steady Euler equations

A fast multigrid solver for the steady incompressible Euler equations is presented. Unlike time-marching schemes this approach uses relaxation of the steady equations. Application of this method results in a discretization that correctly distinguishes between the advection and elliptic parts of the operator, allowing efficient smoothers to be constructed. Solvers for both unstructured triangular grids and structured quadrilateral grids have been written. Flows in two-dimensional channels and over airfoils have been computed. Using Gauss–Seidel relaxation with the grid vertices ordered in the flow direction, ideal multigrid convergence rates of nearly one order-of-magnitude residual reduction per multigrid cycle are achieved, independent of the grid spacing. This approach also may be applied to the compressible Euler equations and the incompressible Navier–Stokes equations.     

Multigrid Methods for the Stokes Equations using Distributive Gauss–Seidel Relaxations based on the Least Squares Commutator

A distributive Gauss–Seidel relaxation based on the least squares commutator is devised for the saddle-point systems arising from the discretized Stokes equations. Based on that, an efficient multigrid method is developed for finite element discretizations of the Stokes equations on both structured grids and unstructured grids. On rectangular grids, an auxiliary space multigrid method using one multigrid cycle for the Marker and Cell scheme as auxiliary space correction and least squares commutator distributive Gauss–Seidel relaxation as a smoother is shown to be very efficient and outperforms the popular block preconditioned Krylov subspace methods.     

Numerical Modeling of Plasma Devices by the Particle-In-Cell Method on Unstructured Grids

The paper considers methods and algorithms providing the basis for a computer program implementing an axial-symmetric electrostatic version of the particle-in-cell method on unstructured triangular grids. In the presented implementation, the Poisson equation is approximated using the finite volume method. A discrete analog of the Poisson equation is solved by the multigrid method. Charged particle trajectories are calculated using the Boris method. Methods for interpolating electrostatic fields on unstructured grids and obtaining the charge density in the computational domain are considered. Special attention is paid to the specifics of implementing these methods in axisymmetric geometry. The developed computer code is tested on the problem of a flat diode operating in the space charge mode.     

A multigrid solver for Stokes control problems

Multigrid solvers for distributed optimal control problems constrained by Stokes equations are presented. The distributed velocity tracking problem is considered with Dirichlet boundary conditions. The optimality system of the control problem that results from a Lagrange multiplier framework, forms a linear system connecting the state, adjoint, and control variables. We investigate multigrid methods on staggered grids. A coarsening by a factor of three is introduced that results in a nested hierarchy of staggered grids and simplified the intergrid transfer operators. On these grids a distributive Gauss–Seidel smoothing scheme is employed. Numerical experiments are performed to validate the effectiveness and efficiency of the proposed multigrid staggered grid framework.     

Partial semi-coarsening multigrid method based on the HOC scheme on nonuniform grids for the convection–diffusion problems

A partial semi-coarsening multigrid method based on the high-order compact (HOC) difference scheme on nonuniform grids is developed to solve the 2D convection–diffusion problems with boundary or internal layers. The significance of this study is that the multigrid method allows different number of grid points along different coordinate directions on nonuniform grids. Numerical experiments on some convection–diffusion problems with boundary or internal layers are conducted. They demonstrate that the partial semi-coarsening multigrid method combined with the HOC scheme on nonuniform grids, without losing the high-order accuracy, is very efficient and effective to decrease the computational cost by reducing the number of grid points along the direction which does not contain boundary or internal layers.     

Parallel multigrid solution of the Navier-Stokes equations on general 2D domains

Multigrid methods are distinguished by their optimal (sequential) efficiency and by the fact that all their algorithmical components are fully parallelizable. For this reason, this class of numerical methods is especially attractive for use on parallel (MIMD, local memory) computers. In this paper, we describe a parallel multigrid solver for steady-state incompressible Navier-Stokes equations on general domains which is currently being developed at the GMD. Due to the geometrical generality of the problem, our approach is based on a non-staggered (nodal-point) finite volume scheme on multi-block boundary fitted grids. The typical instability of non-staggered schemes is overcome by suitably modifying the discrete continuity equation without affecting the overall order of consistency.

Starting from the most simple Cartesian case, we discuss several possible multigrid approaches to the general 2D-problem. This motivates the basic design decisions of our multigrid solver in regard to both the discretization and the choice of multigrid components (smoothing schemes). Furthermore, the principal technique of parallelization (grid partitioning) is described as well as some fundamental aspects of the implementation (communication library).     

Parallel multilevel methods with adaptivity on unstructured grids

We present two parallel multilevel methods for solving large-scale discretized partial differential equations on unstructured 2D/3D grids. The presented methods combine three powerful numerical algorithms: overlapping domain decomposition, multigrid method and adaptivity. As the foundation of the methods we propose an algorithm for generating and partitioning a hierarchy of adaptively refined unstructured grids, so that adaptivity can be incorporated up to a certain grid level. We ensure that the resulting subgrid hierarchies are well balanced and no inter-processor communication is needed across different grid levels, thus obtaining high parallel efficiency. Numerical experiments show that the parallel multilevel methods offer almost equally fast convergence as their sequential multigrid counterpart. And the resulting implementation has reasonably good scalability. Received: 4 December 1998 / Accepted: 12 January 2000     

Optimization of multigrid based elliptic solver for large scale simulations in the FLASH code

FLASH is a multiphysics multiscale adaptive mesh refinement (AMR) code originally designed for simulation of reactive flows often found in Astrophysics. With its wide user base and flexible applications configuration capability, FLASH has a dual task of maintaining scalability and portability in all its solvers. The scalability of fully explicit solvers in the code is tied very closely to that of the underlying mesh. Others such as the Poisson solver based on a multigrid method have more complex scaling behavior. Multigrid methods suffer from processor starvation and dominating communication costs at coarser grids with increase in the number of processors. In this paper, we propose a combination of uniform grid mesh with AMR mesh, and the merger of two different sets of solvers to overcome the scalability limitation of the Poisson solver in FLASH. The principal challenge in the proposed merger is the efficiency of the communication algorithm to map the mesh back and forth between uniform grid and AMR. We present two different parallel mapping algorithms and also discuss results from performance studies of the two implementations. Copyright © 2012 John Wiley & Sons, Ltd.     

Parallel-adaptive simulation with the multigrid-based software framework UG

In this paper we present design aspects and concepts of the unstructured grids (UG) software framework that are relevant for parallel-adaptive simulation of time-dependent, nonlinear partial differential equations. The architectural design is discussed on system, subsystem and component level for distributed mesh management and local adaptation capabilities. Parallelization is founded on top of the innovative programming model dynamic distributed data (DDD). Newly introduced modules and extensions of DDD are discussed. Local multigrid methods are introduced as optimal linear solvers in the solution process. The demands of local parallel mesh adaptation are further described: Beside a mesh manipulation module further steps dynamic load balancing and migration have to be introduced. Their realization in the context of local multigrid methods is significantly non-trivial and makes the major contribution to the paper presented here. Parallel I/O provides an efficient mechanism for restart, postprocessing and long-term, large-scale computations. The UG approach is verified through a considerable code-reuse fraction of nearly 90% for simulations of complicated phenomena like porous media flow and transport as well as elastoplasticity. Parallel simulations with up to 10⁸ unknowns are shown for the Couplex benchmark. Therefore a grid convergence study to verify the reliability of the computed results is possible. For an parallel-adaptive elastoplasticity computation the speedup of the multigrid solver, which is the most scalability critical simulation part, exceeds on 512 processor a value of 300. The overhead introduced by the parallel-adaptive scheme turns out to be below 10% of the whole simulation time.     

Parallel Multigrid for Anisotropic Elliptic Equations

In this paper two well-known robust multigrid solvers for anisotropic operators on structured grids are compared: alternating-plane smoothers combined with full coarsening and plane smoothers combined with semi-coarsening. The study has taken into account not only numerical properties but also architectural ones, focusing on cache memory exploitation and parallel characteristics. Experimental results for the sequential algorithms have been obtained on two different systems based on the MIPS R10000 processor, but with different L2 cache sizes and memory bandwidths (an SGI O2 workstation and an SGI Origin 2000 system). Although the alternating-plane approach is the best choice for sequential implementations, experimental estimations show poor parallel efficiencies. For the semicoarsening alternative two different parallel implementations have been considered. The first one has optimal parallel characteristics but due to deterioration of the convergence properties its realistic efficiency is not satisfactory. In the second one, some processors remain idle during a short period of time on every multigrid cycle. However, the second parallel algorithm is more efficient since it preserves the numerical properties of the sequential version. Parallel experiments have also been taken on a Cray T3E system.     

On efficient multigrid software for elliptic problems on rectangular domains

Emphasis has been laid on software development concerning ‘non-standard’ multigrid techniques as introduced by Foerster, Stüben and Trottenberg¹. The advantages of these methods result in very efficient code for the solution of elliptic problems. In comparison with fast direct methods, the multigrid solver MGOO is as good as direct solvers for model equations on rectangular domains, even better in special cases, and more generally applicable (variable coefficients).     

Performance Rating via the Feast Indices

Based on algorithmic and computational studies, we present the Feast Indices which are new indicators for the realistic performance of many recent processors, as typically used in ‘low cost’ PC's/workstations up to (parallel) supercomputers. Since these tests are very specifically designed for the evaluation of modern numerical simulation techniques, with a special emphasis on `large scale' FEM computations and iterative solvers of Krylov-space/multigrid type, they examine new aspects in comparison to the standard benchmark tests (LINPACK, SPEC FP95, NAS, STREAM) and allow new qualitative and particularly quantitative ratings of the various hardware platforms. We explore the computational efficiency of certain Linear Algebra components, hereby applying the typical sparse approaches and additionally the sparse banded style from Feast which enables us to exploit a significant percentage of the available Peak performance. The tests include ‘simple’ matrix-vector applications as well as complete multigrid solvers with very robust smoothers which are necessary for the efficient treatment of highly adapted meshes. Received: February 10, 1999; revised: June 14, 1999     

Automatic mesh refinement and data structure for multigrid finite elements techniques

A general algorithm for locally refining any conforming triangulation to generate a new conforming one is presented. The proposed algorithm ensures that all angles in subsequent refined triangulations are greater than, or equal to, half the smallest angle in the original triangulation, the shape regularity of all triangles is maintained and the transition between small and large triangles is smooth. The generated triangulations are nested, so it is possible to implement the approach with adaptive and/or multigrid techniques. A complete algorithm for solving two-dimensional elliptic boundary value problems adaptively by multigrid is presented. The development and implementation of the main parts of this algorithm; automatic mesh generator, a posteriori error estimator, refinement strategy and the multigrid solver are presented in some detail. An appropriate data structure is developed to meet the excess data required for the generation process also to keep track of different grid levels. By the aid of this data structure, it becomes easy to design simple algorithms to store only the non-zero elements of stiffness matrices for different grids and to design a very simple multigrid transfer operator. Numerical examples are presented to show the generated grid sequence for two different boundary value problems.     

A Parallel Finite Element Method for 3D Two-Phase Moving Contact Line Problems in Complex Domains

Moving contact line problem plays an important role in fluid-fluid interface motion on solid surfaces. The problem can be described by a phase-field model consisting of the coupled Cahn–Hilliard and Navier–Stokes equations with the generalized Navier boundary condition (GNBC). Accurate simulation of the interface and contact line motion requires very fine meshes, and the computation in 3D is even more challenging. Thus, the use of high performance computers and scalable parallel algorithms are indispensable. In this paper, we generalize the GNBC to surfaces with complex geometry and introduce a finite element method on unstructured 3D meshes with a semi-implicit time integration scheme. A highly parallel solution strategy using different solvers for different components of the discretization is presented. More precisely, we apply a restricted additive Schwarz preconditioned GMRES method to solve the systems arising from implicit discretization of the Cahn–Hilliard equation and the velocity equation, and an algebraic multigrid preconditioned CG method to solve the pressure Poisson system. Numerical experiments show that the strategy is efficient and scalable for 3D problems with complex geometry and on a supercomputer with a large number of processors.     

Newton-Krylov-FAC methods for problems discretized on locally refined grids

Many problems in computational science and engineering are nonlinear and time-dependent. The solutions to these problems may include spatially localized features, such as boundary layers or sharp fronts, that require very fine grids to resolve. In many cases, it is impractical or prohibitively expensive to resolve these features with a globally fine grid, especially in three dimensions. Adaptive mesh refinement (AMR) is a dynamic gridding approach that employs a fine grid only where necessary to resolve such features. Numerous AMR codes exist for solving hyperbolic problems with explicit time stepping and some classes of linear elliptic problems. Researchers have paid much less attention to the development of AMR algorithms for the implicit solution of systems of nonlinear equations. Recent efforts encompassing a variety of applications demonstrate that Newton-Krylov methods are effective when combined with multigrid preconditioners. This suggests that hierarchical methods, such as the Fast Adaptive Composite grid (FAC) method of McCormick and Thomas, can provide effective preconditioning for problems discretized on locally refined grids. In this paper, we address algorithm and implementation issues for the use of Newton-Krylov-FAC methods on structured AMR grids. In our software infrastructure, we combine nonlinear solvers from KINSOL and PETSc with the SAMRAI AMR library, and include capabilities for implicit time stepping. We have obtained convergence rates independent of the number of grid refinement levels for simple, nonlinear, Poisson-like, problems. Additional efforts to employ this infrastructure in new applications are underway. Communicated by: G. Wittum     

Multigrid method for nonlinear poroelasticity equations

In this study, a nonlinear multigrid method is applied for solving the system of incompressible poroelasticity equations considering nonlinear hydraulic conductivity. For the unsteady problem, an additional artificial term is utilized to stabilize the solutions when the equations are discretized on collocated grids. We employ two nonlinear multigrid methods, i.e. the “full approximation scheme” and “Newton multigrid” for solving the corresponding system of equations arising after discretization. For the steady case, both homogeneous and heterogeneous cases are solved and two different smoothers are examined to search for an efficient multigrid method. Numerical results show a good convergence performance for all the strategies.     

Multigrid for finite element discretizations of aerodynamics equations

A multigrid algorithm for the solution of a finite element stabilized discretization of compressible fluid dynamics equations on unstructured grids is described. The solution of the stationary problems is sought by time-stepping and a linearization of the nonlinear discrete systems leads to a very large system of linear equations. These systems are ill-conditioned and require efficient computational procedures. The numerical experiments for Navier-Stokes and Euler systems are presented. The method can be easily included in a parallel library as a preconditioner.