“Lightning-fast Method of Fundamental Solutions”
Conference:
Type(s):
Title:
- Lightning-fast Method of Fundamental Solutions
Presenter(s)/Author(s):
Abstract:
This work introduces a variational preconditioner, based on the inverse Cholesky factorization, to improve the efficiency of solving dense systems discretized from boundary integral equations, effectively addressing the scalability issue commonly encountered in boundary-based approaches.
References:
[1]
Robert Altmann, Patrick Henning, and Daniel Peterseim. 2021. Numerical homogenization beyond scale separation. Acta Numerica 30 (2021), 1–86.
[2]
Faisal Amlani, St?phanie Chaillat, and Adrien Loseille. 2019. An efficient preconditioner for adaptive Fast Multipole accelerated Boundary Element Methods to model time-harmonic 3D wave propagation. Comput. Methods Appl. Mech. Eng. 352 (2019), 189–210.
[3]
Seungbae Bang, Kirill Serkh, Oded Stein, and Alec Jacobson. 2023. An Adaptive Fast-Multipole-Accelerated Hybrid Boundary Integral Equation Method for Accurate Diffusion Curves. ACM Trans. Graph. 42, 6, Article 215 (2023).
[4]
Richard K. Beatson, Jon B. Cherrie, and Cameron Mouat. 1999. Fast fitting of radial basis functions: Methods based on preconditioned GMRES iteration. Adv. Comput. Math. 11 (1999), 253–270.
[5]
Jonathan Carr, Richard Beatson, Jon Cherrie, T. Mitchell, W. Fright, Bruce McCallum, and T. Evans. 2001. Reconstruction & representation of 3D objects with radial basis functions. In Proceedings of the Conference on Computer Graphics and Interactive Techniques (SIGGRAPH). 67–76.
[6]
Jiong Chen, Florian Sch?fer, Jin Huang, and Mathieu Desbrun. 2021b. Multiscale Cholesky preconditioning for ill-conditioned problems. ACM Trans. Graph. (SIGGRAPH) 40, 4 (2021), 1–13.
[7]
Yifan Chen, Bamdad Hosseini, Houman Owhadi, and Andrew Stuart. 2021a. Solving and learning nonlinear PDEs with Gaussian processes. J. Comp. Phys. 447 (2021), 110668.
[8]
Yifan Chen, Houman Owhadi, and Florian Sch?fer. 2023. Sparse Cholesky factorization for solving nonlinear PDEs via Gaussian processes. arXiv:2304.01294 (2023).
[9]
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.
[10]
Ricardo Cortez. 2001. The method of regularized Stokeslets. SIAM J. Sci. Comput. 23, 4 (2001), 1204–1225.
[11]
Martin Costabel. 1987. Principles of boundary element methods. Computer Physics Reports 6, 1 (1987), 243–274.
[12]
Fang Da, David Hahn, Christopher Batty, Chris Wojtan, and Eitan Grinspun. 2016. Surface-only liquids. ACM Trans. Graph. (SIGGRAPH) 35, 4 (2016), 1–12.
[13]
Fernando De Goes and Doug L James. 2017. Regularized Kelvinlets: sculpting brushes based on fundamental solutions of elasticity. ACM Trans. Graph. (SIGGRAPH) 36, 4 (2017), 1–11.
[14]
Michael G Duffy. 1982. Quadrature over a pyramid or cube of integrands with a singularity at a vertex. SIAM journal on Numerical Analysis 19, 6 (1982), 1260–1262.
[15]
Massimiliano Ferronato, Carlo Janna, and Giuseppe Gambolati. 2015. A novel factorized sparse approximate inverse preconditioner with supernodes. Procedia Computer Science 51 (2015), 266–275.
[16]
Bengt Fornberg and Natasha Flyer. 2015. Solving PDEs with radial basis functions. Acta Numerica 24 (2015), 215–258.
[17]
L. Greengard and V. Rokhlin. 1987. A fast algorithm for particle simulations. J. Comput. Phys. 73, 2 (1987), 325–348.
[18]
Ga?l Guennebaud, Beno?t Jacob, et al. 2010. Eigen library. http://eigen.tuxfamily.org.
[19]
Joseph Guinness. 2018. Permutation and Grouping Methods for Sharpening Gaussian Process Approximations. Technometrics 60, 4 (2018), 415–429.
[20]
Wolfgang Hackbusch. 1999. A Sparse Matrix Arithmetic Based on ?-Matrices. Part I: Introduction to ?-Matrices. Computing 62 (04 1999), 89–108.
[21]
Wolfgang Hackbusch and B. Khoromskij. 2000. A Sparse ?-Matrix Arithmetic, Part II: Application to Multi-Dimensional Problems. Computing 64 (01 2000).
[22]
Libo Huang and Dominik L Michels. 2020. Surface-only ferrofluids. ACM Trans. Graph. (SIGGRAPH) 39, 6 (2020), 1–17.
[23]
Doug L James, Jernej Barbi?, and Dinesh K Pai. 2006. Precomputed acoustic transfer: output-sensitive, accurate sound generation for geometrically complex vibration sources. ACM Trans. Graph. (SIGGRAPH) 25, 3 (2006), 987–995.
[24]
Doug L. James and Dinesh K. Pai. 1999. ArtDefo: Accurate Real Time Deformable Objects. In Proceedings of the Conference on Computer Graphics and Interactive Techniques (SIGGRAPH). 65–72.
[25]
I. E. Kaporin. 1994. New convergence results and preconditioning strategies for the conjugate gradient method. Numer. Linear Algebra Appl. 1, 2 (1994), 179–210.
[26]
Matthias Katzfuss and Joseph Guinness. 2021. A General Framework for Vecchia Approximations of Gaussian Processes. Statist. Sci. 36, 1 (2021), 124–141.
[27]
Liliya Yurievna Kolotilina and Aleksey Yuryevich Yeremin. 1993. Factorized sparse approximate inverse preconditionings I. Theory. SIAM J. Matrix Anal. Appl. 14, 1 (1993), 45–58.
[28]
Ronald Kriemann. 2013. H-LU factorization on many-core systems. Comput. Visual Sci. 16 (2013), 105–117.
[29]
Ronald Kriemann. 2024. HLibPro. https://www.hlibpro.com/.
[30]
Dilip Krishnan and Richard Szeliski. 2011. Multigrid and multilevel preconditioners for computational photography. ACM Trans. Graph. (SIGGRAPH) 30, 6 (2011), 1–10.
[31]
Sebastian Martin, Peter Kaufmann, Mario Botsch, Martin Wicke, and Markus Gross. 2008. Polyhedral Finite Elements Using Harmonic Basis Functions. Comput. Graph. Forum 27, 5 (2008), 1521–1529.
[32]
Alexandrina Orzan, Adrien Bousseau, Holger Winnem?ller, Pascal Barla, Jo?lle Thollot, and David Salesin. 2008. Diffusion curves: a vector representation for smooth-shaded images. ACM Trans. Graph. (SIGGRAPH) 27, 3 (2008), 1–8.
[33]
Houman Owhadi. 2023. Gaussian process hydrodynamics. Appl. Math. Mech. (2023), 1–24.
[34]
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.
[35]
Rohan Sawhney and Keenan Crane. 2020. Monte Carlo geometry processing: A grid-free approach to PDE-based methods on volumetric domains. ACM Trans. Graph. (SIGGRAPH) 39, 4 (2020).
[36]
Rohan Sawhney, Dario Seyb, Wojciech Jarosz, and Keenan Crane. 2022. Grid-free Monte Carlo for PDEs with spatially varying coefficients. ACM Trans. Graph. (SIGGRAPH) 41, 4 (2022), 1–17.
[37]
Florian Sch?fer. 2021. Inference, Computation, and Games. Ph.D. Dissertation. California Institute of Technology.
[38]
Florian Sch?fer, Matthias Katzfuss, and Houman Owhadi. 2021a. Sparse Cholesky Factorization by Kullback-Leibler Minimization. SIAM J. Sci. Comput 43, 3 (2021), A2019–A2046.
[39]
Florian Sch?fer, Timothy John Sullivan, and Houman Owhadi. 2021b. Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity. Multiscale Model. Simul. 19, 2 (2021), 688–730.
[40]
H. Schippers. 1985. Multigrid methods for boundary integral equations. Numer. Math., 46 (1985), 351–363.
[41]
Camille Schreck, Christian Hafner, and Chris Wojtan. 2019. Fundamental solutions for water wave animation. ACM Trans. Graph. (SIGGRAPH) 38, 4 (2019), 1–14.
[42]
Silvia Sell?n and Alec Jacobson. 2022. Stochastic Poisson Surface Reconstruction. ACM Trans. Graph. (SIGGRAPH) 41, 6 (2022), 1–12.
[43]
Han Shao, Libo Huang, and Dominik L Michels. 2022. A fast unsmoothed aggregation algebraic multigrid framework for the large-scale simulation of incompressible flow. ACM Trans. Graph. (SIGGRAPH) 41, 4 (2022), 1–18.
[44]
Michael L Stein. 2002. The screening effect in kriging. The Annals of Statistics 30, 1 (2002), 298–323.
[45]
Michael L Stein, Zhiyi Chi, and Leah J Welty. 2004. Approximating likelihoods for large spatial data sets. J. R. Stat. Soc., B: Stat. Methodol. 66, 2 (2004), 275–296.
[46]
Olaf Steinbach and Wolfgang L Wendland. 1998. The construction of some efficient preconditioners in the boundary element method. Adv. Comput. Math. 9 (1998), 191–216.
[47]
Ryusuke Sugimoto, Christopher Batty, and Toshiya Hachisuka. 2022. Surface-Only Dynamic Deformables using a Boundary Element Method. In Comput. Graph. Forum, Vol. 41. 75–86.
[48]
Ryusuke Sugimoto, Terry Chen, Yiti Jiang, Christopher Batty, and Toshiya Hachisuka. 2023. A Practical Walk-on-Boundary Method for Boundary Value Problems. ACM Trans. Graph. 42, 4, Article 81 (2023).
[49]
Xin Sun, Guofu Xie, Yue Dong, Stephen Lin, Weiwei Xu, Wencheng Wang, Xin Tong, and Baining Guo. 2012. Diffusion curve textures for resolution-independent texture mapping. ACM Trans. Graph. (SIGGRAPH) 31, 4 (2012), 1–9.
[50]
Aldo V Vecchia. 1988. Estimation and model identification for continuous spatial processes. J. R. Stat. Soc., B: Stat. Methodol. 50, 2 (1988), 297–312.
[51]
Ruoxi Wang, Chao Chen, Jonghyun Lee, and Eric Darve. 2021. PBBFMM3D: a parallel black-box algorithm for kernel matrix-vector multiplication. J. Parallel and Distrib. Comput. 154 (2021), 64–73.
[52]
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.
[53]
Aleksey Yuryevich Yeremin, Liliya Yurievna Kolotilina, and A. A. Nikishin. 2000. Factorized sparse approximate inverse preconditionings – III. Iterative construction of preconditioners. J. Math. Sci. 101 (2000), 3237–3254.
[54]
Deyun Zhong, Ju Zhang, and Liguan Wang. 2019. Fast Implicit Surface Reconstruction for the Radial Basis Functions Interpolant. App. Sci. 24, 9 (2019), 5335–5349.
[55]
Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. (SIGGRAPH) 29, 2 (2010), 1–18.
[56]
Daniel Zilber and Matthias Katzfuss. 2021. Vecchia-Laplace approximations of generalized Gaussian processes for big non-Gaussian spatial data. Comput. Stat. Data Anal. 153 (2021), 107081.
