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     

The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids

An abstract framework ofauxiliary space method is proposed and, as an application, an optimal multigrid technique is developed for general unstructured grids. The auxiliary space method is a (nonnested) two level preconditioning technique based on a simple relaxation scheme (smoother) and an auxiliary space (that may be roughly understood as a nonnested coarser space). An optimal multigrid preconditioner is then obtained for a discretized partial differential operator defined on an unstructured grid by using an auxiliary space defined on a more structured grid in which a furthernested multigrid method can be naturally applied. This new technique makes it possible to apply multigrid methods to general unstructured grids without too much more programming effort than traditional solution methods. Some simple examples are also given to illustrate the abstract theory and for instance the Morley finite element space is used as an auxiliary space to construct a preconditioner for Argyris element for biharmonic equations. Some numerical results are also given to demonstrate the efficiency of using structured grid for auxiliary space to precondition unstructured grids.     

Parallel multigrid on hierarchical hybrid grids: a performance study on current high performance computing clusters

This article studies the performance and scalability of a geometric multigrid solver implemented within the hierarchical hybrid grids (HHG) software package on current high performance computing clusters up to nearly 300,000 cores. HHG is based on unstructured tetrahedral finite elements that are regularly refined to obtain a block‐structured computational grid. One challenge is the parallel mesh generation from an unstructured input grid that roughly approximates a human head within a 3D magnetic resonance imaging data set. This grid is then regularly refined to create the HHG grid hierarchy. As test platforms, a BlueGene/P cluster located at Jülich supercomputing center and an Intel Xeon 5650 cluster located at the local computing center in Erlangen are chosen. To estimate the quality of our implementation and to predict runtime for the multigrid solver, a detailed performance and communication model is developed and used to evaluate the measured single node performance, as well as weak and strong scaling experiments on both clusters. Thus, for a given problem size, one can predict the number of compute nodes that minimize the overall runtime of the multigrid solver. Overall, HHG scales up to the full machines, where the biggest linear system solved on Jugene had more than one trillion unknowns. Copyright © 2012 John Wiley & Sons, Ltd.     

An adaptive multilevel multigrid formulation for Cartesian hierarchical grid methods

A Cartesian grid method with adaptive mesh refinement and multigrid acceleration is presented for the compressible Navier-Stokes equations. Cut cells are used to represent boundaries on the Cartesian grid, while ghost cells are introduced to facilitate the implementation of boundary conditions. A cell-tree data structure is used to organize the grid cells in a hierarchical manner. Cells of all refinement levels are present in this data structure such that grid level changes as they are required in a multigrid context do not have to be carried out explicitly. Adaptive mesh refinement is introduced using phenomenon-based sensors. The application of the multilevel method in conjunction with the Cartesian cut-cell method to problems with curved boundaries is described in detail. A 5-step Runge-Kutta multigrid scheme with local time stepping is used for steady problems and also for the inner integration within a dual time-stepping method for unsteady problems. The inefficiency of customary multigrid methods on Cartesian grids with embedded boundaries requires a new multilevel concept for this application, which is introduced in this paper. This new concept is based on the following novelties: a formulation of a multigrid method for Cartesian hierarchical grid methods, the concept of averaged control volumes, and a mesh adaptation strategy allowing to directly control the number of refined and coarsened cells.     

非结构网格的并行多重网格解算器

多重网格方法作为非结构网格的高效解算器,其串行与并行实现在时空上都具有优良特性.以控制方程离散过程为切入点,说明非结构网格在并行数值模拟的流程,指出多重网格方法主要用于求解时间推进格式产生的大规模代数系统方程,简述了算法实现的基本结构,分析了其高效性原理;其次,综述性地概括了几何多重网格与代数多种网格研究动态,并对其并行化的热点问题进行重点论述.同时,针对非结构网格的实际应用,总结了多重网格解算器采用的光滑算子;随后列举了非结构网格应用的部分开源项目软件,并简要说明了其应用功能;最后,指出并行多重网格解算器在非结构网格应用中的若干关键问题和未来的研究方向.     

Numerical simulation of 3D fluid–structure interaction flow using an immersed object method with overlapping grids

The newly developed immersed object method (IOM) [Tai CH, Zhao Y, Liew KM. Parallel computation of unsteady incompressible viscous flows around moving rigid bodies using an immersed object method with overlapping grids. J Comput Phys 2005; 207(1): 151–72] is extended for 3D unsteady flow simulation with fluid–structure interaction (FSI), which is made possible by combining it with a parallel unstructured multigrid Navier–Stokes solver using a matrix-free implicit dual time stepping and finite volume method [Tai CH, Zhao Y, Liew KM. Parallel computation of unsteady three-dimensional incompressible viscous flow using an unstructured multigrid method. In: The second M.I.T. conference on computational fluid and solid mechanics, June 17–20, MIT, Cambridge, MA 02139, USA, 2003; Tai CH, Zhao Y, Liew KM. Parallel computation of unsteady three-dimensional incompressible viscous flow using an unstructured multigrid method, Special issue on “Preconditioning methods: algorithms, applications and software environments. Comput Struct 2004; 82(28): 2425–36]. This uniquely combined method is then employed to perform detailed study of 3D unsteady flows with complex FSI. In the IOM, a body force term F is introduced into the momentum equations during the artificial compressibility (AC) sub-iterations so that a desired velocity distribution V₀ can be obtained on and within the object boundary, which needs not coincide with the grid, by adopting the direct forcing method. An object mesh is immersed into the flow domain to define the boundary of the object. The advantage of this is that bodies of almost arbitrary shapes can be added without grid restructuring, a procedure which is often time-consuming and computationally expensive. It has enabled us to perform complex and detailed 3D unsteady blood flow and blood–leaflets interaction in a mechanical heart valve (MHV) under physiological conditions.     

A multiblock multigrid grid generation method for complex simulations

This paper deals with the aim of coupling multigrid generation of boundary-fitted grids with an effective domain decomposition technique. We present multiblock grid generation algorithms for efficient solutions of domain discretization problems. We propose the generation of structured grids by multiblock transformation of the domains, the choice of specific elliptic systems and the application of multigrid cycling. We assume the Laplacians of the curvilinear coordinates to be equal to appropriate functions of the curvilinear coordinates in the physical domain and, by interchanging the independent and the dependent variable, we obtain the transformed systems in the multiblock transformed computational domain. We adopt standard central differencing for the approximation of the nonlinear generating 2D and 3D systems and full approximation storage algorithms to solve the resulting discrete equations. We use block matching with two-surface overlapping and block by block iterations along with multigrid cycling in each block. We present computed multiblock grids by Figures and evaluation results of method performance by Tables.     

Parallelism in multigrid methods: How much is too much?

Multigrid methods are powerful techniques to accelerate the solution of computationally-intensive problems arising in a broad range of applications. Used in conjunction with iterative processes for solving partial differential equations, multigrid methods speed up iterative methods by moving the computation from the original mesh covering the problem domain through a series of coarser meshes. But this hierarchical structure leaves domain-parallel versions of the standard multigrid algorithms with a deficiency of parallelism on coarser grids. To compensate, several parallel multigrid strategies with more parallelism, but also more work, have been designed. We examine these parallel strategies and compare them to simpler standard algorithms to try to determine which techniques are more efficient and practical. We consider three parallel multigrid strategies: (1) domain-parallel versions of the standard V-cycle and F-cycle algorithms; (2) a multiple coarse grid algorithm, proposed by Fredrickson and McBryan, which generates several coarse grids for each fine grid; and (3) two Rosendale algorithm, which allow computation on all grids simultaneously. We study an elliptic model problem on simple domains, discretized with finite difference techniques on block-structured meshes in two or three dimensions with up to 10⁶ or 10⁹ points, respectively. We analyze performance using three models of parallel computation: the PRAM and two bridging models. The bridging models reflect the salient characteristics of two kinds of parallel computers: SIMD fine-grain computers, which contain a large number of small (bitserial) processors, and SPMD medium-grain computers, which have a more modest number of powerful (single chip) processors. Our analysis suggests that the standard algorithms are substantially more efficient than algorithms utilizing either parallel strategy. Both parallel strategies need too much extra work to compensate for their extra parallelism. They require a highly impractical number of processors to be competitive with simpler, standard algorithms. The analysis also suggests that the F-cycle, with the appropriate optimization techniques, is more efficient than the V-cycle under a broad range of problem, implementation, and machine characteristics, despite the fact that it exhibits even less parallelism than the V-cycle. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, and the Office of Naval Research, Contract No. N0014-91-J-1463.     

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

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.     

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.     

New architectures: Performance highlights and new algorithms

Parallel computers are having a profound impact on computational science. Recently highly parallel machines have taken the lead as the fastest supercomputers, a trend that is likely to accelerate in the future. We describe some of these new computers, and issues involved in using them. We present elliptic PDE solutions currently running at 3.8 gigaflops, and an atmospheric dynamics model running at 1.7 gigaflops, on a 65 536-processor computer.

One intrinsic disadvantage of a parallel machine is the need to perform inter-processor communication. It is important to ensure that such communication time is maintained at a small fraction of computation time. We analyze standard multigrid algorithms in two and three dimensions from this point of view, indicating that performance efficiencies in excess of 95% are attainable under suitable conditions on moderately parallel machines. We also demonstrate that such performance is not attainable for multigrid on massively parallel computers, as indicated by an example of poor multigrid efficiency on 65 536 processors. The fundamental difficulty is the inability to keep 65 536 processors busy when operating on very coarse grids.

Most algorithms used for implementing applications on parallel machines have been derived directly from algorithms designed for serial machines. The previously mentioned multigrid example indicates that such ‘parallelized’ algorithms may not always be optimal. Parallel machines open the possibility of finding totally new approaches to solving standard tasks—intrinsically parallel algorithms. In particular, we present a class of superconvergent multiple scale methods that were motivated directly by massevely parallel machines. These methods differ from standard multigrid methods in an intrinsic way, and allow all processors to be used at all times, even when processing on the coarsest grid levels. Their serial versions are not sensible algorithms. The idea that parallel hardware—the Connection Machine in this case—can lead to discovery of new mathematical algorithms was surprising for us.     

A parallel fictitious domain multigrid preconditioner for the solution of Poisson’s equation in complex geometries

A parallel multilevel preconditioner based on domain decomposition and fictitious domain methods has been presented for the solution of the Poisson equation in complicated geometries. Rectangular blocks with matching grids on interfaces on a structured rectangular mesh have been used for the decomposition of the problem domain. Sloping sides or curved boundary surfaces are approximated using stepwise surfaces formed by the grid cells. A seven-point stencil based on the central difference scheme has been used for the discretization of the Laplacian for both interior and boundary grid points, and this results in a symmetric linear algebraic system for any type of boundary condition. The preconditioned conjugate gradient method has been used for the solution of this symmetric system. The multilevel preconditioner for the CG is based on a V-cycle multigrid applied to the Poisson equation on a fictitious domain formed by the union of the rectangular blocks used for the domain decomposition. Numerical results are presented for two typical Poisson problems in complicated geometries—one related to heat conduction, and the other one arising from the LES/DNS of incompressible turbulent flow over a packed array of spheres. These results clearly show the efficiency and robustness of the proposed approach.     

2-dimensional implicit hydrodynamics on adaptive grids

We present a numerical scheme for two-dimensional hydrodynamics computations using a 2D adaptive grid together with an implicit discretization. The combination of these techniques has offered favorable numerical properties applicable to a variety of one-dimensional astrophysical problems which motivated us to generalize this approach for two-dimensional applications. Due to the different topological nature of 2D grids compared to 1D problems, grid adaptivity has to avoid severe grid distortions which necessitates additional smoothing parameters to be included into the formulation of a 2D adaptive grid. The concept of adaptivity is described in detail and several test computations demonstrate the effectivity of smoothing. The coupled solution of this grid equation together with the equations of hydrodynamics is illustrated by computation of a 2D shock tube problem.     

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.     

Grid applications on distributed memory architectures: Implementation and evaluation

It was shown in the paper of Solchenbach and Trottenberg (in this special issue) that grid algorithms are inherently parallel and that parallel grid algorithms for regular grids can be efficiently implemented on dm-mp systems using the concept of grid partitioning.

In this paper, we demonstrate that grid applications can be implemented quite easily on dm-mp systems if a hardware-independent process system exists and convenient tools (such as the SUPRENUM mapping and communications library) are available.

The evaluation of parallel grid algorithms shows that the multiprocessor speedup and efficiency for single grid applications depends on the communication/calculation performance ratio of the hardware, on the communication/calculation ratio of the algorithms, and on the process size. The efficiency of parallel multigrid algorithms additionally depends on the number of nodes.     

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

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