skip to main content

We present the augmented matrix for principal submatrix update (AMPS) algorithm, a finite element solution method that combines principal submatrix updates and Schur complement techniques, well-suited for interactive simulations of deformation and cutting of finite element meshes. Our approach features real-time solutions to the updated stiffness matrix systems to account for interactive changes in mesh connectivity and boundary conditions. Updates are accomplished by an augmented matrix formulation of the stiffness equations to maintain its consistency with changes to the underlying model without refactorization at each timestep. As changes accumulate over multiple simulation timesteps, the augmented solution algorithm enables tens or hundreds of updates per second. Acceleration schemes that exploit sparsity, memoization and parallelization lead to the updates being computed in real-time. The complexity analysis and experimental results for this method demonstrate that it scales linearly with the number of nonzeros of the factors of the stiffness matrix. Results for cutting and deformation of 3D elastic models are reported for meshes with up to 50,000 nodes, and involve models of surgery for astigmatism and the brain.  more » « less
Award ID(s):
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Numerical linear algebra with applications
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    A fundamental requirement in standard finite element method (FEM) over four‐node quadrilateral meshes is that every element must be convex, else the results can be erroneous. A mesh containing concave element is said to betangled, and tangling can occur, for example, during: mesh generation, mesh morphing, shape optimization, and/or large deformation simulation. The objective of this article is to introduce a tangled finite element method (TFEM) for handling concave elements in four‐node quadrilateral meshes. TFEM extends standard FEM through two concepts. First, the ambiguity of the field in the tangled region is resolved through a careful definition, and this naturally leads to certain correction terms in the FEM stiffness matrix. Second, an equality condition is imposed on the field at re‐entrant nodes of the concave elements. When the correction terms and equality conditions are included, we demonstrate that one can achieve accurate results, and optimal convergence, even over severely tangled meshes. The theoretical properties of the proposed TFEM are established, and the implementation, that requires minimal changes to standard FEM, is discussed in detail. Several numerical experiments are carried out to illustrate the robustness of the proposed method.

    more » « less
  2. Abstract

    As the use of spectral/hpelement methods, and high-order finite element methods in general, continues to spread, community efforts to create efficient, optimized algorithms associated with fundamental high-order operations have grown. Core tasks such as solution expansion evaluation at quadrature points, stiffness and mass matrix generation, and matrix assembly have received tremendous attention. With the expansion of the types of problems to which high-order methods are applied, and correspondingly the growth in types of numerical tasks accomplished through high-order methods, the number and types of these core operations broaden. This work focuses on solution expansion evaluation at arbitrary points within an element. This operation is core to many postprocessing applications such as evaluation of streamlines and pathlines, as well as to field projection techniques such as mortaring. We expand barycentric interpolation techniques developed on an interval to 2D (triangles and quadrilaterals) and 3D (tetrahedra, prisms, pyramids, and hexahedra) spectral/hpelement methods. We provide efficient algorithms for their implementations, and demonstrate their effectiveness using the spectral/hpelement libraryNektar++by running a series of baseline evaluations against the ‘standard’ Lagrangian method, where an interpolation matrix is generated and matrix-multiplication applied to evaluate a point at a given location. We present results from a rigorous series of benchmarking tests for a variety of element shapes, polynomial orders and dimensions. We show that when the point of interest is to be repeatedly evaluated, the barycentric method performs at worst$$50\%$$50%slower, when compared to a cached matrix evaluation. However, when the point of interest changes repeatedly so that the interpolation matrix must be regenerated in the ‘standard’ approach, the barycentric method yields far greater performance, with a minimum speedup factor of$$7\times $$7×. Furthermore, when derivatives of the solution evaluation are also required, the barycentric method in general slightly outperforms the cached interpolation matrix method across all elements and orders, with an up to$$30\%$$30%speedup. Finally we investigate a real-world example of scalar transport using a non-conformal discontinuous Galerkin simulation, in which we observe around$$6\times $$6×speedup in computational time for the barycentric method compared to the matrix-based approach. We also explore the complexity of both interpolation methods and show that the barycentric interpolation method requires$${\mathcal {O}}(k)$$O(k)storage compared to a best case space complexity of$${\mathcal {O}}(k^2)$$O(k2)for the Lagrangian interpolation matrix method.

    more » « less
  3. We present a fully-coupled, implicit-in-time framework for solving a thermodynamically-consistent Cahn-Hilliard Navier-Stokes system that models two-phase flows. In this work, we extend the block iterative method presented in Khanwale et al. [Simulating two-phase flows with thermodynamically consistent energy stable Cahn-Hilliard Navier-Stokes equations on parallel adaptive octree based meshes, J. Comput. Phys. (2020)], to a fully-coupled, provably second-order accurate scheme in time, while maintaining energy-stability. The new method requires fewer matrix assemblies in each Newton iteration resulting in faster solution time. The method is based on a fully-implicit Crank-Nicolson scheme in time and a pressure stabilization for an equal order Galerkin formulation. That is, we use a conforming continuous Galerkin (cG) finite element method in space equipped with a residual-based variational multiscale (RBVMS) procedure to stabilize the pressure. We deploy this approach on a massively parallel numerical implementation using parallel octree-based adaptive meshes. We present comprehensive numerical experiments showing detailed comparisons with results from the literature for canonical cases, including the single bubble rise, Rayleigh-Taylor instability, and lid-driven cavity flow problems. We analyze in detail the scaling of our numerical implementation. 
    more » « less
  4. Immersed finite element methods are designed to solve interface problems on interface- unfitted meshes. However, most of the study, especially analysis, is mainly limited to the two-dimension case. In this paper, we provide an a priori analysis for the trilinear immersed finite element method to solve three-dimensional elliptic interface problems on Cartesian grids consisting of cuboids. We establish the trace and inverse inequalities for trilinear IFE functions for interface elements with arbitrary interface-cutting configuration. Optimal a priori error estimates are rigorously proved in both energy and L2 norms, with the constant in the error bound independent of the interface location and its dependence on coefficient contrast explicitly specified. Numerical examples are provided not only to verify our theoretical results but also to demonstrate the applicability of this IFE method in tackling some real-world 3D interface models. 
    more » « less
  5. Abstract

    We present a method for the efficient processing of contact and collision in volumetric elastic models simulated using the Projective Dynamics paradigm. Our approach enables interactive simulation of tetrahedral meshes with more than half a million elements, provided that the model satisfies two fundamental properties: the region of the model's surface that is susceptible to collision events needs to be known in advance, and the simulation degrees of freedom associated with that surface region should be limited to a small fraction (e.g. 5%) of the total simulation nodes. In such scenarios, a partial Cholesky factorization can abstract away the behaviour of the collision‐safe subset of the face model into the Schur Complement matrix with respect to the collision‐prone region. We demonstrate how fast and accurate updates of bilateral penalty‐based collision terms can be incorporated into this representation, and solved with high efficiency on the GPU. We also demonstrate iterating a partial update of the element rotations, akin to a selective application of the local step, specifically on the smaller collision‐prone region without explicitly paying the cost associated with the rest of the simulation mesh. We demonstrate efficient and robust interactive simulation in detailed models from animation and medical applications.

    more » « less