skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: AMPS: REAL-TIME MESH CUTTING WITH AUGMENTED MATRICES FOR SURGICAL SIMULATIONS
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):
1637534
PAR ID:
10181562
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Numerical linear algebra with applications
ISSN:
1070-5325
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Journal of computational physics)
    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
  2. ; ; ; ; ; ; (, Computer physics communications)
    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
  3. ; ; (, IMA Journal of Numerical Analysis)
    Abstract In this paper we study the biharmonic equation with Navier boundary conditions in a polygonal domain. In particular, we propose a method that effectively decouples the fourth-order problem as a system of Poisson equations. Our method differs from the naive mixed method that leads to two Poisson problems but only applies to convex domains; our decomposition involves a third Poisson equation to confine the solution in the correct function space, and therefore can be used in both convex and nonconvex domains. A $C^0$ finite element algorithm is in turn proposed to solve the resulting system. In addition, we derive optimal error estimates for the numerical solution on both quasi-uniform meshes and graded meshes. Numerical test results are presented to justify the theoretical findings. 
    more » « less
  4. ; ; ; (, Advanced Modeling and Simulation in Engineering Sciences)
    Abstract The embedded finite element technique provides a unique approach for modeling of fiber-reinforced composites. Meshing fibers as distinct bundles represented by truss elements embedded in a matrix material mesh allows for the assignment of more specific material properties for each component rather than homogenization of all of the properties. However, the implementations of the embedded element technique available in commercial software do not replace the material of the matrix elements with the material of the embedded elements. This causes a redundancy in the volume calculation of the overlapping meshes leading to artificially increased stiffness and mass. This paper investigates the consequences in the energy calculations of an explicit dynamic model due to this redundancy. A method for the correction of the edundancy within a finite element code is suggested which removes extra energy and is shown to be effective at correcting the energy calculations for large amounts of redundant volume. 
    more » « less
  5. ; (, Operations Research)
    This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to develop a sampling algorithm and derive its approximation bound for MESP, which improves the best known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. Besides, we investigate the widely used local search algorithm and prove its first known approximation bound for MESP. The proof techniques further inspire for us an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-size and large-scale instances to near optimality. Finally, we extend the analyses to the A-optimal MESP, for which the objective is to minimize the trace of the inverse of the selected principal submatrix. Funding: This work was supported by the National Science Foundation Division of Information and Intelligent Systems [Grant 2246417] and Division of Civil, Mechanical and Manufacturing Innovation [Grant 2246414]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2488 . 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email