Search

We present a novel method for faster physics simulations of elastic solids. Our key idea is to reorder the unknown variables according to the Fiedler vector (i.e., the second-smallest eigenvector) of the combinatorial Laplacian. It is well known in the geometry processing community that the Fiedler vector brings together vertices that are geometrically nearby, causing fewer cache misses when computing differential operators. However, to the best of our knowledge, this idea has not been exploited to accelerate simulations of elastic solids which require an expensive linear (or non-linear) system solve at every time step. The cost of computing the Fiedler vector is negligible, thanks to an algebraic Multigrid-preconditioned Conjugate Gradients (AMGPCG) solver. We observe that our AMGPCG solver requires approximately 1 s for computing the Fiedler vector for a mesh with approximately 50K vertices or 100K tetrahedra. Our method provides a speed-up between 10 % – 30 % at every time step, which can lead to considerable savings, noting that even modest simulations of elastic solids require at least 240 time steps. Our method is easy to implement and can be used as a plugin for speeding up existing physics simulators for elastic solids, as we demonstrate through our experiments using the Vega library and the ADMM solver, which use different algorithms for elasticity. [ABSTRACT FROM AUTHOR]

We consider complex scenarios involving two-way coupled interactions between compressible fluids and solid bodies under extreme conditions where monolithic, as opposed to partitioned, schemes are preferred for maintaining stability. When considering such problems, spurious numerical cavitation can be quite common and have deleterious consequences on the flow field stability, accuracy, etc. Thus, it is desirable to devise numerical methods that maintain the positivity of important physical quantities such as density, internal energy and pressure. We begin by showing that for an arbitrary flux function, one can put conditions on the time step in order to preserve positivity by solving a linear equation for density fluxes and a quadratic equation for energy fluxes. Our formulation is independent of the underlying equation of state. After deriving the method for forward Euler time integration, we further extend it to higher order accurate Runge–Kutta methods. Although the scheme works well in general, there are some cases where no lower bound on the size of the allowable time step exists. Thus, to prevent the size of the time step from becoming arbitrarily small, we introduce a conservative flux clamping scheme which is also positivity preserving. Exploiting the generality of our formulation, we then design a positivity preserving scheme for a semi-implicit approach to time integration that solves a symmetric positive definite linear system to determine the pressure associated with an equation of state. Finally, this modified semi-implicit approach is extended to monolithic two-way solid–fluid coupling problems for modeling fluid structure interactions such as those generated by blast waves impacting complex solid objects. [ABSTRACT FROM AUTHOR]

Abstract: We devise a novel method for treating bubbles in incompressible flow that relies on the conservative advection of bubble mass and an associated equation of state in order to determine pressure boundary conditions inside each bubble. We show that executing this algorithm in a traditional manner leads to stability issues similar to those seen for partitioned methods for solid–fluid coupling. Therefore, we reformulate the problem monolithically. This is accomplished by first proposing a new fully monolithic approach to coupling incompressible flow to fully nonlinear compressible flow including the effects of shocks and rarefactions, and then subsequently making a number of simplifying assumptions on the air flow removing not only the nonlinearities but also the spatial variations of both the density and the pressure. The resulting algorithm is quite robust, has been shown to converge to known solutions for test problems, and has been shown to be quite effective on more realistic problems including those with multiple bubbles, merging and pinching, etc. Notably, this approach departs from a standard two-phase incompressible flow model where the air flow preserves its volume despite potentially large forces and pressure differentials in the surrounding incompressible fluid that should change its volume. Our bubbles readily change volume according to an isothermal equation of state. [Copyright &y& Elsevier]

Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs. Building on the notions of correspondence and Gromov-Hausdorff distance in metric geometry, we describe a model for such data sets as an approximation of an underlying metric graph. We present a novel algorithm that takes as an input such a data set, and outputs a metric graph that is homeomorphic to the underlying metric graph and has bounded distortion of distances. We also implement the algorithm, and evaluate its performance on a variety of real world data sets. [ABSTRACT FROM AUTHOR]

Abstract: We consider tromino tilings of domino-deficient rectangles, where and , and characterize all cases of domino removal that admit such tilings, thereby settling the open problem posed by Ash and Golomb in [J. Marshall Ash, S. Golomb, Tiling Deficient Rectangles with Trominoes, Integre Technical Publishing Co., Mathematics Magazine (2003), 46–55]. We suggest a procedure for tiling domino-deficient rectangles based on this characterization. We also consider general 2-deficiency in rectangles, where , and characterize all pairs of missing squares which do not permit a tromino tiling. [Copyright &y& Elsevier]

Abstract: In this paper we study the diffuse reflection diameter and diffuse reflection radius problems for convex-quadrilateralizable polygons. In the usual model of diffuse reflection, a light ray incident at a point on the reflecting surface is reflected from that point in all possible inward directions. A ray reflected from a polygonal edge may graze that reflecting edge but an incident ray cannot graze the reflecting edge. The diffuse reflection diameter of a simple polygon is the minimum number of diffuse reflections that may be needed in the worst case to illuminate any target point from any point light source inside . We show that the diameter is upper bounded by in our usual model of diffuse reflection for convex-quadrilateralizable polygons. To the best of our knowledge, this is the first upper bound on diffuse reflection diameter within a fraction of for such a class of polygons. We also show that the diffuse reflection radius of a convex-quadrilateralizable simple polygon with vertices is at most under the usual model of diffuse reflection. In other words, there exists a point inside such a polygon from which usual diffuse reflections are always sufficient to illuminate the entire polygon. In order to establish these bounds for the usual model, we first show that the diameter and radius are and respectively, for the same class of polygons for a relaxed model of diffuse reflections; in the relaxed model an incident ray is permitted to graze a reflecting edge before turning and reflecting off the same edge at any interior point on that edge. We also show that the worst-case diameter and radius lower bounds of and respectively, are sometimes attained in the usual model, as well as in the relaxed model of diffuse reflection. [Copyright &y& Elsevier]

Energy conserving and dissipative algorithm designs in Hamilton's canonical equations via Petrov–Galerkin time finite element methodology are proposed in this paper that provide new avenues with high-order convergence rate, improved solution accuracy, and controllable numerical dissipation. Lagrange quadratic shape function in time with flexible interpolation points are considered to approximate the solution over a time interval. Instead of specifying the weight functions, two algorithmic parameters, namely, a principal root (ρ q ∞) and a spurious root (ρ p ∞), are introduced to formulate a generalized weight function, which enables us to introduce controllable numerical dissipation with respect to displacement and momenta while preserving high-order convergence, and features with improved solution accuracy. A family of third-order accurate time finite element algorithms with controllable dissipation and improved solution accuracy is presented in both the homogeneous and non-homogeneous dynamic problems; and via setting (ρ q ∞ , ρ p ∞) = (1 , 1) , this third-order family of algorithms directly leads to a new family of fourth-order accurate non-dissipative algorithms in general homogeneous problems; and the fourth-order accuracy is also preserved in non-homogeneous problems when the third-order time derivative of the external excitation has the order of O (Δ t n) (n ≤ 1). Numerical examples are performed to demonstrate the pros/cons for the conserving properties of various schemes in the proposed Petrov–Galerkin time finite element of algorithms. • A generalized PG in time approach for designing high-order algorithms is developed. • It provides controllable numerical dissipation and unconditionally stable feature. • Quadratic basis function leads to unconditionally stable 3rd/4th order algorithms. • Implicit Radau IIA3 and Lobatto IIIA are recovered with better solution accuracy. • One can apply high-order basis functions to generate high-order algorithms. [ABSTRACT FROM AUTHOR]