Robust and Efficient Wave Simulations on Deforming Meshes

The goal of this paper is to enable the interactive simulation of phenomena such as animated fluid characters. While full 3D fluid solvers achieve this with control algorithms, these 3D simulations are usually too costly for real‐time environments. In order to achieve our goal, we reduce the problem from a three‐ to a two‐dimensional one, and make use of the shallow water equations to simulate surface waves that can be solved very efficiently. In addition to a low runtime cost, stability is likewise crucial for interactive applications. Hence, we make use of an implicit time integration scheme to obtain a robust solver. To ensure a low energy dissipation, we apply an Implicit Newmark time integration scheme. We propose a general formulation of the underlying equations that is tailored towards the use with an Implicit Newmark integrator. Furthermore, we gain efficiency by making use of a direct solver. Due to the generality of our formulation, the fluid simulation can be coupled interactively with arbitrary external forces, such as forces caused by inertia or collisions. We will discuss the properties of our algorithm, and demonstrate its robustness with simulations on strongly deforming meshes.     

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.     

Combined finite volume–finite element method for shallow water equations

This paper is concerned with solving the viscous and inviscid shallow water equations. The numerical method is based on second-order finite volume–finite element (FV–FE) discretization: the convective inviscid terms of the shallow water equations are computed by a finite volume method, while the diffusive viscous terms are computed with a finite element method. The method is implemented on unstructured meshes. The inviscid fluxes are evaluated with the approximate Riemann solver coupled with a second-order upwind reconstruction. Herein, the Roe and the Osher approximate Riemann solvers are used respectively and a comparison between them is made. Appropriate limiters are used to suppress spurious oscillations and the performance of three different limiters is assessed. Moreover, the second-order conforming piecewise linear finite elements are used. The second-order TVD Runge–Kutta method is applied to the time integration. Verification of the method for the full viscous system and the inviscid equations is carried out. By solving an advection–diffusion problem, the performance assessment for the FV–FE method, the full finite volume method, and the discontinuous Galerkin method is presented.     

Performance of a new partitioned procedure versus a monolithic procedure in fluid–structure interaction

Fluid–structure interaction (FSI) can be simulated in a monolithic way by solving the flow and structural equations simultaneously and in a partitioned way with separate solvers for the flow equations and the structural equations. A partitioned quasi-Newton technique which solves the coupled problem through nonlinear equations corresponding to the interface position is presented and its performance is compared with a monolithic Newton algorithm. Various structural configurations with an incompressible fluid are solved, and the ratio of the time for the partitioned simulation, when convergence is reached, to the time for the monolithic simulation is found to be between 1/2 and 4. However, in this comparison of the partitioned and monolithic simulations, the flow and structural equations have been solved with a direct sparse solver in full Newton–Raphson iterations, only relatively small problems have been solved and this ratio would likely change if large industrial problems were considered or if other solution strategies were used.     

An Efficient Solver for Two‐way Coupling Rigid Bodies with Incompressible Flow

We present an efficient solver for monolithic two‐way coupled simulation of rigid bodies with incompressible fluids that is robust to poor conditioning of the coupled system in the presence of large density ratios between the solid and the fluid. Our method leverages ideas from the theory of Domain Decomposition, and uses a hybrid combination of direct and iterative solvers that exploits the low‐dimensional nature of the solid equations. We observe that a single Multigrid V‐cycle for the fluid equations serves as a very effective preconditioner for solving the Schur‐complement system using Conjugate Gradients, which is the main computational bottleneck in our pipeline. We use spectral analysis to give some theoretical insights behind this observation. Our method is simple to implement, is entirely assembly‐free besides the solid equations, allows for the use of large time steps because of the monolithic formulation, and remains stable even when the iterative solver is terminated early. We demonstrate the efficacy of our method on several challenging examples of two‐way coupled simulation of smoke and water with rigid bodies. To illustrate that our method is applicable to other problems, we also show an example of underwater bubble simulation.     

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.     

Randomized constraint solvers: a comparative study

The complexity of constraints is a major obstacle for constraint-based software verification. Automatic constraint solvers are fundamentally incomplete: input constraints often build on some undecidable theory or some theory the solver does not support. This paper proposes and evaluates several randomized solvers to address this issue. We compared the effectiveness of a symbolic solver (CVC3), a random solver, two heuristic search solvers, and seven hybrid solvers (i.e. mix of random, symbolic, and heuristic solvers). We evaluated the solvers on a benchmark generated with a concolic execution of 9 subjects. The performance of each solver was measured by its precision, which is the fraction of constraints that the solver can find solution out of the total number of constraints that some solver can find solution. As expected, symbolic solving subsumes the other approaches for the 4 subjects that only generate decidable constraints. For the remaining 5 subjects, which contain undecidable constraints, the hybrid solvers achieved the highest precision (fraction of constraints that a solver can find a solution out of the total number of satisfiable constraints). We also observed that the solvers were complementary, which suggests that one should alternate their use in iterations of a concolic execution driver.     

Solution properties and approximate Riemann solvers for two-layer shallow flow models

The 4 × 4 system of governing equations for two-layer shallow flow models is known to exhibit particular behaviours such as loss of hyperbolicity under certain flow configurations. An eigenvalue analysis of the conservation part of the equations shows that the loss of hyperbolicity is due only to the reaction exerted by each fluid onto the other at the interface between the fluids. Three Riemann solvers derived from the HLL formalism are presented. In the first solver, the pressure-induced terms are accounted for by the source term; in the second solver, they are incorporated into the fluxes; the third solver uses the same formulation as the first, except that the mass and momentum balance for the bottom layer are replaced with the balance equations for the system formed by the two layers as a whole. Numerical results using the three solvers are presented for (1) static conditions such as two fluids of identical densities at rest above each other, (2) dam-break flows involving the collapse of a body of light fluid over a uniform layer of a denser fluid, and (3) Liska and Wendroff’s ill-posed test cases [24] involving two-layer flows over a topographic bump. The three solvers produce quasi-undistinguishable results for the dam-break flows, and produce sharp solutions over the full range of density ratio, from 0 to 1. However, only the third solver allows a strict preservation of static configurations. Moreover, a method is proposed to assess the convergence of the numerical solutions in the configurations for which no analytical solution can be obtained.     

Multi-solver algorithms for the partitioned simulation of fluid–structure interaction

In partitioned fluid–structure interaction simulations, the flow equations and the structural equations are solved separately. As a result, a coupling algorithm is needed to enforce the equilibrium on the fluid–structure interface in cases with strong interaction. This coupling algorithm performs coupling iterations between the solver of the flow equations and the solver of the structural equations. Current coupling algorithms couple one flow solver with one structural solver. Here, a new class of multi-solver quasi-Newton coupling algorithms for unsteady fluid–structure interaction simulations is presented. More than one flow solver and more than one structural solver are used for a single simulation. The numerical experiments demonstrate that the duration of a simulation decreases as the number of solvers is increased.