Walkin’ Robin: Walk on Stars with Robin Boundary Conditions
Article No.: 41, Pages 1 - 18
Abstract
Numerous scientific and engineering applications require solutions to boundary value problems (BVPs) involving elliptic partial differential equations, such as the Laplace or Poisson equations, on geometrically intricate domains. We develop a Monte Carlo method for solving such BVPs with arbitrary first-order linear boundary conditions---Dirichlet, Neumann, and Robin. Our method directly generalizes the walk on stars (WoSt) algorithm, which previously tackled only the first two types of boundary conditions, with a few simple modifications. Unlike conventional numerical methods, WoSt does not need finite element meshing or global solves. Similar to Monte Carlo rendering, it instead computes pointwise solution estimates by simulating random walks along star-shaped regions inside the BVP domain, using efficient ray-intersection and distance queries. To ensure WoSt produces bounded-variance estimates in the presence of Robin boundary conditions, we show that it is sufficient to modify how WoSt selects the size of these star-shaped regions. Our generalized WoSt algorithm reduces estimation error by orders of magnitude relative to alternative grid-free methods such as the walk on boundary algorithm. We also develop bidirectional and boundary value caching strategies to further reduce estimation error. Our algorithm is trivial to parallelize, scales sublinearly with increasing geometric detail, and enables progressive and view-dependent evaluation.
References
[1]
Robert Anderson, Julian Andrej, Andrew Barker, et al. 2021. MFEM: A modular finite element methods library. Computers & Mathematics with Applications 81 (2021).
[2]
James Arvo. 1995a. The role of functional analysis in global illumination. In Rendering Techniques' 95: Proceedings of the Eurographics Workshop in Dublin, Ireland, June 12--14, 1995 6. Springer, 115--126.
[3]
James Richard Arvo. 1995b. Analytic methods for simulated light transport. Ph. D. Dissertation. Yale University.
[4]
Ghada Bakbouk and Pieter Peers. 2023. Mean Value Caching for Walk on Spheres. In Eurographics Symposium on Rendering, Tobias Ritschel and Andrea Weidlich (Eds.). The Eurographics Association.
[5]
Gavin Barill, Neil G. Dickson, Ryan Schmidt, David I. W. Levin, and Alec Jacobson. 2018. Fast Winding Numbers for Soups and Clouds. ACM Trans. Graph. 37, 4, Article 43 (2018), 12 pages.
[6]
Bruce A Barnes. 1990. Spectral properties of linear Volterra operators. Journal of Operator Theory (1990), 365--382.
[7]
Mégane Bati, Stéphane Blanco, Christophe Coustet, Vincent Eymet, Vincent Forest, Richard Fournier, Jacques Gautrais, Nicolas Mellado, Mathias Paulin, and Benjamin Piaud. 2023. Coupling Conduction, Convection and Radiative Transfer in a Single Path-Space: Application to Infrared Rendering. ACM Trans. Graph. 42, 4 (aug 2023).
[8]
Mireille Bossy, Nicolas Champagnat, Sylvain Maire, and Denis Talay. 2010. Probabilistic interpretation and random walk on spheres algorithms for the Poisson-Boltzmann equation in molecular dynamics. ESAIM: Mathematical Modelling and Numerical Analysis 44, 5 (2010), 997--1048.
[9]
Barbara Busnello, Franco Flandoli, and Marco Romito. 2005. A probabilistic representation for the vorticity of a three-dimensional viscous fluid and for general systems of parabolic equations. Proc. Edinburgh Math. Soc. 48, 2 (2005), 295--336.
[10]
Cadence. 2024. Using a Thermal FEA Solver for Heat Management in Your PCB. Retrieved January 6, 2024 from https://resources.pcb.cadence.com/blog/2020-using-a-thermal-fea-solver-for-heat-management-in-your-pcb
[11]
Chris J Coleman, David L Tullock, and Nhan Phan-Thien. 1991. An effective boundary element method for inhomogeneous PDEs. J. App. Math. Phys. (ZAMP) 42, 5 (1991).
[12]
Martin Costabel. 1987. Principles of boundary element methods. Computer Physics Reports 6, 1--6 (1987), 243--274.
[13]
Auguste De Lambilly, Gabriel Benedetti, Nour Rizk, Chen Hanqi, Siyuan Huang, Junnan Qiu, David Louapre, Raphael Granier De Cassagnac, and Damien Rohmer. 2023. Heat Simulation on Meshless Crafted-Made Shapes. In Proceedings of the 16th ACM SIGGRAPH Conference on Motion, Interaction and Games (<conf-loc>, <city>Rennes</city>, <country>France</country>, </conf-loc>) (MIG '23). Association for Computing Machinery, New York, NY, USA, Article 9, 7 pages.
[14]
Michael Deering, Stephanie Winner, Bic Schediwy, Chris Duffy, and Neil Hunt. 1988. The triangle processor and normal vector shader: a VLSI system for high performance graphics. Acm siggraph computer graphics 22, 4 (1988), 21--30.
[15]
SP Eveson. 2003. Norms of iterates of Volterra operators on L 2. Journal of Operator Theory (2003), 369--386.
[16]
Nicole Feng, Mark Gillespie, and Keenan Crane. 2023. Winding Numbers on Discrete Surfaces. ACM Trans. Graph. 42, 4, Article 36 (jul 2023), 17 pages.
[17]
Natasha Flyer, Bengt Fornberg, Victor Bayona, and Gregory A Barnett. 2016. On the role of polynomials in RBF-FD approximations: I. Interpolation and accuracy. J. Comput. Phys. 321 (2016), 21--38.
[18]
Denis S Grebenkov. 2006. Partially reflected Brownian motion: a stochastic approach to transport phenomena. arXiv preprint math/0610080 (2006).
[19]
Denis S Grebenkov. 2007. NMR survey of reflected Brownian motion. Reviews of Modern Physics 79, 3 (2007), 1077.
[20]
Wolfgang Hackbusch. 2015. Hierarchical matrices: algorithms and analysis. Vol. 49. Springer Berlin, Heidelberg.
[21]
Stefan Heinrich and Peter Mathé. 1993. The Monte Carlo complexity of Fredholm integral equations. mathematics of computation 60, 201 (1993), 257--278.
[22]
Desmond J Higham. 2001. An algorithmic introduction to numerical simulation of stochastic differential equations. SIAM review 43, 3 (2001), 525--546.
[23]
Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast Tetrahedral Meshing in the Wild. ACM Trans. Graph. 39, 4 (2020), 18 pages.
[24]
Peter Hunter and Andrew Pullan. 2001. Fem/bem notes. Department of Engineering Science, The University of Auckland, New Zeland (2001).
[25]
Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1--12.
[26]
David E Johnson and Elaine Cohen. 2001. Spatialized normal come hierarchies. In Proceedings of the 2001 symposium on Interactive 3D graphics. 129--134.
[27]
Konrad Jörgens. 1982. Linear integral operators. Pitman.
[28]
Derek Juba, Walid Keyrouz, Michael Mascagni, and Mary Brady. 2016. Acceleration and Parallelization of ZENO/Walk-on-Spheres. Procedia Computer Science 80 (2016), 269--278. International Conference on Computational Science 2016, ICCS 2016, 6--8 June 2016, San Diego, California, USA.
[29]
Malvin H Kalos and Paula A Whitlock. 2009. Monte carlo methods. John Wiley & Sons.
[30]
Ehsan Kamel and Ali Kazemian. 2023. BIM-integrated thermal analysis and building energy modeling in 3D-printed residential buildings. Energy and Buildings 279 (2023), 112670.
[31]
Tosio Kato. 2013. Perturbation theory for linear operators. Vol. 132. Springer Science & Business Media.
[32]
Bastian Krayer and Stefan Müller. 2021. Hierarchical Point Distance Fields. In International Symposium on Visual Computing. Springer, 435--446.
[33]
Aditi Krishnapriyan, Amir Gholami, Shandian Zhe, Robert Kirby, and Michael W Mahoney. 2021. Characterizing possible failure modes in physics-informed neural networks. Advances in Neural Information Processing Systems 34 (2021), 26548--26560.
[34]
Andreas E Kyprianou, Ana Osojnik, and Tony Shardlow. 2017. Unbiased 'walk-on-spheres' Monte Carlo methods for the fractional Laplacian. IMA J. Numer. Anal. 38, 3 (08 2017), 1550--1578. arXiv:https://academic.oup.com/imajna/article-pdf/38/3/1550/25170901/drx042.pdf
[35]
Eric P Lafortune and Yves D Willems. 1993. Bi-directional path tracing. In Proc. Int. Conf. Comp. Graph. Vis. Tech. Alvor, Portugal.
[36]
Samuli Laine, Tero Karras, and Timo Aila. 2013. Megakernels considered harmful: wavefront path tracing on GPUs. In Proceedings of the 5th High-Performance Graphics Conference (Anaheim, California) (HPG '13). Association for Computing Machinery, New York, NY, USA, 137--143.
[37]
Shaofan Li and Wing Kam Liu. 2007. Meshfree particle methods. Springer Berlin, Heidelberg.
[38]
Zilu Li, Guandao Yang, Xi Deng, Christopher De Sa, Bharath Hariharan, and Steve Marschner. 2023. Neural Caches for Monte Carlo Partial Differential Equation Solvers. In SIGGRAPH Asia 2023 Conference Papers (<conf-loc>, <city>Sydney</city>, <state>NSW</state>, <country>Australia</country>, </conf-loc>) (SA '23). Association for Computing Machinery, New York, NY, USA, Article 34, 10 pages.
[39]
Frank Losasso, Ronald Fedkiw, and Stanley Osher. 2006. Spatially adaptive techniques for level set methods and incompressible flow. Computers & Fluids 35, 10 (2006).
[40]
Michael Mascagni and Nikolai A Simonov. 2004. Monte Carlo Methods for Calculating Some Physical Properties of Large Molecules. SIAM J. Sci. Comp. 26, 1 (2004).
[41]
Bailey Miller, Rohan Sawhney, Keenan Crane, and Ioannis Gkioulekas. 2023. Boundary Value Caching for Walk on Spheres. ACM Trans. Graph. 42, 4, Article 82 (jul 2023), 11 pages.
[42]
Jean-Paul Morillon. 1997. Numerical solutions of linear mixed boundary value problems using stochastic representations. International journal for numerical methods in engineering 40, 3 (1997), 387--405.
[43]
Linus Mossberg. 2021. GPU-Accelerated Monte Carlo Geometry Processing for GradientDomain Methods. Ph. D. Dissertation. Linköping University, Linköping, Sweden.
[44]
Mervin E Muller. 1956. Some Continuous Monte Carlo Methods for the Dirichlet Problem. Annals of Mathematical Statistics 27, 3 (Sept. 1956), 569--589.
[45]
Mohammad Sina Nabizadeh, Ravi Ramamoorthi, and Albert Chern. 2021. Kelvin Transformations for Simulations on Infinite Domains. ACM Trans. Graph. 40, 4, Article 97 (jul 2021), 15 pages.
[46]
NASA. 1999. Guidelines for Thermal Analysis of Spacecraft Hardware. Retrieved January 6, 2024 from https://llis.nasa.gov/lesson/695
[47]
Jean-Claude Nédélec. 2001. Acoustic and electromagnetic equations: integral representations for harmonic problems. Vol. 144. Springer.
[48]
B. Øksendal. 2003. Stochastic Differential Equations: An Introduction with Applications. Springer Berlin, Heidelberg.
[49]
Paul William Partridge, Carlos Alberto Brebbia, et al. 2012. Dual reciprocity boundary element method.
[50]
Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically based rendering: From theory to implementation. Morgan Kaufmann.
[51]
Yang Qi, Dario Seyb, Benedikt Bitterli, and Wojciech Jarosz. 2022. A bidirectional formulation for Walk on Spheres. Computer Graphics Forum 41, 4 (2022), 51--62. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.14586
[52]
Maziar Raissi, Paris Perdikaris, and George E Karniadakis. 2019. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational physics 378 (2019), 686--707.
[53]
Damien Rioux-Lavoie, Ryusuke Sugimoto, Tümay Özdemir, Naoharu H. Shimada, Christopher Batty, Derek Nowrouzezahrai, and Toshiya Hachisuka. 2022. A Monte Carlo Method for Fluid Simulation. ACM Trans. Graph. 41, 6, Article 240 (nov 2022), 16 pages.
[54]
Karl K Sabelfeld and Nikolai A Simonov. 2013. Random walks on boundary for solving PDEs. De Gruyter.
[55]
Karl K Sabelfeld and Nikolai A Simonov. 2016. Stochastic methods for boundary value problems: numerics for high-dimensional PDEs and applications. Walter de Gruyter GmbH & Co KG.
[56]
Rohan Sawhney. 2021. FCPW: Fastest Closest Points in the West. https://github.com/rohan-sawhney/fcpw
[57]
Rohan Sawhney and Keenan Crane. 2020. Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains. ACM Trans. Graph. 39, 4, Article 123 (aug 2020), 18 pages.
[58]
Rohan Sawhney and Bailey Miller. 2023. Zombie: A Grid-Free Monte Carlo Solver for PDEs. https://github.com/rohan-sawhney/zombie
[59]
Rohan Sawhney, Bailey Miller, Ioannis Gkioulekas, and Keenan Crane. 2023. Walk on Stars: A Grid-Free Monte Carlo Method for PDEs with Neumann Boundary Conditions. ACM Trans. Graph. 42, 4, Article 80 (jul 2023), 20 pages.
[60]
Rohan Sawhney, Dario Seyb, Wojciech Jarosz, and Keenan Crane. 2022. Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients. ACM Trans. Graph. 41, 4, Article 53 (jul 2022), 17 pages.
[61]
Hang Si. 2015. TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator. ACM Trans. Math. Softw. 41, 2, Article 11 (feb 2015), 36 pages.
[62]
Nikolai A Simonov. 2017. Walk-on-spheres algorithm for solving third boundary value problem. Applied Mathematics Letters 64 (2017), 156--161.
[63]
Cyril Soler, Ronak Molazem, and Kartic Subr. 2022. A Theoretical Analysis of Compactness of the Light Transport Operator. In ACM SIGGRAPH 2022 Conference Proceedings (Vancouver, BC, Canada) (SIGGRAPH '22). Association for Computing Machinery, New York, NY, USA, Article 17, 9 pages.
[64]
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 (aug 2023), 16 pages.
[65]
Eric Veach. 1998. Robust Monte Carlo methods for light transport simulation. Stanford University.
[66]
Eric Veach and Leonidas Guibas. 1995. Bidirectional estimators for light transport. In Photorealistic Rendering Techniques. Springer, 145--167.
[67]
Alan V Von Arx and Adon Delgado Jr. 1991. Convective heat transfer on Mars. In AIP Conference Proceedings, Vol. 217. American Institute of Physics, 734--739.
[68]
Ingo Wald. 2007. On fast construction of SAH-based bounding volume hierarchies. In 2007 IEEE Symposium on Interactive Ray Tracing. IEEE, 33--40.
[69]
Ekrem Fatih Yılmazer, Delio Vicini, and Wenzel Jakob. 2022. Solving Inverse PDE Problems using Grid-Free Monte Carlo Estimators. arXiv preprint arXiv:2208.02114 (2022).
[70]
Yijing Zhou and Wei Cai. 2016. Numerical Solution of the Robin Problem of Laplace Equations with a Feynman-Kac Formula and Reflecting Brownian Motions. Journal of Scientific Computing 69 (2016).
Index Terms
- Walkin’ Robin: Walk on Stars with Robin Boundary Conditions
Recommendations
Numerical solution of a convection diffusion problem with Robin boundary conditions
We consider a one-dimensional steady-state convection dominated convection-diffusion problem with Robin boundary conditions. We show, both theoretically and with numerical experiments, that numerical solutions obtained using an upwind finite difference ...
Walk on Stars: A Grid-Free Monte Carlo Method for PDEs with Neumann Boundary Conditions
Grid-free Monte Carlo methods based on the walk on spheres (WoS) algorithm solve fundamental partial differential equations (PDEs) like the Poisson equation without discretizing the problem domain or approximating functions in a finite basis. Such ...
A leapfrog multigrid algorithm for the optimal control of parabolic PDEs with Robin boundary conditions
We develop a second-order finite difference scheme for solving the first-order necessary optimality systems arising from the optimal control of parabolic PDEs with Robin boundary conditions. Under the framework of matrix analysis, the proposed leapfrog ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 July 2024
Published in TOG Volume 43, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 380Total Downloads
- Downloads (Last 12 months)380
- Downloads (Last 6 weeks)166
Reflects downloads up to 29 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in