{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:05:47Z","timestamp":1784268347144,"version":"3.55.0"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2153851 2301040"],"award-info":[{"award-number":["2153851 2301040"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,8,1]]},"abstract":"<jats:p>\n                    In parallel simulation, convergence and parallelism are often seen as inherently conflicting objectives. Improved parallelism typically entails lighter local computation and weaker coupling, which unavoidably slow the global convergence. This paper presents a novel GPU algorithm that achieves convergence rates comparable to fullspace Newton's method while maintaining good parallelizability just like the Jacobi method. Our approach is built on a key insight into the phenomenon of\n                    <jats:italic toggle=\"yes\">overshoot.<\/jats:italic>\n                    Overshoot occurs when a local solver aggressively minimizes its local energy without accounting for the global context, resulting in a local update that undermines global convergence. To address this, we derive a theoretically second-order optimal solution to mitigate overshoot. Furthermore, we adapt this solution into a pre-computable form. Leveraging Cubature sampling, our runtime cost is only marginally higher than the Jacobi method, yet our algorithm converges nearly quadratically as Newton's method. We also introduce a novel full-coordinate formulation for more efficient pre-computation. Our method integrates seamlessly with the incremental potential contact method and achieves second-order convergence for both stiff and soft materials. Experimental results demonstrate that our approach delivers high-quality simulations and outperforms state-of-the-art GPU methods with 50\u00d7 to 100\u00d7 better convergence.\n                  <\/jats:p>","DOI":"10.1145\/3731183","type":"journal-article","created":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T04:02:22Z","timestamp":1753588942000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["JGS2: Near Second-order Converging Jacobi\/Gauss-Seidel for GPU Elastodynamics"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-7626-7580","authenticated-orcid":false,"given":"Lei","family":"Lan","sequence":"first","affiliation":[{"name":"University of Utah, Salt Lake City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5031-5074","authenticated-orcid":false,"given":"Zixuan","family":"Lu","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1134-0442","authenticated-orcid":false,"given":"Chun","family":"Yuan","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3756-3539","authenticated-orcid":false,"given":"Weiwei","family":"Xu","sequence":"additional","affiliation":[{"name":"State Key Lab of CAD&amp;CG, Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1796-2682","authenticated-orcid":false,"given":"Hao","family":"Su","sequence":"additional","affiliation":[{"name":"UCSD, La Jolla, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8153-2337","authenticated-orcid":false,"given":"Huamin","family":"Wang","sequence":"additional","affiliation":[{"name":"Style3D Research, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3506-0583","authenticated-orcid":false,"given":"Chenfanfu","family":"Jiang","sequence":"additional","affiliation":[{"name":"UCLA, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7645-5931","authenticated-orcid":false,"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, Utah, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,7,27]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Optimizing cubature for efficient integration of subspace deformations. ACM transactions on graphics (TOG) 27, 5","author":"An Steven S","year":"2008","unstructured":"Steven S An, Theodore Kim, and Doug L James. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM transactions on graphics (TOG) 27, 5 (2008), 1\u201310."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280821"},{"key":"e_1_2_2_3_1","volume-title":"Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM transactions on graphics (TOG) 24, 3","author":"Barbi\u010d Jernej","year":"2005","unstructured":"Jernej Barbi\u010d and Doug L James. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM transactions on graphics (TOG) 24, 3 (2005), 982\u2013990."},{"key":"e_1_2_2_4_1","volume-title":"Real-time large-deformation substructuring. ACM transactions on graphics (TOG) 30, 4","author":"Barbi\u010d Jernej","year":"2011","unstructured":"Jernej Barbi\u010d and Yili Zhao. 2011. Real-time large-deformation substructuring. ACM transactions on graphics (TOG) 30, 4 (2011), 1\u20138."},{"key":"e_1_2_2_5_1","volume-title":"Ian Farmer, Eitan Grinspun, and Peter Schr\u00f6der.","author":"Bathe Klaus-J\u00fcrgen","year":"2003","unstructured":"Klaus-J\u00fcrgen Bathe. 2006. Finite element procedures. Klaus-Jurgen Bathe. Jeff Bolz, Ian Farmer, Eitan Grinspun, and Peter Schr\u00f6der. 2003. Sparse matrix solvers on the GPU: conjugate gradients and multigrid. ACM transactions on graphics (TOG) 22, 3 (2003), 917\u2013924."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00886.x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566622"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545268"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383266"},{"key":"e_1_2_2_11_1","volume-title":"A simple geometric model for elastic deformations. ACM transactions on graphics (TOG) 29, 4","author":"Chao Isaac","year":"2010","unstructured":"Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schr\u00f6der. 2010. A simple geometric model for elastic deformations. ACM transactions on graphics (TOG) 29, 4 (2010), 1\u20136."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658179"},{"key":"e_1_2_2_13_1","volume-title":"Trust-Region Eigenvalue Filtering for Projected Newton. In SIGGRAPH Asia 2024 Conference Papers. 1\u201310","author":"Chen Honglin","year":"2024","unstructured":"Honglin Chen, Hsueh-Ti Derek Liu, Alec Jacobson, David IW Levin, and Changxi Zheng. 2024b. Trust-Region Eigenvalue Filtering for Projected Newton. In SIGGRAPH Asia 2024 Conference Papers. 1\u201310."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658154"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.13"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964968"},{"key":"e_1_2_2_17_1","volume-title":"Principles towards real-time simulation of material point method on modern GPUs. arXiv preprint arXiv:2111.00699","author":"Fei Yun","year":"2021","unstructured":"Yun Fei, Yuhan Huang, and Ming Gao. 2021. Principles towards real-time simulation of material point method on modern GPUs. arXiv preprint arXiv:2111.00699 (2021)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982437"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Marco Fratarcangeli Huamin Wang and Yin Yang. 2018. Parallel iterative solvers for real-time elastic deformations. In SIGGRAPH Asia 2018 Courses. 1\u201345.","DOI":"10.1145\/3277644.3277779"},{"key":"e_1_2_2_20_1","volume-title":"David IW Levin, and Alec Jacobson","author":"Fulton Lawson","year":"2019","unstructured":"Lawson Fulton, Vismay Modi, David Duvenaud, David IW Levin, and Alec Jacobson. 2019. Latent-space Dynamics for Reduced Deformable Simulation. In Computer graphics forum, Vol. 38. Wiley Online Library, 379\u2013391."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944846.1944855"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Anne Greenbaum. 1997. Iterative methods for solving linear systems. SIAM.","DOI":"10.1137\/1.9781611970937"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566578"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3687988"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461922"},{"key":"e_1_2_2_26_1","first-page":"16","article-title":"Interactive Deformation Using Modal Analysis with Constraints","volume":"3","author":"Hauser Kris K","year":"2003","unstructured":"Kris K Hauser, Chen Shen, and James F O'Brien. 2003. Interactive Deformation Using Modal Analysis with Constraints.. In Graphics Interface, Vol. 3. 16\u201317.","journal-title":"Graphics Interface"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2231816.2231821"},{"key":"e_1_2_2_28_1","volume-title":"The finite element method: linear static and dynamic finite element analysis","author":"Hughes Thomas JR","unstructured":"Thomas JR Hughes. 2012. The finite element method: linear static and dynamic finite element analysis. Courier Corporation."},{"key":"e_1_2_2_29_1","volume-title":"As-rigid-as-possible shape manipulation. ACM transactions on Graphics (TOG) 24, 3","author":"Igarashi Takeo","year":"2005","unstructured":"Takeo Igarashi, Tomer Moscovich, and John F Hughes. 2005. As-rigid-as-possible shape manipulation. ACM transactions on Graphics (TOG) 24, 3 (2005), 1134\u20131141."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964973"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1618452.1618469"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019406.2019415"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14508"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592104"},{"key":"e_1_2_2_35_1","volume-title":"Efficient GPU Cloth Simulation with Non-distance Barriers and Subspace Reuse. ACM Transactions on Graphics (TOG)43, 6","author":"Lan Lei","year":"2024","unstructured":"Lei Lan, Zixuan Lu, Jingyi Long, Chun Yuan, Xuan Li, Xiaowei He, Huamin Wang, Chenfanfu Jiang, and Yin Yang. 2024. Efficient GPU Cloth Simulation with Non-distance Barriers and Subspace Reuse. ACM Transactions on Graphics (TOG)43, 6 (2024), 1\u201316."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3384515"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530069"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459753"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322951"},{"key":"e_1_2_2_41_1","volume-title":"Codimensional incremental potential contact. arXiv preprint arXiv:2012.04457","author":"Li Minchen","year":"2020","unstructured":"Minchen Li, Danny M Kaufman, and Chenfanfu Jiang. 2020b. Codimensional incremental potential contact. arXiv preprint arXiv:2012.04457 (2020)."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3610548.3618157"},{"key":"e_1_2_2_43_1","volume-title":"Green coordinates. ACM transactions on graphics (TOG) 27, 3","author":"Lipman Yaron","year":"2008","unstructured":"Yaron Lipman, David Levin, and Daniel Cohen-Or. 2008. Green coordinates. ACM transactions on graphics (TOG) 27, 3 (2008), 1\u201310."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805964.1805971"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661270"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.2990496"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356493"},{"key":"e_1_2_2_48_1","volume-title":"Physics-based quadratic deformation using elastic weighting","author":"Luo Ran","year":"2017","unstructured":"Ran Luo, Weiwei Xu, Huamin Wang, Kun Zhou, and Yin Yang. 2017. Physics-based quadratic deformation using elastic weighting. IEEE transactions on visualization and computer graphics 24, 12 (2017), 3188\u20133199."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461984"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3487983.3488289"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994258.2994272"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7949(71)90031-9"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778776"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588432.3591499"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545269"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2007.01.005"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073216"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14105"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/b98874"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818090"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355621"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/74333.74355"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459754"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786784.2786787"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180491"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818081"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766904"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508392"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386760"},{"key":"e_1_2_2_72_1","series-title":"SIAM review 11, 2","volume-title":"Convergence conditions for ascent methods","author":"Wolfe Philip","year":"1969","unstructured":"Philip Wolfe. 1969. Convergence conditions for ascent methods. SIAM review 11, 2 (1969), 226\u2013235."},{"key":"e_1_2_2_73_1","volume-title":"Coordinate descent algorithms. Mathematical programming 151, 1","author":"Wright Stephen J","year":"2015","unstructured":"Stephen J Wright. 2015. Coordinate descent algorithms. Mathematical programming 151, 1 (2015), 3\u201334."},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530085"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417865"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818065"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356486"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818089"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.12"},{"key":"e_1_2_2_80_1","volume-title":"XPBI: Position-Based Dynamics with Smoothing Kernels Handles Continuum Inelasticity. In SIGGRAPH Asia 2024 Conference Papers. 1\u201312","author":"Yu Chang","year":"2024","unstructured":"Chang Yu, Xuan Li, Lei Lan, Yin Yang, and Chenfanfu Jiang. 2024. XPBI: Position-Based Dynamics with Smoothing Kernels Handles Continuum Inelasticity. In SIGGRAPH Asia 2024 Conference Papers. 1\u201312."},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658214"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461961"},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731047.1731054"},{"key":"e_1_2_2_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/3610548.3618207"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3731183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:51:13Z","timestamp":1774633873000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,27]]},"references-count":84,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,1]]}},"alternative-id":["10.1145\/3731183"],"URL":"https:\/\/doi.org\/10.1145\/3731183","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,27]]},"assertion":[{"value":"2025-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}