{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:24:09Z","timestamp":1774686249705,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T00:00:00Z","timestamp":1721347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-23-1-2545"],"award-info":[{"award-number":["N00014-23-1-2545"]}],"id":[{"id":"10.13039\/100000006","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":[[2024,7,19]]},"abstract":"<jats:p>The method of fundamental solutions (MFS) and its associated boundary element method (BEM) have gained popularity in computer graphics due to the reduced dimensionality they offer: for three-dimensional linear problems, they only require variables on the domain boundary to solve and evaluate the solution throughout space, making them a valuable tool in a wide variety of applications. However, MFS and BEM have poor computational scalability and huge memory requirements for large-scale problems, limiting their applicability and efficiency in practice. By leveraging connections with Gaussian Processes and exploiting the sparse structure of the inverses of boundary integral matrices, we introduce a variational preconditioner that can be computed via a sparse inverse-Cholesky factorization in a massively parallel manner. We show that applying our preconditioner to the Preconditioned Conjugate Gradient algorithm greatly improves the efficiency of MFS or BEM solves, up to four orders of magnitude in our series of tests.<\/jats:p>","DOI":"10.1145\/3658199","type":"journal-article","created":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T14:47:57Z","timestamp":1721400477000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Lightning-fast Method of Fundamental Solutions"],"prefix":"10.1145","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9411-1689","authenticated-orcid":false,"given":"Jiong","family":"Chen","sequence":"first","affiliation":[{"name":"INRIA Saclay, Palaiseau, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4891-0172","authenticated-orcid":false,"given":"Florian","family":"Schaefer","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3424-6079","authenticated-orcid":false,"given":"Mathieu","family":"Desbrun","sequence":"additional","affiliation":[{"name":"INRIA Saclay, Palaiseau, France"},{"name":"Ecole Polytechnique, Palaiseau, France"}]}],"member":"320","published-online":{"date-parts":[[2024,7,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492921000015"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2019.04.026"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618374"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018932227617"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383266"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3450626.3459851","article-title":"Multiscale Cholesky preconditioning for ill-conditioned problems","volume":"40","author":"Chen Jiong","year":"2021","unstructured":"Jiong Chen, Florian Sch\u00e4fer, Jin Huang, and Mathieu Desbrun. 2021b. Multiscale Cholesky preconditioning for ill-conditioned problems. ACM Trans. Graph. (SIGGRAPH) 40, 4 (2021), 1--13.","journal-title":"ACM Trans. Graph. (SIGGRAPH)"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2021.110668"},{"key":"e_1_2_1_8_1","volume-title":"Sparse Cholesky factorization for solving nonlinear PDEs via Gaussian processes. arXiv:2304.01294","author":"Chen Yifan","year":"2023","unstructured":"Yifan Chen, Houman Owhadi, and Florian Sch\u00e4fer. 2023. Sparse Cholesky factorization for solving nonlinear PDEs via Gaussian processes. arXiv:2304.01294 (2023)."},{"key":"e_1_2_1_9_1","volume-title":"AIP Conference Proceedings","volume":"1853","author":"Cockayne Jon","year":"2017","unstructured":"Jon Cockayne, Chris Oates, Tim Sullivan, and Mark Girolami. 2017. Probabilistic numerical methods for PDE-constrained Bayesian inverse problems. In AIP Conference Proceedings, Vol. 1853."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S106482750038146X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-7977(87)90014-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925899"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073595"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0719090"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2015.05.238"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492914000130"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"e_1_2_1_18_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et al. 2010. Eigen library. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.2018.1437476"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"e_1_2_1_21_1","volume-title":"Arithmetic, Part II: Application to Multi-Dimensional Problems. Computing 64 (01","author":"Hackbusch Wolfgang","year":"2000","unstructured":"Wolfgang Hackbusch and B. Khoromskij. 2000. A Sparse \u210b-Matrix Arithmetic, Part II: Application to Multi-Dimensional Problems. Computing 64 (01 2000)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417799"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141983"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311542"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680010208"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-STS755"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0614004"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00791-014-0226-7"},{"key":"e_1_2_1_29_1","unstructured":"Ronald Kriemann. 2024. HLibPro. https:\/\/www.hlibpro.com\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024211"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2008.01293.x"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360691"},{"key":"e_1_2_1_33_1","unstructured":"Houman Owhadi. 2023. Gaussian process hydrodynamics. Appl. Math. Mech. (2023) 1--24."},{"key":"e_1_2_1_34_1","volume-title":"From a Game Theoretic Approach to Numerical Approximation and Algorithm Design","author":"Owhadi Houman","unstructured":"Houman Owhadi and Clint Scovel. 2019. Operator-Adapted Wavelets, Fast Solvers, and Numerical Homogenization: From a Game Theoretic Approach to Numerical Approximation and Algorithm Design. Vol. 35. Cambridge University Press."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392374"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530134"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1336254"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M129526X"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01389491"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323002"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555441"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530109"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1015362194"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1046\/j.1369-7412.2003.05512.x"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018937506719"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14625"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592109"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185570"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1988.tb01729.x"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2021.04.005"},{"key":"e_1_2_1_52_1","first-page":"1","article-title":"A GPU-based multilevel additive schwarz preconditioner for cloth and deformable body simulation","volume":"41","author":"Wu Botao","year":"2022","unstructured":"Botao Wu, Zhendong Wang, and Huamin Wang. 2022. A GPU-based multilevel additive schwarz preconditioner for cloth and deformable body simulation. ACM Trans. Graph. (SIGGRAPH) 41, 4 (2022), 1--14.","journal-title":"ACM Trans. Graph. (SIGGRAPH)"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02672769"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.3390\/app9245335"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731047.1731054"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2020.107081"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658199","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658199","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:04:16Z","timestamp":1750291456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,19]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7,19]]}},"alternative-id":["10.1145\/3658199"],"URL":"https:\/\/doi.org\/10.1145\/3658199","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,19]]},"assertion":[{"value":"2024-07-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}