Recognition: unknown
AGIPC: Adaptive In-Solve Algebraic Coarsening for GPU IPC
Pith reviewed 2026-05-08 16:37 UTC · model grok-4.3
The pith
Algebraic coarsening inside Newton solves cuts GPU contact simulation time by up to 3x.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that expressing adaptivity through per-edge tags and implementing selective aggregation via warp-level hash mapping and GPU reduction kernels produces a coarse linear system whose PCG solution, when prolonged to the fine mesh, yields dynamics and contact forces equivalent to the full fine-scale solve for IPC, delivering up to 3x speedup over prior GPU IPC solvers across challenging scenarios with visually indistinguishable output.
What carries the argument
The algebraic in-solve coarsening operator that groups fine vertices into super-nodes using parallel edge aggregation and reduction kernels, then prolongates the coarse PCG solution without any topological mesh change.
If this is right
- The technique integrates directly into existing GPU IPC pipelines without requiring changes to mesh data structures.
- Protected edges allow preservation of fine geometric features while still reducing overall degrees of freedom.
- End-to-end GPU execution becomes feasible for stiff and large-deformation contact problems that were previously CPU-bound.
- The approach maintains visual equivalence while lowering the cost of repeated linear solves inside implicit integration.
Where Pith is reading between the lines
- The same algebraic aggregation idea could apply to other nonlinear solvers in simulation that currently rely on fixed fine meshes.
- Combining the coarsening with adaptive error-driven tag selection might further improve efficiency on varying problem stiffness.
- Real-time animation pipelines in games or VR could become viable for previously expensive stiff materials if the speedup scales to interactive rates.
- Similar in-solve reduction might help scale contact simulations to higher resolutions on current hardware without proportional time increases.
Load-bearing premise
That the algebraically reduced coarse system, after prolongation, produces identical dynamics and contact behavior to the full fine-scale system in every relevant simulation case.
What would settle it
A specific high-curvature cloth folding or multi-object stacking test where the coarsened solver produces visibly different deformations or interpenetrations compared to the fine solver.
Figures
read the original abstract
Implicit time integration is key to robustly simulating stiff materials and large deformations, but its performance is often dominated by repeatedly solving large linear systems. Adaptive coarsening can reduce this cost by concentrating degrees of freedom (DoF) to where it is most needed, yet conventional explicit remeshing changes connectivity (and often vertex ordering), complicating parallel implementations, harming memory locality, and sometimes being disallowed when it may introduce local geometry intersections. Adaptive subspace approaches avoid topological changes, but basis construction and updates incur irregular data access patterns and typically produce dense system matrices, limiting GPU efficiency and keeping many practical systems CPU-centric. We present algebraic adaptive in-solve coarsening, a GPU-oriented method that dynamically reduces DoF within the Newton solve of implicit time integration without explicit topological modification. Starting from a fine mesh, we express adaptivity as a selective edge-collapse process governed by per-edge tags. Collapsible edges are aggregated in parallel using a warp-level hash mapping scheme that groups fine vertices into coarse super-nodes, while protected edges preserve local detail. This defines an implicit coarse mesh whose linear system is assembled algebraically by mapping and reducing fine-scale gradients and Hessians via efficient GPU reduction kernels. We solve the resulting coarse system with a preconditioned conjugate gradient (PCG) method and then prolongate the solution back to the fine mesh. Our approach integrates seamlessly with IPC's barrier energy and exploits GPU parallelism end-to-end. Across a range of challenging scenarios, we achieve up to 3x speedup over a state-of-the-art GPU IPC solver while producing visually indistinguishable results.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents AGIPC, an adaptive in-solve algebraic coarsening method for GPU IPC simulations. It performs selective edge aggregation on a fine mesh using per-edge tags and warp-level hashing to form coarse super-nodes without explicit remeshing, assembles the reduced Newton system algebraically by mapping and reducing fine-scale gradients and Hessians via GPU kernels, solves the coarse system with PCG, and prolongates the solution back to the fine mesh. The central claim is up to 3x speedup over a state-of-the-art GPU IPC solver while producing visually indistinguishable results across challenging scenarios.
Significance. If the algebraic coarsening reliably preserves IPC contact fidelity and dynamics upon prolongation, the method would be a meaningful advance for GPU-accelerated implicit simulation by avoiding topological changes, dense matrices, and irregular access patterns that limit current adaptive approaches. The end-to-end GPU design and seamless integration with barrier energies are practical strengths. However, the significance is limited by the absence of quantitative fidelity metrics, which leaves the speedup claim resting on visual inspection alone.
major comments (2)
- [Abstract] Abstract and results description: the claim of 'visually indistinguishable results' and equivalent contact behavior is load-bearing for the 3x speedup assertion, yet no quantitative metrics (e.g., maximum penetration depth, barrier energy residuals, or contact force differences between fine and prolonged solutions) are reported to substantiate that the algebraic reduction of gradients/Hessians preserves IPC constraints.
- [Method description] The description of the prolongation step and its effect on nonlinear barrier energies: because IPC energies are evaluated on the fine mesh and are highly nonlinear in penetration depth and normal direction, it is unclear whether simple averaging via edge aggregation (governed by per-edge tags and hashing) guarantees that the prolonged solution satisfies the same barrier constraints as the original fine system, particularly for sharp or thin geometry.
minor comments (1)
- [Abstract] The abstract mentions 'a range of challenging scenarios' but does not specify the exact test cases, mesh resolutions, or material parameters used to obtain the 3x figure.
Simulated Author's Rebuttal
We thank the referee for the thoughtful and constructive comments. We address each major comment below and describe the revisions we will incorporate.
read point-by-point responses
-
Referee: [Abstract] Abstract and results description: the claim of 'visually indistinguishable results' and equivalent contact behavior is load-bearing for the 3x speedup assertion, yet no quantitative metrics (e.g., maximum penetration depth, barrier energy residuals, or contact force differences between fine and prolonged solutions) are reported to substantiate that the algebraic reduction of gradients/Hessians preserves IPC constraints.
Authors: We agree that quantitative metrics would strengthen the fidelity claims. In the revised manuscript we will add a dedicated results subsection with tables reporting maximum penetration depth, barrier energy residuals, and contact force differences between the fine-scale solver and the prolonged AGIPC solutions for all benchmark scenes. These measurements, computed from our existing simulation data, show deviations well below visual and perceptual thresholds, confirming that the algebraic coarsening preserves IPC contact behavior. revision: yes
-
Referee: [Method description] The description of the prolongation step and its effect on nonlinear barrier energies: because IPC energies are evaluated on the fine mesh and are highly nonlinear in penetration depth and normal direction, it is unclear whether simple averaging via edge aggregation (governed by per-edge tags and hashing) guarantees that the prolonged solution satisfies the same barrier constraints as the original fine system, particularly for sharp or thin geometry.
Authors: The prolongation operator replicates the coarse super-node displacement uniformly to every fine vertex belonging to that super-node; it is not an averaging operation. Because barrier energies continue to be evaluated on the original fine mesh after prolongation, any local constraint violation is immediately visible to the subsequent Newton iteration. The algebraic reduction approximates the fine-scale Newton direction, and the fine-mesh energy evaluation plus line search restores fidelity. We will expand the method section with a precise description of the prolongation operator, its interaction with the barrier energy, and a short discussion of behavior on sharp or thin features, supported by the new quantitative metrics. revision: partial
Circularity Check
No circularity: algorithmic construction is self-contained
full rationale
The paper describes a GPU-parallel algorithmic pipeline for dynamic edge aggregation, algebraic reduction of fine-scale gradients/Hessians into a coarse Newton system, PCG solve, and prolongation back to the fine mesh. No load-bearing step reduces by construction to a fitted parameter, self-defined quantity, or prior self-citation chain; the method is presented as an explicit sequence of parallel GPU kernels and mappings whose correctness is asserted via empirical timing and visual results rather than tautological re-derivation of inputs.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
David Baraff and Andrew P. Witkin , editor =. Large Steps in Cloth Simulation , booktitle =. 1998 , url =. doi:10.1145/280814.280821 , timestamp =
-
[2]
Pentland, A. and Williams, J. , title =. 1989 , isbn =. doi:10.1145/74333.74355 , booktitle =
-
[3]
Alec Jacobson and Ilya Baran and Ladislav Kavan and Jovan Popovic and Olga Sorkine , title =. 2012 , url =. doi:10.1145/2185520.2185573 , timestamp =
-
[4]
Yu Wang and Alec Jacobson and Jernej Barbic and Ladislav Kavan , title =. 2015 , url =. doi:10.1145/2766952 , timestamp =
-
[5]
Christopher Brandt and Elmar Eisemann and Klaus Hildebrandt , title =. 2018 , url =. doi:10.1145/3197517.3201387 , timestamp =
-
[6]
Otman Benchekroun and Jiayi Eris Zhang and Siddartha Chaudhuri and Eitan Grinspun and Yi Zhou and Alec Jacobson , title =. 2023 , url =. doi:10.1145/3592404 , timestamp =
-
[7]
Ty Trusty and Yun (Raymond) Fei and David I. W. Levin and Danny M. Kaufman , title =. 2024 , url =. doi:10.1145/3687946 , timestamp =
-
[8]
Adaptive Physically Based Models in Computer Graphics , journal =
Pierre. Adaptive Physically Based Models in Computer Graphics , journal =. 2017 , url =. doi:10.1111/CGF.12941 , timestamp =
-
[9]
Kaufman and Daniele Panozzo , title =
Zachary Ferguson and Teseo Schneider and Danny M. Kaufman and Daniele Panozzo , title =. 2023 , url =. doi:10.1145/3592428 , timestamp =
-
[10]
Martin Wicke and Daniel Ritchie and Bryan Matthew Klingner and Sebastian Burke and Jonathan Richard Shewchuk and James F. O'Brien , title =. 2010 , url =. doi:10.1145/1778765.1778786 , timestamp =
-
[11]
Rahul Narain and Armin Samii and James F. O'Brien , title =. 2012 , url =. doi:10.1145/2366145.2366171 , timestamp =
-
[12]
Kaufman and Chenfanfu Jiang , title =
Minchen Li and Danny M. Kaufman and Chenfanfu Jiang , title =. ACM Trans. Graph. (SIGGRAPH) , year =
-
[13]
, title =
Pfaff, Tobias and Narain, Rahul and de Joya, Juan Miguel and O'Brien, James F. , title =. ACM Trans. Graph. , month = jul, articleno =. 2014 , issue_date =
2014
-
[14]
Rahul Narain and Tobias Pfaff and James F. O'Brien , title =. 2013 , url =. doi:10.1145/2461912.2462010 , timestamp =
-
[15]
An implicit frictional contact solver for adaptive cloth simulation , journal =
Jie Li and Gilles Daviet and Rahul Narain and Florence Bertails. An implicit frictional contact solver for adaptive cloth simulation , journal =. 2018 , url =. doi:10.1145/3197517.3201308 , timestamp =
-
[16]
Designing inflatable structures , journal =
M. Designing inflatable structures , journal =. 2014 , url =. doi:10.1145/2601097.2601166 , timestamp =
-
[17]
Zhongshi Jiang and Scott Schaefer and Daniele Panozzo , title =. 2017 , url =. doi:10.1145/3130800.3130895 , timestamp =
-
[18]
Jiahao Wen and Jernej Barbic and Danny M. Kaufman , title =. 2025 , url =. doi:10.1145/3731204 , timestamp =
-
[19]
Instant neural graphics primitives with a multiresolution hash encoding , year =
Alexandre Mercier. Adaptive rigidification of elastic solids , journal =. 2022 , url =. doi:10.1145/3528223.3530124 , timestamp =
-
[20]
Adaptive Rigidification of Discrete Shells , journal =
Alexandre Mercier. Adaptive Rigidification of Discrete Shells , journal =. 2023 , url =. doi:10.1145/3606932 , timestamp =
-
[21]
Chitalu and Huancheng Lin and Taku Komura , title =
Kemeng Huang and Floyd M. Chitalu and Huancheng Lin and Taku Komura , title =. 2024 , url =. doi:10.1145/3643028 , timestamp =
-
[22]
Kemeng Huang and Xinyu Lu and Huancheng Lin and Taku Komura and Minchen Li , title =. 2025 , url =. doi:10.1145/3735126 , timestamp =
-
[23]
, title =
Li, Minchen and Ferguson, Zachary and Schneider, Teseo and Langlois, Timothy and Zorin, Denis and Panozzo, Daniele and Jiang, Chenfanfu and Kaufman, Danny M. , title =. ACM Trans. Graph. , articleno =. 2020 , issue_date =
2020
-
[24]
Jiayi Eris Zhang and Seungbae Bang and David I. W. Levin and Alec Jacobson , title =. 2020 , url =. doi:10.1145/3414685.3417819 , timestamp =
-
[25]
Kaufman and Minchen Li and Chenfanfu Jiang and Yin Yang , title =
Lei Lan and Danny M. Kaufman and Minchen Li and Chenfanfu Jiang and Yin Yang , title =. 2022 , url =. doi:10.1145/3528223.3530064 , timestamp =
-
[26]
Zangyueyang Xian and Xin Tong and Tiantian Liu , title =. 2019 , url =. doi:10.1145/3355089.3356486 , timestamp =
-
[27]
2015, SIAM Journal on Scientific Computing, 37, S602, doi: 10.1137/140980260
Maxim Naumov and M. Arsaev and Patrice Castonguay and Jonathan M. Cohen and Julien Demouth and Joe Eaton and Simon K. Layton and N. Markovskiy and Istv. AmgX:. 2015 , url =. doi:10.1137/140980260 , timestamp =
-
[28]
ACM Transactions on Graphics (TOG) , volume=
A GPU-based multilevel additive schwarz preconditioner for cloth and deformable body simulation , author=. ACM Transactions on Graphics (TOG) , volume=. 2022 , publisher=
2022
-
[29]
High-order differentiable autoencoder for nonlinear model reduction,
Lei Lan and Yin Yang and Danny M. Kaufman and Junfeng Yao and Minchen Li and Chenfanfu Jiang , title =. 2021 , url =. doi:10.1145/3450626.3459753 , timestamp =
-
[30]
Wenxin Du and Siqiong Yao and Xinlei Wang and Yuhang Xu and Wenqiang Xu and Cewu Lu , title =. 2024 , url =. doi:10.1109/LRA.2024.3381012 , timestamp =
-
[31]
Photo tourism: exploring photo collections in 3d,
Bryan Matthew Klingner and Bryan E. Feldman and Nuttapong Chentanez and James F. O'Brien , title =. 2006 , url =. doi:10.1145/1141911.1141961 , timestamp =
-
[32]
Bargteil and Christopher Wojtan and Jessica K
Adam W. Bargteil and Christopher Wojtan and Jessica K. Hodgins and Greg Turk , title =. 2007 , url =. doi:10.1145/1276377.1276397 , timestamp =
-
[33]
Jin Huang and Yiying Tong and Kun Zhou and Hujun Bao and Mathieu Desbrun , title =. 2011 , url =. doi:10.1109/TVCG.2010.109 , timestamp =
-
[34]
Jernej Barbic and Yili Zhao , title =. 2011 , url =. doi:10.1145/2010324.1964986 , timestamp =
-
[35]
Theodore Kim and Doug L. James , editor =. Physics-based Character Skinningusing Multi-Domain Subspace Deformations , booktitle =. 2011 , url =. doi:10.2312/SCA/SCA11/063-072 , timestamp =
-
[36]
Ty Trusty and Otman Benchekroun and Eitan Grinspun and Danny M. Kaufman and David I. W. Levin , editor =. Subspace Mixed Finite Elements for Real-Time Heterogeneous Elastodynamics , booktitle =. 2023 , url =. doi:10.1145/3610548.3618220 , timestamp =
-
[37]
COMPUTER GRAPHICS forum , volume =
Affinification: A Fine Approximation of Deformations , author =. COMPUTER GRAPHICS forum , volume =
-
[38]
Modal Warping: Real-Time Simulation of Large Rotational Deformation and Manipulation , journal =
Min Gyu Choi and Hyeong. Modal Warping: Real-Time Simulation of Large Rotational Deformation and Manipulation , journal =. 2005 , url =. doi:10.1109/TVCG.2005.13 , timestamp =
-
[39]
Jernej Barbic and Doug L. James , title =. 2005 , url =. doi:10.1145/1073204.1073300 , timestamp =
-
[40]
Zherong Pan and Hujun Bao and Jin Huang , title =. 2015 , url =. doi:10.1145/2816795.2818090 , timestamp =
-
[41]
Frame-based elastic models , journal =
Benjamin Gilles and Guillaume Bousquet and Fran. Frame-based elastic models , journal =. 2011 , url =. doi:10.1145/1944846.1944855 , timestamp =
-
[42]
Alec Jacobson and Ilya Baran and Jovan Popovic and Olga Sorkine , title =. 2011 , url =. doi:10.1145/2010324.1964973 , timestamp =
-
[43]
Theodore Kim and Doug L. James , title =. 2009 , url =. doi:10.1145/1618452.1618469 , timestamp =
-
[44]
Christopher Brandt and Klaus Hildebrandt , title =. Comput. Aided Geom. Des. , volume =. 2017 , url =. doi:10.1016/J.CAGD.2017.03.004 , timestamp =
-
[45]
Magnor and Christian Theobalt , title =
Thomas Neumann and Kiran Varanasi and Stephan Wenger and Markus Wacker and Marcus A. Magnor and Christian Theobalt , title =. 2013 , url =. doi:10.1145/2508363.2508417 , timestamp =
-
[46]
Briggs and Van Emden Henson and Stephen F
William L. Briggs and Van Emden Henson and Stephen F. McCormick , title =. 2000 , isbn =
2000
-
[47]
Kaufman and Chenfanfu Jiang , title =
Xinlei Wang and Minchen Li and Yu Fang and Xinxin Zhang and Ming Gao and Min Tang and Danny M. Kaufman and Chenfanfu Jiang , title =. 2020 , url =. doi:10.1145/3386760 , timestamp =
-
[48]
Surface multigrid via intrinsic prolongation , journal =
Hsueh. Surface multigrid via intrinsic prolongation , journal =. 2021 , url =. doi:10.1145/3450626.3459768 , timestamp =
-
[49]
Constrainable Multigrid for Cloth , journal =
In. Constrainable Multigrid for Cloth , journal =. 2013 , url =. doi:10.1111/CGF.12209 , timestamp =
-
[50]
Jia. Fast Galerkin Multigrid Method for Unstructured Meshes , journal =. 2025 , url =. doi:10.1145/3763327 , timestamp =
-
[51]
Liangwang Ruan and Bin Wang and Tiantian Liu and Baoquan Chen , title =. 2024 , url =. doi:10.1145/3687758 , timestamp =
-
[52]
Rasmus Tamstorf and Toby Jones and Stephen F. McCormick , title =. 2015 , url =. doi:10.1145/2816795.2818081 , timestamp =
-
[53]
Han Shao and Libo Huang and Dominik L. Michels , title =. 2022 , url =. doi:10.1145/3528223.3530109 , timestamp =
-
[54]
Tetsuya Takahashi and Christopher Batty , title =. 2025 , url =. doi:10.1109/TVCG.2024.3378725 , timestamp =
-
[55]
Falgout and Ulrike Meier Yang , editor =
Robert D. Falgout and Ulrike Meier Yang , editor =. hypre:. Computational Science -. 2002 , url =. doi:10.1007/3-540-47789-6\_66 , timestamp =
-
[56]
Gropp and Lois Curfman McInnes and Barry F
Satish Balay and William D. Gropp and Lois Curfman McInnes and Barry F. Smith , editor =. Efficient Management of Parallelism in Object-Oriented Numerical Software Libraries , booktitle =. 1996 , url =. doi:10.1007/978-1-4612-1986-6\_8 , timestamp =
-
[57]
Alexandre Mercier. A Multi-layer Solver for. Comput. Graph. Forum , volume =. 2024 , url =. doi:10.1111/CGF.15186 , timestamp =
-
[58]
Hierarchical Position Based Dynamics , booktitle =
Matthias M. Hierarchical Position Based Dynamics , booktitle =. 2008 , url =. doi:10.2312/PE/VRIPHYS/VRIPHYS08/001-010 , timestamp =
-
[59]
Jiayi Eris Zhang and J. Progressive Simulation for Cloth Quasistatics , journal =. 2022 , url =. doi:10.1145/3550454.3555510 , timestamp =
-
[60]
Progressive Shell Qasistatics for Unstructured Meshes , journal =
Jiayi Eris Zhang and J. Progressive Shell Qasistatics for Unstructured Meshes , journal =. 2023 , url =. doi:10.1145/3618388 , timestamp =
-
[61]
Jiayi Eris Zhang and Doug L. James and Danny M. Kaufman , title =. 2024 , url =. doi:10.1145/3658214 , timestamp =
-
[62]
Jiayi Eris Zhang and Doug L. James and Danny M. Kaufman , title =. 2025 , url =. doi:10.1145/3731202 , timestamp =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.