{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:10:30Z","timestamp":1784268630511,"version":"3.55.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>We present a novel multigrid solver framework that significantly advances the efficiency of physical simulation for unstructured meshes. While multi-grid methods theoretically offer linear scaling, their practical implementation for deformable body simulations faces substantial challenges, particularly on GPUs. Our framework achieves up to 6.9\u00d7 speedup over traditional methods through an innovative combination of matrix-free vertex block Jacobi smoothing with a Full Approximation Scheme (FAS), enabling both piecewise constant and linear Galerkin formulations without the computational burden of dense coarse matrices. Our approach demonstrates superior performance across varying mesh resolutions and material stiffness values, maintaining consistent convergence even under extreme deformations and challenging initial configurations. Comprehensive evaluations against state-of-the-art methods confirm our approach achieves lower simulation error with reduced computational cost, enabling simulation of tetrahedral meshes with over one million vertices at approximately one frame per second on modern GPUs.<\/jats:p>","DOI":"10.1145\/3763327","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T17:15:39Z","timestamp":1764868539000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast Galerkin Multigrid Method for Unstructured Meshes"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7793-0463","authenticated-orcid":false,"given":"Jia-Ming","family":"Lu","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6119-8829","authenticated-orcid":false,"given":"Tailing","family":"Yuan","sequence":"additional","affiliation":[{"name":"Independent Researcher, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2151-2881","authenticated-orcid":false,"given":"Zhe-Han","family":"Mo","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7507-6542","authenticated-orcid":false,"given":"Shi-Min","family":"Hu","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073625"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280821"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_1_4_1","volume-title":"Multi-level adaptive solutions to boundary-value problems. Mathematics of computation 31, 138","author":"Brandt Achi","year":"1977","unstructured":"Achi Brandt. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of computation 31, 138 (1977), 333\u2013390."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658179"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Nuttapong Chentanez and Matthias M\u00fcller. 2011. Real-time Eulerian water simulation using a restricted tall cell grid. In ACM Siggraph 2011 Papers. 1\u201310.","DOI":"10.1145\/1964921.1964977"},{"key":"e_1_2_1_7_1","volume-title":"Solving the fluid pressure Poisson equation using multigrid\u2014evaluation and improvements","author":"Dick Christian","year":"2015","unstructured":"Christian Dick, Marcus Rogowsky, and R\u00fcdiger Westermann. 2015. Solving the fluid pressure Poisson equation using multigrid\u2014evaluation and improvements. IEEE transactions on visualization and computer graphics 22, 11 (2015), 2480\u20132492."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2307873"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2459687"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2006.02.016"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207169208804096"},{"key":"e_1_2_1_12_1","volume-title":"Computer Graphics Forum","author":"Jeon Inyong","unstructured":"Inyong Jeon, Kwang-Jin Choi, Tae-Yong Kim, Bong-Ouk Choi, and Hyeong-Seok Ko. 2013. Constrainable multigrid for cloth. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 31\u201339."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3388769.3407490"},{"key":"e_1_2_1_14_1","volume-title":"Computer Graphics Forum","author":"Lee Yongjoon","unstructured":"Yongjoon Lee, Sung-eui Yoon, Seungwoo Oh, Duksu Kim, and Sunghee Choi. 2010. Multi-resolution cloth simulation. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 2225\u20132232."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_1_16_1","article-title":"Surface multigrid via intrinsic prolongation","volume":"40","author":"Derek Liu Hsueh-Ti","year":"2021","unstructured":"Hsueh-Ti Derek Liu, Jiayi Eris Zhang, Mirela Ben-Chen, and Alec Jacobson. 2021. Surface multigrid via intrinsic prolongation. ACM Transactions on Graphics 40, 4 (2021), 13 pages.","journal-title":"ACM Transactions on Graphics"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508406"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3309486.3340247"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459748"},{"key":"e_1_2_1_20_1","volume-title":"Symposium on Computer Animation","volume":"65","author":"McAdams Aleka","year":"2010","unstructured":"Aleka McAdams, Eftychios Sifakis, and Joseph Teran. 2010. A Parallel Multigrid Poisson Solver for Fluids Simulation on Large Grids.. In Symposium on Computer Animation, Vol. 65. 74."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964932"},{"key":"e_1_2_1_22_1","volume-title":"Computer Graphics Forum","author":"Mercier-Aubin Alexandre","unstructured":"Alexandre Mercier-Aubin and Paul G Kry. 2024. A Multi-layer Solver for XPBD. In Computer Graphics Forum. Wiley Online Library, e15186."},{"key":"e_1_2_1_23_1","volume-title":"Hierarchical position-based dynamics. (03","author":"M\u00fcller Matthias","year":"2015","unstructured":"Matthias M\u00fcller. 2015. Hierarchical position-based dynamics. (03 2015)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/140980260"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1272690.1272715"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3687758"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530109"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2514\/1.36792"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180491"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818081"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550469.3555418"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386760"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41095-023-0368-y"},{"key":"e_1_2_1_36_1","volume-title":"Computer Graphics Forum","author":"Wang Zhendong","unstructured":"Zhendong Wang, Longhua Wu, Marco Fratarcangeli, Min Tang, and Huamin Wang. 2018. Parallel multigrid for nonlinear cloth simulation. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 131\u2013141."},{"key":"e_1_2_1_37_1","volume-title":"Computer Graphics Forum","author":"Weber Daniel","unstructured":"Daniel Weber, Johannes Mueller-Roemer, Andr\u00e9 Stork, and Dieter Fellner. 2015. A Cut-Cell Geometric Multigrid Poisson Solver for Fluid Simulation. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 481\u2013491."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530085"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356486"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555469"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618388"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658214"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731047.1731054"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:18:14Z","timestamp":1764969494000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3763327"],"URL":"https:\/\/doi.org\/10.1145\/3763327","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-05-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}