{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:21:45Z","timestamp":1764969705309,"version":"3.46.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T00:00:00Z","timestamp":1764806400000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2403122","2440472","1844538"],"award-info":[{"award-number":["2403122","2440472","1844538"]}],"id":[{"id":"10.13039\/100000001","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":[[2025,12]]},"abstract":"<jats:p>We present a variance reduction technique for Walk on Spheres (WoS) that solves elliptic partial differential equations (PDEs) by combining overlapping harmonic expansions of the solution, each estimated using unbiased Monte Carlo random walks. Our method supports Laplace and screened Poisson equations with Dirichlet, Neumann, and Robin boundary conditions in both 2D and 3D. By adaptively covering the domain with local expansion regions and reconstructing the solution inside each region using an infinite Fourier series of the harmonic function, our method achieves over an order of magnitude lower error than traditional pointwise WoS in equal time. While low-order truncations of the series typically introduce limited bias, we also introduce a stochastic truncation scheme that eliminates this bias in the reconstructed solution. Compared to recently developed caching algorithms for WoS, such as Boundary and Mean Value Caching, our approach yields solutions with lower error and fewer correlation artifacts.<\/jats:p>","DOI":"10.1145\/3763322","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T17:15:39Z","timestamp":1764868539000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Harmonic Caching for Walk on Spheres"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-6052-2931","authenticated-orcid":false,"given":"Zihong","family":"Zhou","sequence":"first","affiliation":[{"name":"Dartmouth College, Hanover, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3761-2989","authenticated-orcid":false,"given":"Eugene","family":"d'Eon","sequence":"additional","affiliation":[{"name":"NVIDIA Research, Wellington, New Zealand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3661-1554","authenticated-orcid":false,"given":"Rohan","family":"Sawhney","sequence":"additional","affiliation":[{"name":"NVIDIA Research, Seattle, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1652-0954","authenticated-orcid":false,"given":"Wojciech","family":"Jarosz","sequence":"additional","affiliation":[{"name":"Dartmouth College, Hanover, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"James Richard Arvo. 1993. Transfer Functions in Global Illumination. In Global Illumination (ACM SIGGRAPH Courses). 1\u201328."},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the Eurographics Symposium on Rendering (EGSR), Tobias Ritschel and Andrea Weidlich (Eds.). Eurographics Association. gsk2p7","author":"Bakbouk Ghada","year":"2023","unstructured":"Ghada Bakbouk and Pieter Peers. 2023. Mean Value Caching for Walk on Spheres. In Proceedings of the Eurographics Symposium on Rendering (EGSR), Tobias Ritschel and Andrea Weidlich (Eds.). Eurographics Association. gsk2p7"},{"key":"e_1_2_2_3_1","first-page":"4","article-title":"Coupling Conduction, Convection and Radiative Transfer in a Single Path-Space: Application to Infrared Rendering","volume":"42","author":"Bati M\u00e9gane","year":"2023","unstructured":"M\u00e9gane Bati, St\u00e9phane 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 Transactions on Graphics (Proceedings of SIGGRAPH) 42, 4 (July 2023), 79:1\u201379:20. gsk4f5","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(82)90079-1"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(81)90159-5"},{"key":"e_1_2_2_6_1","series-title":"Pure and Applied Undergraduate Texts","volume-title":"Partial Differential Equations: A First Course. Number","author":"Choksi Rustum","unstructured":"Rustum Choksi. 2022. Partial Differential Equations: A First Course. Number volume 54 in Pure and Applied Undergraduate Texts. American Mathematical Society, Providence, Rhode Island."},{"key":"e_1_2_2_7_1","unstructured":"Michael Czekanski Benjamin Faber Margaret Fairborn Adelle Wright and David Bindel. 2024. Walking on Spheres and Talking to Neighbors: Variance Reduction for Laplace's Equation. arXiv:2404.17692 [physics]"},{"key":"e_1_2_2_8_1","volume-title":"Heat Simulation on Meshless Crafted-Made Shapes. In ACM SIGGRAPH Conference on Motion, Interaction and Games (MIG '23)","author":"Lambilly Auguste De","year":"2023","unstructured":"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 ACM SIGGRAPH Conference on Motion, Interaction and Games (MIG '23). ACM Press, 1\u20137. g57648"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781315371412"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2005.05.023"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3721238.3730593"},{"key":"e_1_2_2_12_1","volume-title":"Neural Monte Carlo Fluid Simulation. In ACM SIGGRAPH Conference Papers (SIGGRAPH '24)","author":"Jain Pranav","year":"2024","unstructured":"Pranav Jain, Ziyin Qu, Peter Yichen Chen, and Oded Stein. 2024. Neural Monte Carlo Fluid Simulation. In ACM SIGGRAPH Conference Papers (SIGGRAPH '24). Association for Computing Machinery, New York, NY, USA, 1\u201311. gt48wt"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1330511.1330518"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2231816.2231823"},{"key":"e_1_2_2_15_1","volume-title":"Irradiance Gradients in the Presence of Participating Media and Occlusions. Computer Graphics Forum (Proceedings of the Eurographics Symposium on Rendering) 27","author":"Jarosz Wojciech","year":"2008","unstructured":"Wojciech Jarosz, Matthias Zwicker, and Henrik Wann Jensen. 2008b. Irradiance Gradients in the Presence of Participating Media and Occlusions. Computer Graphics Forum (Proceedings of the Eurographics Symposium on Rendering) 27, 4 (June 2008), 1087\u20131096. bg8nww"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090122.1090148"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.83"},{"key":"e_1_2_2_18_1","volume-title":"Neural Caches for Monte Carlo Partial Differential Equation Solvers. In ACM SIGGRAPH Asia Conference Papers. Association for Computing Machinery","author":"Li Zilu","year":"2023","unstructured":"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 ACM SIGGRAPH Asia Conference Papers. Association for Computing Machinery, New York, NY, USA, 1\u201310. gs82vd"},{"key":"e_1_2_2_19_1","volume-title":"Neural Control Variates with Automatic Integration. In ACM SIGGRAPH Conference Papers (SIGGRAPH '24)","author":"Li Zilu","year":"2024","unstructured":"Zilu Li, Guandao Yang, Qingqing Zhao, Xi Deng, Leonidas Guibas, Bharath Hariharan, and Gordon Wetzstein. 2024. Neural Control Variates with Automatic Integration. In ACM SIGGRAPH Conference Papers (SIGGRAPH '24). Association for Computing Machinery, New York, NY, USA, 1\u20139. gt48wv"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3185225"},{"key":"e_1_2_2_21_1","first-page":"4","article-title":"Boundary Value Caching for Walk on Spheres","volume":"42","author":"Miller Bailey","year":"2023","unstructured":"Bailey Miller, Rohan Sawhney, Keenan Crane, and Ioannis Gkioulekas. 2023. Boundary Value Caching for Walk on Spheres. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 42, 4 (July 2023), 82:1\u201382:11. gsk4f8","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3687913"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658153"},{"key":"e_1_2_2_24_1","first-page":"4","article-title":"Unbiased and Consistent Rendering Using Biased Estimators","volume":"41","author":"Misso Zackary","year":"2022","unstructured":"Zackary Misso, Benedikt Bitterli, Iliyan Georgiev, and Wojciech Jarosz. 2022. Unbiased and Consistent Rendering Using Biased Estimators. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 41, 4 (July 2022), 48:1\u201348:13. gqjn66","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728169"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4655(94)00185-5"},{"key":"e_1_2_2_27_1","first-page":"4","article-title":"Kelvin Transformations for Simulations on Infinite Domains","volume":"40","author":"Nabizadeh Mohammad Sina","year":"2021","unstructured":"Mohammad Sina Nabizadeh, Ravi Ramamoorthi, and Albert Chern. 2021. Kelvin Transformations for Simulations on Infinite Domains. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 40, 4 (July 2021), 97:1\u201397:15. gnmwgs","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/3692070.3693583"},{"key":"e_1_2_2_29_1","volume-title":"Metropolis Light Transport for Participating Media. In Rendering Techniques (Proceedings of the Eurographics Workshop on Rendering). Springer-Verlag","author":"Pauly Mark","year":"2000","unstructured":"Mark Pauly, Thomas Kollig, and Alexander Keller. 2000. Metropolis Light Transport for Participating Media. In Rendering Techniques (Proceedings of the Eurographics Workshop on Rendering). Springer-Verlag, Vienna, 11\u201322. gfzm93"},{"volume-title":"Physically Based Rendering: From Theory to Implementation (2 ed.). Morgan Kaufmann","author":"Pharr Matt","key":"e_1_2_2_30_1","unstructured":"Matt Pharr and Greg Humphreys. 2010. Physically Based Rendering: From Theory to Implementation (2 ed.). Morgan Kaufmann, San Francisco, USA."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14586"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2231816.2231819"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189762.1189764"},{"key":"e_1_2_2_34_1","first-page":"6","article-title":"A Monte Carlo Method for Fluid Simulation","volume":"41","author":"Rioux-Lavoie Damien","year":"2022","unstructured":"Damien Rioux-Lavoie, Ryusuke Sugimoto, T\u00fcmay \u00d6zdemir, Naoharu H. Shimada, Christopher Batty, Derek Nowrouzezahrai, and Toshiya Hachisuka. 2022. A Monte Carlo Method for Fluid Simulation. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) 41, 6 (Nov. 2022), 240:1\u2013240:16. gscnnz","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia)"},{"key":"e_1_2_2_35_1","article-title":"Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-based Methods on Volumetric Domains","volume":"39","author":"Sawhney Rohan","year":"2020","unstructured":"Rohan Sawhney and Keenan Crane. 2020. Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-based Methods on Volumetric Domains. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 39, 4 (2020). ghw7t7","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_36_1","volume-title":"Zombie: A Grid-Free Monte Carlo Solver for PDEs.","author":"Sawhney Rohan","year":"2023","unstructured":"Rohan Sawhney and Bailey Miller. 2023. Zombie: A Grid-Free Monte Carlo Solver for PDEs."},{"key":"e_1_2_2_37_1","first-page":"4","article-title":"Walk on Stars: A Grid-Free Monte Carlo Method for PDEs with Neumann Boundary Conditions","volume":"42","author":"Sawhney Rohan","year":"2023","unstructured":"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 Transactions on Graphics (Proceedings of SIGGRAPH) 42, 4 (July 2023), 80:1\u201380:20. gsk4f6","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_38_1","first-page":"4","article-title":"Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients","volume":"41","author":"Sawhney Rohan","year":"2022","unstructured":"Rohan Sawhney, Dario Seyb, Wojciech Jarosz, and Keenan Crane. 2022. Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 41, 4 (July 2022), 53:1\u201353:17. gqjn65","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_39_1","first-page":"6","article-title":"Practical Hessian-based Error Control for Irradiance Caching","volume":"31","author":"Schwarzhaupt Jorge","year":"2012","unstructured":"Jorge Schwarzhaupt, Henrik Wann Jensen, and Wojciech Jarosz. 2012. Practical Hessian-based Error Control for Irradiance Caching. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) 31, 6 (Nov. 2012), 1. gbb6n4","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia)"},{"key":"e_1_2_2_40_1","first-page":"2","article-title":"Analysis of Sample Correlations for Monte Carlo Rendering","volume":"38","author":"Singh Gurprit","year":"2019","unstructured":"Gurprit Singh, Cengiz \u00d6ztireli, Abdalla G.M. Ahmed, David Coeurjolly, Kartic Subr, Oliver Deussen, Victor Ostromoukhov, Ravi Ramamoorthi, and Wojciech Jarosz. 2019. Analysis of Sample Correlations for Monte Carlo Rendering. Computer Graphics Forum (Proceedings of Eurographics State of the Art Reports) 38, 2 (April 2019). gf6rzc","journal-title":"Computer Graphics Forum (Proceedings of Eurographics State of the Art Reports)"},{"key":"e_1_2_2_41_1","first-page":"4","article-title":"A Practical Walk-on-Boundary Method for Boundary Value Problems","volume":"42","author":"Sugimoto Ryusuke","year":"2023","unstructured":"Ryusuke Sugimoto, Terry Chen, Yiti Jiang, Christopher Batty, and Toshiya Hachisuka. 2023. A Practical Walk-on-Boundary Method for Boundary Value Problems. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 42, 4 (July 2023), 81:1\u201381:16. gsk4f7","journal-title":"ACM Transactions on Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_42_1","volume-title":"Heckbert","author":"Ward Gregory J.","year":"1992","unstructured":"Gregory J. Ward and Paul S. Heckbert. 1992. Irradiance Gradients. In CE_EGWR93, Alan Chalmers, Derek Paddon, and Fran\u00e7ois X. Sillion (Eds.). Consolidation Express Bristol, Bristol, UK, 85\u201398."},{"key":"e_1_2_2_43_1","first-page":"4","article-title":"A Ray Tracing Solution for Diffuse Interreflection","volume":"22","author":"Ward Gregory J.","year":"1988","unstructured":"Gregory J. Ward, Francis M. Rubinstein, and Robert D. Clear. 1988. A Ray Tracing Solution for Diffuse Interreflection. Computer Graphics (Proceedings of SIGGRAPH) 22, 4 (Aug. 1988), 85\u201392. dk6rt5","journal-title":"Computer Graphics (Proceedings of SIGGRAPH)"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3687990"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3641519.3657460"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763322","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:19:13Z","timestamp":1764969553000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3763322"],"URL":"https:\/\/doi.org\/10.1145\/3763322","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-05-23","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"}}]}}