A MIMD implementation of a parallel Euler solver for unstructured grids

A mesh-vertex finite volume scheme for solving the Euler equations on triangular unstructured meshes is implemented on a MIMD (multiple instruction/multiple data stream) parallel computer. Three partitioning strategies for distributing the work load onto the processors are discussed. Issues pertaining to the communication costs are also addressed. We find that the spectral bisection strategy yields the best performance. The performance of this unstructured computation on the Intel iPSC/860 compares very favorably with that on a one-processor CRAY Y-MP/1 and an earlier implementation on the Connection Machine.The authors are employees of Computer Sciences Corporation. This work was funded under contract NAS 2-12961     

Implementation of a parallel unstructured Euler solver on shared- and distributed-memory architectures

An efficient three-dimensional unstructured Euler solver is parallelized on a CRAY Y-MP C90 shared-memory computer and on an Intel Touchstone Delta distributed-memory computer. This paper relates the experiences gained and describes the software tools and hardware used in this study. Performance comparisons between the two differing architectures are made.This work was sponsored in part by ARPA (NAG-1-1485) and by NASA Contract No. NAS1-19480 while authors Mavriplis, Saltz and Das were in residence at ICASE, NASA Langley Research Center, Hampton, Virginia. This research was performed in part using the Intel Touchstone Delta System operated by Caltech on behalf of the Concurrent Supercomputing Consortium. Access to this fecility was provided by NASA Langley Research Center and the Center for Research in Parallel Processing. The content of the information does not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred.     

An automatic solver for very large jigsaw puzzles using genetic algorithms

In this paper we propose the first effective genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel crossover procedure that merges two “parent” solutions to an improved “child” configuration by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance, as far as handling previously attempted puzzles more accurately and efficiently, as well puzzle sizes that have not been attempted before. The extended experimental results provided in this paper include, among others, a thorough inspection of up to 30,745-piece puzzles (compared to previous attempts on 22,755-piece puzzles), using a considerably faster concurrent implementation of the algorithm. Furthermore, we explore the impact of different phases of the novel crossover operator by experimenting with several variants of the GA. Finally, we compare different fitness functions and their effect on the overall results of the GA-based solver.     

Assessment of implicit operators for the upwind point Gauss-Seidel method on unstructured meshes

The effect of the numerical dissipation level of implicit operators on the stability and convergence characteristics of the upwind point Gauss-Seidel (GS) method for solving the Euler equations was studied through the von Neumann stability analysis and numerical experiments. The stability analysis for linear model equations showed that the point GS method is unstable even for very small CFL numbers when the numerical dissipation level of the implicit operator is equivalent to that of the explicit operator. The stability restriction is rapidly alleviated as the dissipation level of the implicit operator increases. The instability predicted by the linear stability analysis was further amplified as the flow problems became stiffer due to the presence of the shock wave or the refinement of the mesh. It was found that for the efficiency and the robustness of the upwind point GS method, the numerical flux of the implicit operator needs to be more dissipative than that of the explicit operator.     

Conservative upwind difference schemes for the Euler equations

In a recent paper [1] a number of numerical schemes for the shallow water equations based on a conservative linearization are analyzed. In particular, it is established that the schemes are related through the use of a source term. In this paper this technique is applied to the Euler equations, and further analysis suggests a new formulation of an existing scheme having the same key properties.     

A curved-element unstructured discontinuous Galerkin method on GPUs for the Euler equations

In this work we consider Runge–Kutta discontinuous Galerkin methods for the solution of hyperbolic equations enabling high order discretization in space and time. We aim at an efficient implementation of DG for Euler equations on GPUs. A mesh curvature approach is presented for the proper resolution of the domain boundary. This approach is based on the linear elasticity equations and enables a boundary approximation with arbitrary, high order. In order to demonstrate the performance of the boundary curvature a massively parallel solver on graphics processors is implemented and utilized for the solution of the Euler equations of gas-dynamics.     

A multi-dimensional solver for the steady Euler equations

In this paper a numerical algorithm for the solution of the multi-dimensional steady Euler equations in conservative and non-conservative form is presented. Most existing standard and multi-dimensional schemes use flux balances with assumed constant distribution of variables along each cell edge, which interfaces two grid cells. This assumption is believed to be one of the main reasons for the limited advantage gained from multi-dimensional high order discretisations compared to standard one-dimensional ones. The present algorithm is based on the optimisation of polynomials describing the distribution of flow variables in grid cells, where only polynomials that satisfy the Euler equations in the entire grid cell can be selected. The global solution is achieved if all polynomials and by that the flow variables are continuous along edges interfacing neighbouring grid cells. A discrete approximation of a given spatial order is converged if the deviation between polynomial distributions of adjacent grid cells along the interfacing edge of the cells is minimal. Results from the present scheme between first and fifth order spatial accuracy are compared to standard first and second order Roe computations for simple test cases demonstrating the gain in accuracy for a number of sub- and supersonic flow problems.     

A massively parallel Eikonal solver on unstructured meshes

Algorithms for the numerical solution of the Eikonal equation discretized with tetrahedra are discussed. Several massively parallel algorithms for GPU computing are developed. This includes domain decomposition concepts for tracking the moving wave fronts in sub-domains and over the sub-domain boundaries. Furthermore a low memory footprint implementation of the solver is introduced which reduces the number of arithmetic operations and enables improved memory access schemes. The numerical tests for different meshes originating from the geometry of a human heart document the decreased runtime of the new algorithms.

     

An upwind discretization scheme for the finite volume lattice Boltzmann method

The fact that the classic lattice Boltzmann method is restricted to Cartesian Grids has inspired several researchers to apply Finite Volume [Nannelli F, Succi S. The lattice Boltzmann equation on irregular lattices. J Stat Phys 1992;68:401–7; Peng G, Xi H, Duncan C, Chou SH. Finite volume scheme for the lattice Boltzmann method on unstructured meshes. Phys Rev E 1999;59:4675–82; Chen H. Volumetric formulation of the lattice Boltzmann method for fluid dynamics: basic concept. Phys Rev E 1998;58:3955–63] or Finite Element [Lee T, Lin CL. A characteristic Galerkin method for discrete Boltzmann equation. J Comp Phys 2001;171:336–56; Shi X, Lin J, Yu Z. Discontinuous Galerkin spectral element lattice Boltzmann method on triangular element. Int J Numer Methods Fluids 2003;42:1249–61] methods to the Discrete Boltzmann equation. The finite volume method proposed by Peng et al. works on unstructured grids, thus allowing an increased geometrical flexibility. However, the method suffers from substantial numerical instability compared to the standard LBE models. The computational efficiency of the scheme is not competitive with standard methods.We propose an alternative way of discretizing the convection operator using an upwind scheme, as opposed to the central scheme described by Peng et al. We apply our method to some test problems in two spatial dimensions to demonstrate the improved stability of the new scheme and the significant improvement in computational efficiency. Comparisons with a lattice Boltzmann solver working on a hierarchical grid were done and we found that currently finite volume methods for the discrete Boltzmann equation are not yet competitive as stand alone fluid solvers.     

An automatic class generation mechanism by using method integration

The paper presents a mechanism for automatically generating new classes from classes existing in a library by using their modification histories. To generate classes that are likely to meet a programmer's requirements and that are consistent with the existing classes, we propose three actors: a Specifier, a Finder, and an integrator. The Specifier records the history of modifications between methods with the same interface of a parent class and its heir. If the required method is not defined in the existing class which a programmer is referring to, the Finder retrieves classes similar to the referenced class and the Integrator applies the past modifications of similar classes to the referenced class. Classes are determined to be similar, based on their positions in a class hierarchy tree. Both the Specifier and Integrator are achieved by using a method integration algorithm based on object oriented bounded program slicing and class dependence graph matching. This mechanism enables programmers to reuse classes with little or no modification, and thus, easily create object oriented programs     

Incompressible flow computations over moving boundary using a novel upwind method

In this paper a novel method for simulating unsteady incompressible viscous flow over a moving boundary is described. The numerical model is based on a 2D Navier–Stokes incompressible flow in artificial compressibility formulation with Arbitrary Lagrangian Eulerian approach for moving grid and dual time stepping approach for time accurate discretization. A higher order unstructured finite volume scheme, based on a Harten Lax and van Leer with Contact (HLLC) type Riemann solver for convective fluxes, developed for steady incompressible flow in artificial compressibility formulation by Mandal and Iyer (AIAA paper 2009-3541), is extended to solve unsteady flows over moving boundary. Viscous fluxes are discretized in a central differencing manner based on Coirier’s diamond path. An algorithm based on interpolation with radial basis functions is used for grid movements. The present numerical scheme is validated for an unsteady channel flow with a moving indentation. The present numerical results are found to agree well with experimental results reported in literature.     

A multi-dimensional HLL-Riemann solver for Euler equations of gas dynamics

This article presents a numerical model that enables to solve on unstructured triangular meshes and with a high-order of accuracy, a multi-dimensional Riemann problem that appears when solving hyperbolic problems.For this purpose, we use a MUSCL-like procedure in a “cell-vertex” finite-volume framework.In the first part of this procedure, we devise a four-state bi-dimensional HLL solver (HLL-2D). This solver is based upon the Riemann problem generated at the centre of gravity of a triangular cell, from surrounding cell-averages. A new three-wave model makes it possible to solve this problem, approximately. A first-order version of the bi-dimensional Riemann solver is then generated for discretizing the full compressible Euler equations.In the second part of the MUSCL procedure, we develop a polynomial reconstruction that uses all the surrounding numerical data of a given point, to give at best third-order accuracy. The resulting over determined system is solved by using a least-square methodology. To enforce monotonicity conditions into the polynomial interpolation, we develop a simplified central WENO (CWENO) procedure.Numerical tests and comparisons with competing numerical methods enable to identify the salient features of the whole model.     

A high efficiency parallel unstructured solver dedicated to internal combustion engine simulation

IFP-C3D, a hexahedral unstructured parallel solver dedicated to multiphysics calculation is being developed at IFP to compute the compressible combustion in internal engines. IFP-C3D uses an unstructured formalism, the finite volume method on staggered grid, time splitting, SIMPLE loop, subcycled advection, turbulent and Lagrangian spray and a liquid film model. Original algorithms and models such as the conditional temporal interpolation methodology for moving grids, the remapping algorithm for transferring quantities on different meshes during the computation enable IFP-C3D to deal with complex moving geometries with large volume deformation induced by all moving geometrical parts (intake/exhaust valve, piston). Large super-scalar machines up to 1000 processors are being widely used and IFP-C3D has been optimized for running on these Cluster machines. IFP-C3D is parallelized using the Message Passing Interface (MPI) library to distribute a calculation over a large number of processors. Moreover, IFP-C3D uses an optimized linear algebraic library to solve linear matrix systems and the METIS partitionner library to distribute the computational load equally for all meshes used during the calculation and in particular during the remap stage when new meshes are loaded. Numerical results and performance timing are presented to demonstrate the computational efficiency of the code.     

An innovative eigenvalue problem solver for free vibration of Euler–Bernoulli beam by using the Adomian decomposition method

This paper deals with free vibration problems of Euler–Bernoulli beam under various supporting conditions. The technique we have used is based on applying the Adomian decomposition method (ADM) to our vibration problems. Doing some simple mathematical operations on the method, we can obtain ith natural frequencies and mode shapes one at a time. The computed results agree well with those analytical and numerical results given in the literature. These results indicate that the present analysis is accurate, and provides a unified and systematic procedure which is simple and more straightforward than the other modal analysis.     

An image segmentation method using automatic threshold based on improved genetic selecting algorithm

In this paper, an image segmentation method using automatic threshold based on improved genetic selecting algorithm is presented. Optimal threshold for image segmentation is converted into an optimization problem in this new method. In order to achieve good effects for image segmentation, the optimal threshold is solved by using optimizing efficiency of improved genetic selecting algorithm that can achieve a global optimum. The genetic selecting algorithm is optimized by using simulated annealing temperature parameters to achieve appropriate selective pressures. Encoding, crossover, mutation operator and other parameters of genetic selecting algorithm are improved moderately in this method. It can overcome the shortcomings of the existing image segmentation methods, which only consider pixel gray value without considering spatial features and large computational complexity of these algorithms. Experiment results show that the new algorithm greatly reduces the optimization time, enhances the anti-noise performance of image segmentation, and improves the efficiency of image segmentation. Experimental results also show that the new algorithm can get better segmentation effect than that of Otsu’s method when the gray-level distribution of the background follows normal distribution approximately, and the target region is less than the background region. Therefore, the new method can facilitate subsequent processing for computer vision, and can be applied to realtime image segmentation.     

An extended GPU radiosity solver

In this paper we present an extended GPU progressive radiosity solver which integrates ideal diffuse as well as specular transmittance and reflection. The solver is capable to handle multiple specular reflections with correct mirror–object–mirror occlusions. The use of graphics hardware allows to consider attenuation of radiation due to reflections and/or transmissions on a per-pixel basis, enabling us to handle multiple specular triangles with different reflection coefficients at once. Alpha masks are used to replace complex geometry in certain cases to reduce computation times. Furthermore, the inclusion of ambient overshooting into the radiosity solver is discussed.     

Curvature and entropy based wall boundary condition for the high order spectral volume Euler solver

A curvature and entropy based wall boundary condition is implemented in the high order spectral volume (SV) context. This method borrows ideas from the “curvature-corrected symmetry technique” developed by (Dadone A, Grossman B. Surface Boundary Conditions for Compressible Flows. AIAA J 1994; 32(2): 285–93), for a low order structured grid Euler solver. After numerically obtaining the curvature, the right state (by convention, the left state is inside the computational domain and the right state lies outside of the computational domain) face pressure values are obtained by solving a linearised system of equations. This is unlike that of the lower order finite volume and difference simulations, wherein the right state face values are trivial to obtain. The right state face density values are then obtained by enforcing entropy conservation. Accuracy studies show that simulations performed by employing the new boundary conditions deliver much more accurate results than the ones which employ traditional boundary conditions, while at the same time asymptotically reaching the desired order of accuracy. Numerical results for two-dimensional inviscid flows around the NACA0012 airfoil and over a bump with the new boundary condition showed dramatic improvements over those with the conventional approach. In all cases and orders, spurious entropy productions with the new boundary treatment are significantly reduced. In general, the numerical results are very promising and indicate that the approach has a great potential for 3D high order simulations.     

Diffusion and dispersion errors of the flux corrected upwind method

The inviscid form of Burger's equation is solved numerically using the flux corrected upwind method. A nonlinear Hirt stability analysis is carried out. It is shown that the flux limiting process is responsible for modifying the advection speed in the shock region to reduce the dispersion errors. The linear and the nonlinear diffusion coefficients are of the same sign i.e. diffusion errors are dominant. The flux limiter preserves the conservation property.