A Robust Multigrid Algorithm for the Simulation of a Yawed Flat Plate

This paper presents a full multigrid solver for the simulation of a flow over a yawed flat plate. The two problems associated with this simulation; boundary layers and entering flows with non-aligned characteristics, have been successfully overcome through the combination of a plane-implicit solver and semicoarsening. In fact, this multigrid algorithm exhibits a textbook multigrid convergence rate, i.e., the solution of the discrete system of equations is obtained in a fixed amount of computational work, independently of the grid size, grid stretching factor and non-alignment parameter. Also, a parallel variant of the smoother based on a four-color ordering of planes is investigated.     

A multigrid solver for phase field simulation of microstructure evolution

This paper presents a semi-implicit numerical method for the simulation of grain growth in two dimensions with a multi-phase field model. To avoid the strong stability condition of traditional explicit methods, a first-order, semi-implicit discretisation scheme is employed, which offers a good compromise with regard to memory intensity and computational requirements. A nonlinear multigrid solver based on the Full Approximation Scheme is implemented to solve the equations resulting from this discretisation. Simulations with the multigrid solver show that the solver has grid size independent convergence properties and is faster than a standard first-order explicit solver. As such, the multigrid solver promises to be a reliable additional computational tool for the simulation of microstructural evolution. A comparison with existing alternatives remains, however, subject of further investigation. To validate the implementation, the results of specific test cases are studied.     

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

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

Convergence analysis and numerical implementation of a second order numerical scheme for the three-dimensional phase field crystal equation

In this paper we analyze and implement a second-order-in-time numerical scheme for the three-dimensional phase field crystal (PFC) equation. The numerical scheme was proposed in Hu et al. (2009), with the unique solvability and unconditional energy stability established. However, its convergence analysis remains open. We present a detailed convergence analysis in this article, in which the maximum norm estimate of the numerical solution over grid points plays an essential role. Moreover, we outline the detailed multigrid method to solve the highly nonlinear numerical scheme over a cubic domain, and various three-dimensional numerical results are presented, including the numerical convergence test, complexity test of the multigrid solver and the polycrystal growth simulation.     

Geophysical modelling of 3D electromagnetic diffusion with multigrid

The performance of a multigrid solver for time-harmonic electromagnetic problems in geophysical settings was investigated. With the low frequencies used in geophysical surveys for deeper targets, the light-speed waves in the earth can be neglected. Diffusion of induced currents is the dominant physical effect. The governing equations were discretised by the Finite-Integration Technique. The resulting set of discrete equation was solved by a multigrid method. The multigrid method provided excellent convergence with constant grid spacings, but not on stretched grids. The slower convergence rate of the multigrid method could be compensated by using bicgstab2, in which case multigrid acted as a preconditioner. Still, the overall performance was less than satisfactory with substantial grid stretching.     

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.     

A parallel multigrid solver for incompressible flows on computing architectures with accelerators

An efficient parallel multigrid pressure correction algorithm is proposed for the solution of the incompressible Navier–Stokes equations on computing architectures with acceleration devices. The pressure correction procedure is based on the numerical solution of a Poisson-type problem, which is discretized using a fourth-order finite difference compact scheme. Since this is the most time-consuming part of the solver, we propose a parallel pressure correction algorithm using an iterative method based on a block cyclic reduction solution method combined with a multigrid technique. The grid points are numbered with respect to the red–black ordering scheme for the parallel Gauss–Seidel smoother. These parallelization techniques allow the execution of the entire simulation computations on the acceleration device, minimizing memory communication costs. The realization is developed using the OpenACC API, and the numerical method is demonstrated for the solution of two classical incompressible flow test problems. The first is the two-dimensional lid-driven cavity problem over equal mesh sizes while the other is the Stokes boundary layer, which is a decent benchmark problem for unequal mesh spacing. The effect of several multigrid components on modern and legacy acceleration architectures is examined. Eventually the performance investigation demonstrates that the proposed parallel multigrid solver achieves an acceleration of more than 10\(\times \) over the sequential solver and more than 4\(\times \) over multi-core CPU only realizations for all tested accelerators.     

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.     

Two level algorithms for partitioned fluid-structure interaction computations

In this paper we use the multigrid algorithm - commonly used to improve the efficiency of the flow solver - to improve the efficiency of partitioned fluid-structure interaction iterations. Coupling not only the structure with the fine flow mesh, but also with the coarse flow mesh (often present due to the multigrid scheme) leads to a significant efficiency improvement. As solution of the flow equations typically takes much longer than the structure solve, and as multigrid is not standard in structure solvers, we do not coarsen the structure or the interface. As a result, the two level method can be easily implemented into existing solvers.Two types of two level algorithms were implemented: (1) coarse grid correction of the partitioning error and (2) coarse grid prediction or full multigrid to generate a better initial guess. The resulting schemes are combined with a fourth-order Runge-Kutta implicit time integration scheme. For the linear, one-dimensional piston problem with compressible flow the superior stability, accuracy and efficiency of the two level algorithms is shown. The parameters of the piston problem were chosen such that both a weak and a strong interaction case were obtained.Even the strong interaction case, with a flexible structure, could be solved with our new two level partitioned scheme with just one iteration on the fine grid. This is a major accomplishment as most weakly coupled methods fail in this case. Of the two algorithms the coarse grid prediction or full multigrid method was found to perform best. The resulting efficiency gain for our one-dimensional problem is around a factor of ten for the coarse to intermediate time steps at which the high-order time integration methods should be run. For two- and three-dimensional problems the efficiency gain is expected to be even larger.     

An Algebraic Multigrid Method for Higher-order Finite Element Discretizations

In this paper, we will design and analyze a class of new algebraic multigrid methods for algebraic systems arising from the discretization of second order elliptic boundary value problems by high-order finite element methods. For a given sparse stiffness matrix from a quadratic or cubic Lagrangian finite element discretization, an algebraic approach is carefully designed to recover the stiffness matrix associated with the linear finite element disretization on the same underlying (but nevertheless unknown to the user) finite element grid. With any given classical algebraic multigrid solver for linear finite element stiffness matrix, a corresponding algebraic multigrid method can then be designed for the quadratic or higher order finite element stiffness matrix by combining with a standard smoother for the original system. This method is designed under the assumption that the sparse matrix to be solved is associated with a specific higher order, quadratic for example, finite element discretization on a finite element grid but the geometric data for the underlying grid is unknown. The resulting new algebraic multigrid method is shown, by numerical experiments, to be much more efficient than the classical algebraic multigrid method which is directly applied to the high-order finite element matrix. Some theoretical analysis is also provided for the convergence of the new method.     

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

Application of single-level,pointwise algebraic,and smoothed aggregation multigrid methods to direct numerical simulations of incompressible turbulent flows

Single- and multi-level iterative methods for sparse linear systems are applied to unsteady flow simulations via implementation into a direct numerical simulation solver for incompressible turbulent flows on unstructured meshes. The performance of these solution methods, implemented in the well-established SAMG and ML packages, are quantified in terms of computational speed and memory consumption, with a direct sparse LU solver (SuperLU) used as a reference. The classical test case of unsteady flow over a circular cylinder at low Reynolds numbers is considered, employing a series of increasingly fine anisotropic meshes. As expected, the memory consumption increases dramatically with the considered problem size for the direct solver. Surprisingly, however, the computation times remain reasonable. The speed and memory usage of pointwise algebraic and smoothed aggregation multigrid solvers are found to exhibit near-linear scaling. As an alternative to multi-level solvers, a single-level ILUT-preconditioned GMRES solver with low drop tolerance is also considered. This solver is found to perform sufficiently well only on small meshes. Even then, it is outperformed by pointwise algebraic multigrid on all counts. Finally, the effectiveness of pointwise algebraic multigrid is illustrated by considering a large three-dimensional direct numerical simulation case using a novel parallelization approach on a large distributed memory computing cluster.     

A multigrid fluid pressure solver handling separating solid boundary conditions

We present a multigrid method for solving the linear complementarity problem (LCP) resulting from discretizing the Poisson equation subject to separating solid boundary conditions in an Eulerian liquid simulation’s pressure projection step. The method requires only a few small changes to a multigrid solver for linear systems. Our generalized solver is fast enough to handle 3D liquid simulations with separating boundary conditions in practical domain sizes. Previous methods could only handle relatively small 2D domains in reasonable time, because they used expensive quadratic programming (QP) solvers. We demonstrate our technique in several practical scenarios, including nonaxis-aligned containers and moving solids in which the omission of separating boundary conditions results in disturbing artifacts of liquid sticking to solids. Our measurements show, that the convergence rate of our LCP solver is close to that of a standard multigrid solver.     

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.     

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 solution of the steady-state lattice Boltzmann equation

Efficient solution strategies for the steady-state lattice Boltzmann equation are investigated. Stable iterative methods for the linearized lattice Boltzmann equation are formulated based on the linearization of the lattice Boltzmann time-stepping procedure. These are applied as relaxation methods within a linear multigrid scheme, which itself is used to drive a Newton solver for the full non-linear problem. Although the linear multigrid strategy provides rapid convergence, the cost of a linear residual evaluation is found to be substantially higher than the cost of evaluating the non-linear residual directly. Therefore, a non-linear multigrid approach is adopted, which makes use of the non-linear LBE time-stepping scheme on each grid level. Rapid convergence to steady-state is achieved by the non-linear algorithm, resulting in one or more orders of magnitude increase in solution efficiency over the LBE time-integration approach. Grid-independent convergence rates are demonstrated, although degradation with increasing Reynolds number is observed, as in the case of the original LBE time-stepping scheme. The multigrid solver is implemented in a modular fashion by calling an existing LBE time-stepping routine, and delivers the identical steady-state solution as the original LBE time-stepping approach.     

Parallel computation of unsteady three-dimensional incompressible viscous flow using an unstructured multigrid method

The development and validation of a parallel unstructured tetrahedral non-nested multigrid (MG) method for simulation of unsteady 3D incompressible viscous flow is presented. The Navier-Stokes solver is based on the artificial compressibility method (ACM) and a higher-order characteristics-based finite-volume scheme on unstructured MG. Unsteady flow is calculated with an implicit dual time stepping scheme. The parallelization of the solver is achieved by a MG domain decomposition approach (MG-DD), using the Single Program Multiple Data (SPMD) programming paradigm. The Message-Passing Interface (MPI) Library is used for communication of data and loop arrays are decomposed using the OpenMP standard. The parallel codes using single grid and MG are used to simulate steady and unsteady incompressible viscous flows for a 3D lid-driven cavity flow for validation and performance evaluation purposes. The speedups and efficiencies obtained by both the parallel single grid and MG solvers are reasonably good for all test cases, using up to 32 processors on the SGI Origin 3400. The parallel results obtained agree well with those of serial solvers and with numerical solutions obtained by other researchers, as well as experimental measurements.     

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.     

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.     

一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

针对传统串行迭代法求解大波数Helmholtz方程存在效率低下且受限于单机内存的问题,提出了一种基于消息传递接口(Message Passing Interface,MPI) 的并行预条件迭代法。该算法利用复移位拉普拉斯算子对Helmholtz方程进行预条件处理,联合稳定双共轭梯度法和基于矩阵的多重网格法来求解预条件方程离散后的大规模线性系统,在Linux集群系统上基于 MPI环境实现了求解算法的并行计算,重点解决了多重网格的并行划分、信息传递和多重网格组件的构建问题。数值实验表明,对于大波数问题,提出的算法具有良好的并行加速比,相较于串行算法极大地提高了计算效率。