“Lightning-fast Method of Fundamental Solutions” – ACM SIGGRAPH HISTORY ARCHIVES

“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.


ACM Digital Library Publication:



Overview Page:



Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org