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.     

Hybrid grid generation for two-dimensional high-Reynolds flows

An hybrid mesh generation algorithm for two-dimensional viscous flows at high-Reynolds number is presented. An advancing-front method is used close to solid surfaces and in the wake region(s). The boundary layer and wake grids possibly contain both highly stretched quadrilateral and triangular elements. The latter are inserted locally to improve the quality of the grid, thus circumventing some drawbacks of standard structured grid advancing-front methods. An advancing-front/Delaunay algorithm triangulates the remaining portion of the computational domain. An overview of both algorithms is given and results for viscous laminar and turbulent compressible flows around single and multi-element airfoils are shown to support the present approach.     

An implicit gas-kinetic scheme for turbulent flow on unstructured hybrid mesh

In this study, an implicit scheme for the gas-kinetic scheme (GKS) on the unstructured hybrid mesh is proposed. The Spalart–Allmaras (SA) one equation turbulence model is incorporated into the implicit gas-kinetic scheme (IGKS) to predict the effects of turbulence. The implicit macroscopic governing equations are constructed and solved by the matrix-free lower-upper symmetric-Gauss–Seidel (LU-SGS) method. To reduce the number of cells and computational cost, the hybrid mesh is applied. A modified non-manifold hybrid mesh data(NHMD) is used for both unstructured hybrid mesh and uniform grid. Numerical investigations are performed on different 2D laminar and turbulent flows. The convergence property and the computational efficiency of the present IGKS method are investigated. Much better performance is obtained compared with the standard explicit gas-kinetic scheme. Also, our numerical results are found to be in good agreement with experiment data and other numerical solutions, demonstrating the good applicability and high efficiency of the present IGKS for the simulations of laminar and turbulent flows.     

A block LU-SGS implicit unsteady incompressible flow solver on hybrid dynamic grids for 2D external bio-fluid simulations

A hybrid dynamic grid generation technique for two-dimensional (2D) morphing bodies and a block lower-upper symmetric Gauss-Seidel (BLU-SGS) implicit dual-time-stepping method for unsteady incompressible flows are presented for external bio-fluid simulations. To discretize the complicated computational domain around 2D morphing configurations such as fishes and insect/bird wings, the initial grids are generated by a hybrid grid strategy firstly. Body-fitted quadrilateral (quad) grids are generated first near solid bodies. An adaptive Cartesian mesh is then generated to cover the entire computational domain. Cartesian cells which overlap the quad grids are removed from the computational domain, and a gap is produced between the quad grids and the adaptive Cartesian grid. Finally triangular grids are used to fill this gap. During the unsteady movement of morphing bodies, the dynamic grids are generated by a coupling strategy of the interpolation method based on ‘Delaunay graph’ and local remeshing technique. With the motion of moving/morphing bodies, the grids are deformed according to the motion of morphing body boundaries firstly with the interpolation strategy based on ‘Delaunay graph’ proposed by Liu and Qin. Then the quality of deformed grids is checked. If the grids become too skewed, or even intersect each other, the grids are regenerated locally. After the local remeshing, the flow solution is interpolated from the old to the new grid. Based on the hybrid dynamic grid technique, an efficient implicit finite volume solver is set up also to solve the unsteady incompressible flows for external bio-fluid dynamics. The fully implicit equation is solved using a dual-time-stepping approach, coupling with the artificial compressibility method (ACM) for incompressible flows. In order to accelerate the convergence history in each sub-iteration, a block lower-upper symmetric Gauss-Seidel implicit method is introduced also into the solver. The hybrid dynamic grid generator is tested by a group of cases of morphing bodies, while the implicit unsteady solver is validated by typical unsteady incompressible flow case, and the results demonstrate the accuracy and efficiency of present solver. Finally, some applications for fish swimming and insect wing flapping are carried out to demonstrate the ability for 2D external bio-fluid simulations.     

A novel approach of three-dimensional hybrid grid methodology: Part 1. Grid generation

We propose a novel approach of three-dimensional hybrid grid methodology, the DRAGON grid method in the three-dimensional space. The DRAGON grid is created by means of a Direct Replacement of Arbitrary Grid Overlapping by Nonstructured grid, and is structured-grid dominated with unstructured grids in small regions. The DRAGON grid scheme is an adaptation to the Chimera thinking. It is capable of preserving the advantageous features of both the structured and unstructured grids, and eliminates/minimizes their shortcomings. In the present paper, we describe essential and programming aspects, and challenges of the three-dimensional DRAGON grid method, with respect to grid generation. We demonstrate the capability of generating computational grids for multi-components complex configurations.     

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     

A block LU-SGS implicit dual time-stepping algorithm for hybrid dynamic meshes

A block lower-upper symmetric Gauss-Seidel (BLU-SGS) implicit dual time-stepping method is developed for moving body problems with hybrid dynamic grids. To simulate flows over complex configurations, a hybrid grid method is adopted in this paper. Body-fitted quadrilateral (quad) grids are generated first near solid bodies. An adaptive Cartesian mesh is then generated to cover the entire computational domain. Cartesian cells which overlap the quad grids are removed from the computational domain, and a gap is produced between the quad grids and the adaptive Cartesian grid. Finally triangular grids are used to fill this gap. With the motion of moving bodies, the quad grids move with the bodies, while the adaptive Cartesian grid remains stationary. Meanwhile, the triangular grids are deformed according to the motion of solid bodies with a ‘spring’ analogy approach. If the triangular grids become too skewed, or the adaptive Cartesian grid crosses into the quad grids, the triangular grids are regenerated. Then the flow solution is interpolated from the old to the new grid. The fully implicit equation is solved using a dual time-stepping solver. A Godunov-type scheme with Roe’s flux splitting is used to compute the inviscid flux. Several sub-iteration schemes are investigated in this study. Both supersonic and transonic unsteady cases are tested to demonstrate the accuracy and efficiency of the method.     

Multi-objective optimization of free-form grid structures

Computational modeling software facilitates the creation of any surface geometry imaginable, but it is not always obvious how to create an efficient grid shell structure on a complex surface. This paper presents a design tool for synthesis of optimal grid structures, using a Multi-Objective Genetic Algorithm to vary rod directions over the surface in response to two or more load cases. A process of grid homogenization allows the tool to be rapidly applied to any grid structure consisting of a repeating unit cell, including quadrilateral, triangular and double layer grids. Two case studies are presented to illustrate the successful execution of the optimization procedure.     

The unconditionally positive-convergent implicit time integration scheme for two-equation turbulence models: Revisited

The unconditionally positive-convergent implicit scheme for two-equation turbulence models, originally developed by Mor-Yossef and Levy, is revisited. A compact, simple, and uniform reformulation of the method for the use of both structured and unstructured grid based flow solvers is presented. An analytical proof of the scheme revision is given showing that positivity of the turbulence model solutions and convergence of the turbulence model equations are guaranteed for any time step. Numerical experiments are conducted, simulating two test cases of three-dimensional complex flow fields using structured and hybrid unstructured grids. To demonstrate the overall scheme’s robustness, it is applied to non-linear k-ω and non-linear k- turbulence models. Results from the numerical simulations show that the scheme exhibits very good convergence characteristics, is robust, and it always preserves the positivity of the turbulence model dependent variables, even for an infinite time step.     

A folding/unfolding algorithm for the construction of semi-structured layers in hybrid grid generation

A method is presented for generating semi-structured layers in hybrid grids suitable for high Reynolds number flow simulations. It can produce superior quality grids around convex and concave ridges of the domain compared to a standard prismatic or advancing layers generator. In a first step, hybrid quadrilateral/triangular grids are employed to cluster the surface grid towards sharp corners and ridges. Starting from this surface grid as an initial front for the volume grid generation, a prismatic and hexahedral layers generation technique is used, containing degenerate faces to add or remove elements in convex or concave areas of the geometry respectively. The method can automatically create structured-like grids in concave gaps and better discretize the space around convex ridges to improve overall accuracy. The final grid remains conforming to not complicate the solver and post-processing requirements. Several examples illustrate the application of the method.     

基于非结构网格隐式算法的GPU加速研究

针对非结构网格隐式算法在GPU上的加速效果不佳的问题,通过分析GPU的架构及并行模式,研究并实现了基于非结构网格格点格式的隐式LU-SGS算法的GPU并行加速.通过采用RCM和Metis网格重排序（重组）方法,优化非结构网格的数据局部性,改善非结构网格的隐式算法在GPU上的并行加速效果.通过三维机翼算例验证了本文实现的正确性及效率.结果表明两种网格重排序（重组）方法分别得到了63%和69%的加速效果提高.优化后的LU-SGS隐式GPU并行算法获得了相较于CPU串行算法27倍的加速比,充分说明了本文方法的高效性.     

Domain decomposition based coupling between the lattice Boltzmann method and traditional CFD methods—Part I: Formulation and application to the 2-D Burgers’ equation

The lattice Boltzmann method is being increasingly employed in the field of computational fluid dynamics due to its computational efficiency. Floating-point operations in the lattice Boltzmann method involve local data and therefore allow easy cache optimization and parallelization. Due to this, the cache-optimized lattice Boltzmann method has superior computational performance over traditional finite difference methods for solving unsteady flow problems. When solving steady flow problems, the explicit nature of the lattice Boltzmann discretization limits the time step size and therefore the efficiency of the lattice Boltzmann method for steady flows. To quantify the computational performance of the lattice Boltzmann method for steady flows, a comparison study between the lattice Boltzmann method (LBM) and the alternating direction implicit (ADI) method was performed using the 2-D steady Burgers’ equation. The comparison study showed that the LBM performs comparatively poor on high-resolution meshes due to smaller time step sizes, while on coarser meshes where the time step size is similar for both methods, the cache-optimized LBM performance is superior. Because flow domains can be discretized with multiblock grids consisting of coarse and fine grid blocks, the cache-optimized LBM can be applied on the coarse grid block while the traditional implicit methods are applied on the fine grid blocks. This paper finds the coupled cache-optimized lattice Boltzmann-ADI method to be faster by a factor of 4.5 over the traditional methods while maintaining similar accuracy.     

The heat equation as grid smoothing in a local optimization procedure

We consider a local optimization technique, where starting from a preliminary version of the grid under consideration, we try to improve the part of the grid that really needs this improvement. When this procedure is performed, the processed grids may result irregular, so a smoothing step must be taken into account. We propose a smoothing approach based on an iterative formula resembling the explicit difference schemes for the heat equation. This is a quite general approach, however to fix the ideas it is described in the context of quadrilateral grid generation and the variational approach is considered as the base method for the solution of planar grid generation. Some numerical experiments are presented to show the efficiency of the proposed method.     

Dual Marching Cubes: Primal Contouring of Dual Grids

We present a method for contouring an implicit function using a grid topologically dual to structured grids such as octrees. By aligning the vertices of the dual grid with the features of the implicit function, we are able to reproduce thin features of the extracted surface without excessive subdivision required by methods such as Marching Cubes or Dual Contouring. Dual Marching Cubes produces a crack‐free, adaptive polygonalization of the surface that reproduces sharp features. Our approach maintains the advantage of using structured grids for operations such as CSG while being able to conform to the relevant features of the implicit function yielding much sparser polygonalizations than has been possible using structured grids.     

Variational method for hexahedral grid generation with control metric

A variational method of generating spatial structured (or regular) grids composed of hexahedral cells is considered. In the method it is minimized the functional, whose integrand is a dimensionless ratio of metric invariants. The functional depends on the metric elements of two metrics. One metric is induced by a curvilinear grid generated in the physical domain, while the other control metric given in a special way provides additional control of the cell shape such as condensing the coordinate surfaces and orthogonalizing the coordinate lines of the grid towards the domain boundary. Nondegeneracy conditions for the grid and the hexahedral cell are discussed. The method for redistributing nodes over the domain boundary is considered. Grid generation examples are given.     

Winslow Smoothing on Two-Dimensional Unstructured Meshes

The Winslow equations from structured elliptic grid generation are adapted to smoothing of two-dimensional unstructured meshes using a finite difference approach. We use a local mapping from a uniform N-valent logical mesh to a local physical subdomain. Taylor Series expansions are then applied to compute the derivatives which appear in the Winslow equations. The resulting algorithm for Winslow smoothing on unstructured triangular and quadrilateral meshes gives generally superior qualilty than traditional Laplacian smoothing, while retaining the resistance to mesh folding on structured quadrilateral meshes.     

Hierarchical grid conversion

Hierarchical grids appear in various applications in computer graphics such as subdivision and multiresolution surfaces, and terrain models. Since the different grid types perform better at different tasks, it is desired to switch between regular grids to take advantages of these grids. Based on a 2D domain obtained from the connectivity information of a mesh, we can define simple conversions to switch between regular grids. In this paper, we introduce a general framework that can be used to convert a given grid to another and we discuss the properties of these refinements such as their transformations. This framework is hierarchical meaning that it provides conversions between meshes at different level of refinement. To describe the use of this framework, we define new regular and near-regular refinements with good properties such as small factors. We also describe how grid conversion enables us to use patch-based data structures for hexagonal cells and near-regular refinements. To do so, meshes are converted to a set of quadrilateral patches that can be stored in simple structures. Near-regular refinements are also supported by defining two sets of neighborhood vectors that connect a vertex to its neighbors and are useful to address connectivity queries.     

A near optimal isosurface extraction algorithm using the span space

Presents the “Near Optimal IsoSurface Extraction” (NOISE) algorithm for rapidly extracting isosurfaces from structured and unstructured grids. Using the span space, a new representation of the underlying domain, we develop an isosurface extraction algorithm with a worst case complexity of o(√n+k) for the search phase, where n is the size of the data set and k is the number of cells intersected by the isosurface. The memory requirement is kept at O(n) while the preprocessing step is O(n log n). We utilize the span space representation as a tool for comparing isosurface extraction methods on structured and unstructured grids. We also present a fast triangulation scheme for generating and displaying unstructured tetrahedral grids     

Finite volume method on the unstructured grid system

Applying the Voronoi diagram to the cell system for the finite volume method, a new method on the unstructured grid system is devised for the simulation of incompressible steady flow. In this method, the SIMPLE algorithm can be applied with little expansion. The turbulent flow around the two-dimensional vehicle model is simulated with the k-ε turbulence model by this method. Comparing the calculation result with another result obtained using the structured grid system and the experimental data, the new method is shown to be suitable for the simulation of complex flow fields.