Application of the multigrid approach for solving 3D Navier-Stokes equations on hexahedral grids using the discontinuous Galerkin method

The Galerkin method with discontinuous basis functions is adapted for solving the Euler and Navier-Stokes equations on unstructured hexahedral grids. A hybrid multigrid algorithm involving the finite element and grid stages is used as an iterative solution method. Numerical results of calculating the sphere inviscid flow, viscous flow in a bent pipe, and turbulent flow past a wing are presented. The numerical results and the computational cost are compared with those obtained using the finite volume method.     

Geometric and algebraic multigrid techniques for fluid dynamics problems on unstructured grids

Issues concerning the implementation and practical application of geometric and algebraic multigrid techniques for solving systems of difference equations generated by the finite volume discretization of the Euler and Navier–Stokes equations on unstructured grids are studied. The construction of prolongation and interpolation operators, as well as grid levels of various resolutions, is discussed. The results of the application of geometric and algebraic multigrid techniques for the simulation of inviscid and viscous compressible fluid flows over an airfoil are compared. Numerical results show that geometric methods ensure faster convergence and weakly depend on the method parameters, while the efficiency of algebraic methods considerably depends on the input parameters.     

Preconditioning of the Euler and Navier-Stokes equations in low-velocity flow simulation on unstructured grids

Low-velocity inviscid and viscous flows are simulated using the compressible Euler and Navier-Stokes equations with finite-volume discretizations on unstructured grids. Block preconditioning is used to speed up the convergence of the iterative process. The structure of the preconditioning matrix for schemes of various orders is discussed, and a method for taking into account boundary conditions is described. The capabilities of the approach are demonstrated by computing the low-velocity inviscid flow over an airfoil.     

A Parallel Implementation of the Algebraic Multigrid Method for Solving Problems in Dynamics of Viscous Incompressible Fluid

An algorithm for improving the scalability of the multigrid method used for solving the system of difference equations obtained by the finite volume discretization of the Navier–Stokes equations on unstructured grids with an arbitrary cell topology is proposed. It is based on the cascade assembly of the global level; the cascade procedure gradually decreases the number of processors involved in the computations. Specific features of the proposed approach are described, and the results of solving benchmark problems in the dynamics of viscous incompressible fluid are discussed; the scalability and efficiency of the proposed method are estimated. The advantages of using the global level in the parallel implementation of the multigrid method which sometimes makes it possible to speed up the computations by several fold.     

A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.     

An algebraic multigrid method for finite element systems on criss-cross grids

In this paper, we design and analyze an algebraic multigrid method for a condensed finite element system on criss-cross grids and then provide a convergence analysis. Criss-cross grid finite element systems represent a large class of finite element systems that can be reduced to a smaller system by first eliminating certain degrees of freedoms. The algebraic multigrid method that we construct is analogous to many other algebraic multigrid methods for more complicated problems such as unstructured grids, but, because of the specialty of our problem, we are able to provide a rigorous convergence analysis to our algebraic multigrid method. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday The work was supported in part by NSAF(10376031) and National Major Key Project for basic researches and by National High-Tech ICF Committee in China.     

A multigrid method for grid generation with line-spacing control

A multigrid method for grid generation on two-dimensional regions and its applications to test problems are presented. The multigrid algorithm deals with the solution of elliptic differential problems which occur in the computation of boundary-fitted grids. The solution of elliptic systems of partial differential equations, which correspond to transformed Poisson systems, is carried out by a full approximation storage (FAS) algorithm. The components of the method, such as the relaxation for error smoothing and the coarsening strategy, are evaluated on problems in which sources of attractions are considered, and the generated grids are shown by figures.     

一种新的并行代数多重网格粗化算法

近年来,受实际应用领域中大规模科学计算问题的驱动,在大规模并行机上实现代数多重网格（AMG）算法成为数值计算领域的研究热点。本文针对经典AMG方法,提出一种新的并行网格粗化算法一多阶段并行RS算法（MPRS）。我们将新算法集成到了高性能预条件子软件包Hypre中。大量数值实验结果显示,新算法适合更广泛的问题,相对其他并行粗化算法,明显地改善了AMG并行计算的可扩展性。对三维27点格式有限差分离散的Poisson方程,在64个处理机上并行AMG求解,含8百万个未知量,新算法比RS3算法减少了近60的三维Poisson方程,近32万个未知量,在16个处理机上并行AMG—GMRES求解,新算法所需的迭代步数大约为其他粗化算法的一半,显示了很好的算法可扩展性。     

A Multigrid Block LU-SGS Algorithm for Euler Equations on Unstructured Grids

We propose an efficient and robust algorithm to solve the steady Euler equa- tions on unstructured grids.The new algorithm is a Newton-iteration method in which each iteration step is a linear multigrid method using block lower-upper symmetric Gauss-Seidel(LU-SGS)iteration as its smoother To regularize the Jacobian matrix of Newton-iteration,we adopted a local residual dependent regularization as the replace- ment of the standard time-stepping relaxation technique based on the local CFL number The proposed method can be extended to high order approximations and three spatial dimensions in a nature way.The solver was tested on a sequence of benchmark prob- lems on both quasi-uniform and local adaptive meshes.The numerical results illustrated the efficiency and robustness of our algorithm.     

Efficient iterative solvers for time-harmonic Maxwell equations using domain decomposition and algebraic multigrid

Paper presents a set of parallel iterative solvers and preconditioners for the efficient solution of systems of linear equations arising in the high order finite-element approximations of boundary value problems for 3-D time-harmonic Maxwell equations on unstructured tetrahedral grids. Balancing geometric domain decomposition techniques combined with algebraic multigrid approach and coarse-grid correction using hierarchic basis functions are exploited to achieve high performance of the solvers and small memory load on the supercomputers with shared and distributed memory. Testing results for model and real-life problems show the efficiency and scalability of the presented algorithms.     

The adaptation of unstructured grids for transonic viscous flow simulation

The computation of viscous flows using unstructured grids is a relatively new area of research. This paper details work carried out to analyse the efficiency of initial unstructured viscous grids and their adaptation, particularly in the region of aerofoil trailing edges. This will enable an optimal approach to be established which can be extended into practical three-dimensional viscous flow simulations.     

Algebraic multigrid preconditioning of the Hessian in optimization constrained by a partial differential equation

We construct an algebraic multigrid (AMG) based preconditioner for the reduced Hessian of a linear‐quadratic optimization problem constrained by an elliptic partial differential equation. While the preconditioner generalizes a geometric multigrid preconditioner introduced in earlier works, its construction relies entirely on a standard AMG infrastructure built for solving the forward elliptic equation, thus allowing for it to be implemented using a variety of AMG methods and standard packages. Our analysis establishes a clear connection between the quality of the preconditioner and the AMG method used. The proposed strategy has a broad and robust applicability to problems with unstructured grids, complex geometry, and varying coefficients. The method is implemented using the Hypre package and several numerical examples are presented.     

并行间断有限元算法求解Navier-Stokes方程

间断Galerkin有限元方法非常适合在非结构网格上高精度求解Navier-Stokes方程,然而其十分耗费计算资源.为了提高计算效率,提出了高效的MIMD并行算法.采用隐式时间离散GMRES+LU SGS格式,结合多重网格方法,当地时间步长加速算法收敛.为了保证各处理器间负载平衡,采用区域分解二级图方法划分网格,实现内存合理分配,数据只在相邻处理器间传递.数值模拟了RAE2822翼型和M6黏性绕流,加速比基本呈线性变化且接近理想值.结果表明了该算法能有效减少计算时间、合理分配内存,具有较高的加速比和并行效率,适合于MIMD粗粒度科学计算.     

Multigrid applications to three-dimensional elliptic coordinate generation

The multigrid algorithm was applied to solve the coupled set of elliptic quasilinear partial differential equations associated with three-dimensional coordinate generation. The results indicate that the multigrid scheme is more than twice as fast as conventional relaxation schemes on moderate-size grids. Convergence factors of order 0.90 per work unit were achieved on 36,000-point grids. The paper covers the form of transformation, develops the set of generation equations, and gives details on the multigrid approach used. Included are a development of the full-approximation storage scheme, details of the smoothing-rate analysis, and a section devoted to rational programming techniques applicable to the multigrid algorithm.     

Comparison of two cell-centered multigrid schemes for problems with discontinuous coefficients

Two different schemes for constructing coarse-grid operators are implemented in a linear multigrid code. In the first scheme, the construction of the coarse-grid operators is done using a variational approach. Certain conservation properties of the fine-grid matrices are shown to be preserved on the coarser grids by the variational construction. In the second scheme, the diffusion coefficients for the coarse grids are calculated by a simple restriction of the coefficient from the fine grid, using a flux conservation principle. The multigrid codes are then applied to solve the linear equations from an IMPES formulation of a two-phase porous-media flow model. A standard elliptic model problem with jump discontinuous coefficients is also solved using the two multigrid schemes. In simple cases of particular elliptic equations these two schemes are identical. However, in more general cases, such as in reservoir problems, these schemes differ. It is shown that multigrid efficiency typical of the constant coefficient cases is obtained for these problems involving discontinuous coefficients. © 1993 John Wiley & Sons, Inc.     

Efficient numerical methods for pricing American options under stochastic volatility

Five numerical methods for pricing American put options under Heston's stochastic volatility model are described and compared. The option prices are obtained as the solution of a two‐dimensional parabolic partial differential inequality. A finite difference discretization on nonuniform grids leading to linear complementarity problems with M‐matrices is proposed. The projected SOR, a projected multigrid method, an operator splitting method, a penalty method, and a componentwise splitting method are considered. The last one is a direct method while all other methods are iterative. The resulting systems of linear equations in the operator splitting method and in the penalty method are solved using a multigrid method. The projected multigrid method and the componentwise splitting method lead to a sequence of linear complementarity problems with one‐dimensional differential operators that are solved using the Brennan and Schwartz algorithm. The numerical experiments compare the accuracy and speed of the considered methods. The accuracies of all methods appear to be similar. Thus, the additional approximations made in the operator splitting method, in the penalty method, and in the componentwise splitting method do not increase the error essentially. The componentwise splitting method is the fastest one. All multigrid‐based methods have similar rapid grid independent convergence rates. They are about two or three times slower that the componentwise splitting method. On the coarsest grid the speed of the projected SOR is comparable with the multigrid methods while on finer grids it is several times slower. ©John Wiley & Sons, Inc. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Parallel linear multigrid by agglomeration for the acceleration of 3D compressible flow calculations on unstructured meshes

In this paper, we report on our recent efforts concerning the design of parallel linear multigrid algorithms for the acceleration of 3-dimensional compressible flow calculations. The multigrid strategy adopted in this study relies on a volume agglomeration principle for the construction of the coarse grids starting from a fine discretization of the computational domain. In the past, this strategy has mainly been studied in the 2-dimensional case for the solution of the Euler equations (see Lallemand et al. [6]), the laminar Navier–Stokes equations (see Mavriplis and Venkatakrishnan [12]) and the turbulent Navier–Stokes equations (see Carré [1], Mavriplis [10] and Francescatto and Dervieux [4]). A first extension to the 3-dimensional case is presented by Mavriplis and Venkatakrishnan in [13] and more recently in Mavriplis and Pirzadeh [11]. The main contribution of the present work is twofold: on the one hand, we demonstrate the successful extension and application of the multigrid by a volume agglomeration principle to the acceleration of complex 3-dimensional flow calculations on unstructured tetrahedral meshes and, on the other hand, we enhance further the efficiency of the methodology through its adaptation to parallel architectures. Moreover, a nontrivial aspect of this work is that the corresponding software developments are taking place in an existing industrial flow solver. This revised version was published online in June 2006 with corrections to the Cover Date.     

A multigrid method with unstructured adaptive grids for steady Euler equations

The multigrid method based on multi-stage Jacobi relaxation, earlier developed by the authors for structured grid calculations with Euler equations, is extended to unstructured grid applications. The meshes are generated with Delaunay triangulation algorithms and are adapted to the flow solution.     

A two-phase flow with a viscous and an inviscid fluid

We study the free boundary between a viscous and an inviscid fluid satisfying the Navier-Stokes and Euler equations respectively. Surface tension is incorporated. We read the equations as a free boundary problem for one viscous fluid with a nonlocal boundary force. We decompose the pressure distribution in the inviscid fluid into two contributions. A positivity result for the first, and a compactness property for the second contribution are dervied. We prove a short time existence theorem for the two-phase problem