Premium
AMPS: Real‐time mesh cutting with augmented matrices for surgical simulations
Author(s) -
Yeung YuHong,
Pothen Alex,
Crouch Jessica
Publication year - 2020
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2323
Subject(s) - polygon mesh , finite element method , computer science , stiffness matrix , matrix (chemical analysis) , algorithm , computational science , boundary (topology) , acceleration , augmented lagrangian method , schur complement , mathematical optimization , mathematics , computer graphics (images) , mathematical analysis , structural engineering , eigenvalues and eigenvectors , materials science , physics , classical mechanics , quantum mechanics , engineering , composite material
Summary 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 three‐dimensional (3D) elastic models are reported for meshes with up to 50 000 nodes, and involve models of surgery for astigmatism and the brain.