A two-level computational graph method for the adjoint of a finite volume based compressible unsteady flow solver

The adjoint method is a useful tool for finding gradients of design objectives with respect to system parameters for fluid dynamics simulations. But the utility of this method is hampered by the difficulty in writing an efficient implementation for the adjoint flow solver, especially one that scales to thousands of cores. This paper demonstrates a Python library, called adFVM, that can be used to construct an explicit unsteady flow solver and derive the corresponding discrete adjoint flow solver using automatic differentiation (AD). The library uses a two-level computational graph method for representing the structure of both solvers. The library translates this structure into a sequence of optimized kernels, significantly reducing its execution time and memory footprint. Kernels can be generated for heterogeneous architectures including distributed memory, shared memory and accelerator based systems. The library is used to write a finite volume based compressible flow solver. A wall clock time comparison between different flow solvers and adjoint flow solvers built using this library and state of the art graph based AD libraries is presented on a turbomachinery flow problem. Performance analysis of the flow solvers is carried out for CPUs and GPUs. Results of strong and weak scaling of the flow solver and its adjoint are demonstrated on subsonic flow in a periodic box.     

Non-Nested Multi-Level Solvers for Finite Element Discretisations of Mixed Problems

We consider a general framework for analysing the convergence of multi-grid solvers applied to finite element discretisations of mixed problems, both of conforming and nonconforming type. As a basic new feature, our approach allows to use different finite element discretisations on each level of the multi-grid hierarchy. Thus, in our multi-level approach, accurate higher order finite element discretisations can be combined with fast multi-level solvers based on lower order (nonconforming) finite element discretisations. This leads to the design of efficient multi-level solvers for higher order finite element discretisations. Received May 17, 2001; revised February 2, 2002 Published online April 25, 2002     

Efficient solution of lattice equations by the recovery method Part I: Scalar elliptic problems

In this paper, an efficient solver for high dimensional lattice equations will be introduced. We will present a new concept, the recovery method, to define a bilinear form on the continuous level which has equivalent energy as the original lattice equation. The finite element discretisation of the continuous bilinear form will lead to a stiffness matrix which serves as an quasi-optimal preconditioner for the lattice equations. Since a large variety of efficient solvers are available for linear finite element problems the new recovery method allows to apply these solvers for unstructured lattice problems.     

Coupling of a nonlinear finite element structural method with a Navier-Stokes solver

A new three-dimensional viscous aeroelastic solver is developed in the present work. A well validated full Navier-Stokes code is coupled with a nonlinear finite element plate model. Implicit coupling between the computational fluid dynamics and structural solvers is achieved using a subiteration approach. Computations of several benchmark static and dynamic plate problems are used to validate the finite element portion of the code. This coupled aeroelastic scheme is then applied to the problem of three-dimensional panel flutter. Inviscid and viscous supersonic results match previous computations using the same aerodynamic method coupled with a finite difference structural solver. For the case of subsonic flow, multiple solutions consisting of static, upward and downward deflections of the panel are discussed. The particular solution obtained is shown to be sensitive to the cavity pressure specified underneath the panel.     

Stability and Convergence Analysis of a Class of Continuous Piecewise Polynomial Approximations for Time-Fractional Differential Equations

Sparse regularization plays a central role in many recent developments in imaging and other related fields. However, it is still of limited use in numerical solvers for partial differential equations (PDEs). In this paper we investigate the use of \(\ell _1\) regularization to promote sparsity in the shock locations of hyperbolic PDEs. We develop an algorithm that uses a high order sparsifying transform which enables us to effectively resolve shocks while still maintaining stability. Our method does not require a shock tracking procedure nor any prior information about the number of shock locations. It is efficiently implemented using the alternating direction method of multipliers. We present our results on one and two dimensional examples using both finite difference and spectral methods as underlying PDE solvers.     

QR-algebraic method for approximating zeros of system of polynomials

We present a new method for computing zeros of polynomial systems using the algebraic solver and the QR-method. It is based on the theory of algebraic solvers. The unstable calculation of the determinant of the large matrix is replaced by a stable technique using the QR-method. Algorithms and numerical results are presented.     

Parallel methods for optimality criteria-based topology optimization

Topology optimization problems require the repeated solution of finite element problems that are often extremely ill-conditioned due to highly heterogeneous material distributions. This makes the use of iterative linear solvers inefficient unless appropriate preconditioning is used. Even then, the solution time for topology optimization problems is typically very high. These problems are addressed by considering the use of non-overlapping domain decomposition-based parallel methods for the solution of topology optimization problems. The parallel algorithms presented here are based on the solid isotropic material with penalization (SIMP) formulation of the topology optimization problem and use the optimality criteria method for iterative optimization. We consider three parallel linear solvers to solve the equilibrium problem at each step of the iterative optimization procedure. These include two preconditioned conjugate gradient (PCG) methods: one using a diagonal preconditioner and one using an incomplete LU factorization preconditioner with a drop tolerance. A third substructuring solver that employs a hybrid of direct and iterative (PCG) techniques is also studied. This solver is found to be the most effective of the three solvers studied, both in terms of parallel efficiency and in terms of its ability to mitigate the effects of ill-conditioning. In addition to examining parallel linear solvers, we consider the parallelization of the iterative optimality criteria method. To tackle checkerboarding and mesh dependence, we propose a multi-pass filtering technique that limits the number of “ghost” elements that need to be exchanged across interprocessor boundaries.     

基于OpenCL的并行方腔流加速性能分析*

本文提出了一种使用OpenCL技术对方腔流问题进行加速计算的方法。在计算方腔流问题时,本文将其转换为Ｎ-Ｓ方程通过空间有限差分和龙格库塔时间差分求解,并使用局部缓存等技术进行GPU优化。实验在Nvidia和ATI平台对所给算法进行评测。结果显示,OpenCL相对其串行版本加速约30倍左右。     

Coupling of two- and three-dimensional hydrodynamic numerical models for simulating wind-induced currents in deep basins

The main interest of the present study is the simulation of wind-induced currents in closed water bodies with shallow and deep regions. This paper describes a low time consumption numerical modelling technique for the simulation of free-surface flow over a geometrically complex bed. To achieve this, a technique employing coupled two- and three-dimensional flow solvers is developed for simulation of the flow. The conjunctive model consists of an upper part 2D Shallow Water Flow Solver (2D-SWFS) coupled with a 3D pseudo-compressible flow solver (3D-PCFS) for the deep regions with a proper interface boundary condition. The 2D-SWFS and 3D-PCFS solvers are coupled via an interfacial shear stress gradient and pressure effects. Time stepping is performed for the 2D solver, and an iterative procedure is employed by the 3D solver to satisfy the equilibrium constraints for the interfacial boundary. The model is able to consider 2D wetting and drying shallow regions without any underlying deep water. Both the 2D and 3D models use nodal based Galerkin finite volume method (GFVM) for solving the governing equations on the unstructured meshes. The accuracy of both models in solving the effective phenomena is examined by comparing the results of simulated test cases with readily available analytical solutions and experimental measurements. Finally, the accuracy of the conjunctive model is assessed by comparing its results for test cases with analytical solutions and experimental measurements from the literature. The new simulation method is then used to solve a wind-induced flow problem in a basin with deep water surrounded by shallow water parts.     

Complex flow simulations in natural aquifer

Natural aquifers are complex media and contain heterogeneous structures. This paper introduces a new algorithm to simulate flow fluid in such complex media. A parallel version of the method is released, and two well-known sparse linear solvers, based, respectively, on a multifrontal Cholesky factorization and an iterative structured multigrid method, are tested. The mixed finite element (MFE) method is used to discretize Darcy’s equation. The efficiency of the algorithm proposed is shown in different numerical examples.     

Non-stationary iterative solvers on a PC cluster

In this study, we introduce cost effective strategies and algorithms for parallelizing the Krylov subspace based non-stationary iterative solvers such as Bi-CGM and Bi-CGSTAB for distributed computing on a cluster of PCs using ANULIB message passing libraries. We investigate the effectiveness of the parallel solvers on the linear systems resulting in numerical solution of some 2D and 3D nonlinear partial differential equations governing heat convection process by finite element, finite difference and wavelet based numerical schemes. Largely Bi-CGM is found to give better performance measured in terms of speedup factors.     

Applying SAT Solving in Classification of Finite Algebras

The classification of mathematical structures plays an important role for research in pure mathematics. It is, however, a meticulous task that can be aided by using automated techniques. Many automated methods concentrate on the quantitative side of classification, like counting isomorphism classes for certain structures with given cardinality. In contrast, we have devised a bootstrapping algorithm that performs qualitative classification by producing classification theorems that describe unique distinguishing properties for isomorphism classes. In order to fully verify the classification it is essential to prove a range of problems, which can become quite challenging for classical automated theorem provers even in the case of relatively small algebraic structures. But since the problems are in a finite domain, employing Boolean satisfiability solving is possible. In this paper we present the application of satisfiability solvers to generate fully verified classification theorems in finite algebra. We explore diverse methods to efficiently encode the arising problems both for Boolean SAT solvers as well as for solvers with built-in equational theory. We give experimental evidence for their effectiveness, which leads to an improvement of the overall bootstrapping algorithm.     

A multigrid scheme for 3D Monge–Ampère equations*

The elliptic Monge–Ampère equation is a fully nonlinear partial differential equation which has been the focus of increasing attention from the scientific computing community. Fast three-dimensional solvers are needed, for example in medical image registration but are not yet available. We build fast solvers for smooth solutions in three dimensions using a nonlinear full-approximation storage multigrid method. Starting from a second-order accurate centred finite difference approximation, we present a nonlinear Gauss–Seidel iterative method which has a mechanism for selecting the convex solution of the equation. The iterative method is used as an effective smoother, combined with the full-approximation storage multigrid method. Numerical experiments are provided to validate the accuracy of the finite difference scheme and illustrate the computational efficiency of the proposed multigrid solver.     

A performance assessment of NE/Nastran's new sparse direct and iterative solvers

Noran Engineering, Inc. has recently added two new solvers, Vector Sparse Solver (VSS) and Vector Iterative Solver (VIS), to its general-purpose finite element analysis engine, NE/Nastran. One solver uses a direct approach while the other uses an iterative Preconditioned Conjugate Gradient (PCG) approach. Both solvers are fully sparse and store and operate only on nonzero matrix elements. This paper looks at the effect these solvers have on the performance of NE/Nastran for various finite element model and solution types. In many cases performance has increased by a factor of 10, thus allowing jobs that took days to be solved in minutes.     

Partitioned but strongly coupled iteration schemes for nonlinear fluid–structure interaction

We look at the computational procedure of computing the response of a coupled fluid–structure interaction problem. We use the so-called strong fluid–structure coupling––a totally implicit formulation. At each time step in an implicit formulation, new values for the solution variables have to be computed by solving a nonlinear system of equations, where we assume that we have solvers for the subproblems. This is often the case, when we have existing software to solve each subproblem separately, and want to couple both. We show how to solve the overall nonlinear system by using only the solvers for the subproblems. This is achieved not by considering the equilibrium equations, but the fixed-point problem resulting from the solution iteration for each of the subproblems.     

An Efficient Correction Method to Obtain a Formally Third-Order Accurate Flow Solver for Node-Centered Unstructured Grids

A new method of obtaining third-order accuracy on unstructured grid flow solvers is presented. The method involves a simple correction to a traditional linear Galerkin scheme on tetrahedra and can be conveniently added to existing second-order accurate node-centered flow solvers. The correction involves gradients of the flux computed with a quadratic least squares approximation. However, once the gradients are computed, no second derivative information or high-order quadrature is necessary to achieve third-order accuracy. The scheme is analyzed both analytically using truncation error, and numerically using solution error for an exact solution to the Euler equations. Two demonstration cases for steady, inviscid flow reveal increased accuracy and excellent shock capturing with no loss in steady-state convergence rate. Computational timing results are presented which show the additional expense from the correction is modest compared to the increase in accuracy.     

The solution of elliptic partial differential equations using number theoretic transforms with application to narrow or limited computer hardware

A new variation of the transform method for solving discretised elliptic partial differential equations is discussed. Elements of the algebraic approximation to the p.d.e. are scaled and quantised on a finite range of integer values. The resulting integer algebraic equations are solved using transforms with the cyclic convolution property in finite rings of interests. These transforms are particularly efficient on computers with limited or narrow hardware. The resulting p.d.e. solvers are fast and have no roundoff.     

Deterministic finite automata representation for model predictive control of hybrid systems

As is well known, the computational complexity in the mixed integer programming (MIP) problem is one of the main issues in model predictive control (MPC) of hybrid systems such as mixed logical dynamical systems. Thus several efficient MIP solvers such as multi-parametric MIP solvers have been extensively developed to cope with this problem. On the other hand, as an alternative approach to this issue, this paper addresses how a deterministic finite automaton, which is a part of a hybrid system, should be expressed to efficiently solve the MIP problem to which the MPC problem is reduced. More specifically, a modeling method to represent a deterministic finite automaton in the form of a linear state equation with a smaller set of binary input variables and binary linear inequalities is proposed. After a motivating example is described, a derivation procedure of a linear state equation with linear inequalities representing a deterministic finite automaton is proposed as three steps; modeling via an implicit system, coordinate transformation to a linear state equation, and state feedback binarization. Various significant properties on the proposed modeling are also presented throughout the proofs on the derivation procedure.     

Moving-body simulations using overset framework with rigid body dynamics

The simulation of flow past bodies in relative motion is a challenging task due to the presence of complex flow features, moving grids, and rigid body movements under the action of external forces and moments. A generalized grid-based overset framework is presented for the simulation of this class of problems. The equations that govern the fluid flows are cast in an integral form and are solved using a cell-centered finite volume upwind scheme. The rigid body dynamics equations are formulated using quaternion and are solved using fourth-order Runge–Kutta (RK) time integration. The overset framework and the six degree of freedom (6-DOF) rigid body dynamics simulators are developed in a library form for easy incorporation into existing flow solvers. The details of the flow solver, the 6-DOF library, and the overset framework are presented in this paper along with the validation results of the developed system.     

Performance analysis of parallel Schwarz preconditioners in the LES of turbulent channel flows

We present a comparative study of parallel Schwarz preconditioners in the solution of linear systems arising in a Large Eddy Simulation (LES) procedure for turbulent plane channel flows. This procedure applies a time-splitting technique to suitably filtered Navier–Stokes equations, in order to decouple the continuity and momentum equations, and uses a semi-implicit scheme for time integration and finite volumes for space discretisation. This approach requires the solution of four sparse linear systems at each time step, accounting for a large part of the overall simulation; hence the linear system solvers are a crucial component in the whole procedure. Several preconditioners are applied in the simulation of a reference test case for the LES community, using discretisation grids of different sizes, with the aim of analysing the effects of different algorithmic choices defining the preconditioners, and identifying the most effective ones for the selected problem. The preconditioners, coupled with the GMRES method, are run within SParC-LES, a recently developed LES code based on the PSBLAS and MLD2P4 libraries for parallel sparse matrix computations and preconditioning.