{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T09:51:19Z","timestamp":1768470679463,"version":"3.49.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>This paper unifies multigrid and multilevel (hierarchical) preconditioners, two widely-used approaches for solving computational photography and other computer graphics simulation problems. It provides detailed experimental comparisons of these techniques and their variants, including an analysis of relative computational costs and how these impact practical algorithm performance. We derive both theoretical convergence rates based on the condition numbers of the systems and their preconditioners, and empirical convergence rates drawn from real-world problems. We also develop new techniques for sparsifying higher connectivity problems, and compare our techniques to existing and newly developed variants such as algebraic and combinatorial multigrid. Our experimental results demonstrate that, except for highly irregular problems, adaptive hierarchical basis function preconditioners generally outperform alternative multigrid techniques, especially when computational complexity is taken into account.<\/jats:p>","DOI":"10.1145\/2070781.2024211","type":"journal-article","created":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T13:58:46Z","timestamp":1322661526000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Multigrid and multilevel preconditioners for computational photography"],"prefix":"10.1145","volume":"30","author":[{"given":"Dilip","family":"Krishnan","sequence":"first","affiliation":[{"name":"New York University"}]},{"given":"Richard","family":"Szeliski","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]}],"member":"320","published-online":{"date-parts":[[2011,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015718"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276495"},{"key":"e_1_2_1_3_1","volume-title":"A Multigrid Tutorial","author":"Briggs W. L.","unstructured":"Briggs , W. L. , Henson , V. E. , and McCormick , S. F. 2000. A Multigrid Tutorial , second ed. SIAM , Philadelphia . Briggs, W. L., Henson, V. E., and McCormick, S. F. 2000. A Multigrid Tutorial, second ed. SIAM, Philadelphia."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Davis T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM.   Davis T. A. 2006. Direct Methods for Sparse Linear Systems . SIAM.","DOI":"10.1137\/1.9780898718881"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360666"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531373"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566573"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531328"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964964"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199410"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1618452.1618462"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731047.1731052"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10331-5_99"},{"key":"e_1_2_1_14_1","volume-title":"Tech. Rep. NYU-TR-941","author":"Krishnan D.","year":"2011","unstructured":"Krishnan , D. , and Szeliski , R . 2011 . Multigrid and multilevel preconditioners for computational photography. Tech. Rep. NYU-TR-941 , New York University , October. Krishnan, D., and Szeliski, R. 2011. Multigrid and multilevel preconditioners for computational photography. Tech. Rep. NYU-TR-941, New York University, October."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2009.147"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015780"},{"key":"e_1_2_1_17_1","volume-title":"Eighth European Conference on Computer Vision (ECCV","author":"Levin A.","year":"2004","unstructured":"Levin , A. , Zomet , A. , Peleg , S. , and Weiss , Y . 2004. Seamless image stitching in the gradient domain . In Eighth European Conference on Computer Vision (ECCV 2004 ), Springer-Verlag , vol. IV , 377--389. Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In Eighth European Conference on Computer Vision (ECCV 2004), Springer-Verlag, vol. IV, 377--389."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1177"},{"key":"e_1_2_1_19_1","volume-title":"ACM SIGGRAPH\/Eurographics Symposium on Computer Animation, 65--74","author":"McAdams A.","unstructured":"McAdams , A. , Sifakis , E. , and Teran , J . 2010. A parallel multigrid Poisson solver for fluids simulation on large grids . ACM SIGGRAPH\/Eurographics Symposium on Computer Animation, 65--74 . McAdams, A., Sifakis, E., and Teran, J. 2010. A parallel multigrid Poisson solver for fluids simulation on large grids. ACM SIGGRAPH\/Eurographics Symposium on Computer Animation, 65--74."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360692"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.741"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.277594"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882269"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.21914\/anziamj.v43i0.465"},{"key":"e_1_2_1_25_1","volume-title":"Iterative Methods for Sparse Linear Systems","author":"Saad Y.","unstructured":"Saad , Y. 2003. Iterative Methods for Sparse Linear Systems , second ed. SIAM. Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, second ed. SIAM."},{"key":"e_1_2_1_26_1","unstructured":"Shewchuk J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. http:\/\/www.cs. berkeley.edu\/~jrs\/ August.  Shewchuk J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. http:\/\/www.cs. berkeley.edu\/~jrs\/ August."},{"key":"e_1_2_1_27_1","volume-title":"Intl. Conf. on Computational Photography (ICCP 11)","author":"Szeliski R.","unstructured":"Szeliski , R. , Uyttendaele , M. , and Steedly , D . 2011. Fast Poisson blending using multi-splines . In Intl. Conf. on Computational Photography (ICCP 11) . Szeliski, R., Uyttendaele, M., and Steedly, D. 2011. Fast Poisson blending using multi-splines. In Intl. Conf. on Computational Photography (ICCP 11)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.56188"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1142005"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767767"},{"key":"e_1_2_1_31_1","unstructured":"Trottenberg U. Oosterlee C. W. and Schuller A. 2000. Multigrid. Academic Press.   Trottenberg U. Oosterlee C. W. and Schuller A. 2000. Multigrid . Academic Press."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018429.1021105"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2070781.2024211","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2070781.2024211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:03Z","timestamp":1750241163000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2070781.2024211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2070781.2024211"],"URL":"https:\/\/doi.org\/10.1145\/2070781.2024211","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2011-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}