{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:07:09Z","timestamp":1784268429701,"version":"3.55.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"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":[[2018,8,31]]},"abstract":"<jats:p>Many computer graphics problems require computing geometric shapes subject to certain constraints. This often results in non-linear and non-convex optimization problems with globally coupled variables, which pose great challenge for interactive applications. Local-global solvers developed in recent years can quickly compute an approximate solution to such problems, making them an attractive choice for applications that prioritize efficiency over accuracy. However, these solvers suffer from lower convergence rate, and may take a long time to compute an accurate result. In this paper, we propose a simple and effective technique to accelerate the convergence of such solvers. By treating each local-global step as a fixed-point iteration, we apply Anderson acceleration, a well-established technique for fixed-point solvers, to speed up the convergence of a local-global solver. To address the stability issue of classical Anderson acceleration, we propose a simple strategy to guarantee the decrease of target energy and ensure its global convergence. In addition, we analyze the connection between Anderson acceleration and quasi-Newton methods, and show that the canonical choice of its mixing parameter is suitable for accelerating local-global solvers. Moreover, our technique is effective beyond classical local-global solvers, and can be applied to iterative methods with a common structure. We evaluate the performance of our technique on a variety of geometry optimization and physics simulation problems. Our approach significantly reduces the number of iterations required to compute an accurate result, with only a slight increase of computational cost per iteration. Its simplicity and effectiveness makes it a promising tool for accelerating existing algorithms as well as designing efficient new algorithms.<\/jats:p>","DOI":"10.1145\/3197517.3201290","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T15:56:23Z","timestamp":1533052583000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":66,"title":["Anderson acceleration for geometry optimization and physics simulation"],"prefix":"10.1145","volume":"37","author":[{"given":"Yue","family":"Peng","sequence":"first","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bailin","family":"Deng","sequence":"additional","affiliation":[{"name":"Cardiff University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juyong","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fanyu","family":"Geng","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenjie","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ligang","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2017.06.031"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/321296.321305"},{"key":"e_1_2_2_3_1","volume-title":"First-Order Methods in Optimization","author":"Beck A.","unstructured":"A. Beck . 2017. First-Order Methods in Optimization . Society for Industrial and Applied Mathematics , Philadelphia, PA . A. Beck. 2017. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/120887679"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03171.x"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2014.01.004"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/040617364"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1996.0059"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.617"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601106"},{"key":"e_1_2_2_13_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob etal 2010. Eigen v3. http:\/\/eigen.tuxfamily.org. (2010).  Ga\u00ebl Guennebaud Beno\u00eet Jacob et al. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org. (2010)."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-015-0078-3"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1076770"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo etal 2016. libigl: A simple C++ geometry processing library. (2016). http:\/\/libigl.github.io\/libigl\/.  Alec Jacobson Daniele Panozzo et al. 2016. libigl: A simple C++ geometry processing library. (2016). http:\/\/libigl.github.io\/libigl\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_17_1","volume-title":"Iterative Methods for Linear and Nonlinear Equations","author":"Kelley C.","unstructured":"C. Kelley . 1995. Iterative Methods for Linear and Nonlinear Equations . Society for Industrial and Applied Mathematics . C. Kelley. 1995. Iterative Methods for Linear and Nonlinear Equations. Society for Industrial and Applied Mathematics."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925920"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/120867846"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1731309.1731336"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508406"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2990496"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141941"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559758"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024174"},{"key":"e_1_2_2_26_1","first-page":"372","article-title":"A method of solving a convex programming problem with convergence rate O (1\/k<sup>2<\/sup>)","volume":"27","author":"Nesterov Yurii","year":"1983","unstructured":"Yurii Nesterov . 1983 . A method of solving a convex programming problem with convergence rate O (1\/k<sup>2<\/sup>) . Soviet Mathematics Doklady 27 (1983), 372 -- 376 . Yurii Nesterov. 1983. A method of solving a convex programming problem with convergence rate O (1\/k<sup>2<\/sup>). Soviet Mathematics Doklady 27 (1983), 372--376.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_2_27_1","volume-title":"Wright","author":"Nocedal Jorge","year":"2006","unstructured":"Jorge Nocedal and Stephen J . Wright . 2006 . Numerical optimization ( 2 nd ed.). Springer-Verlag New York . Jorge Nocedal and Stephen J. Wright. 2006. Numerical optimization (2nd ed.). Springer-Verlag New York.","edition":"2"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598338093"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2730875"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.09.008"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2015.11.018"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0009-2614(80)80396-4"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.540030413"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983621"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10910-011-9863-y"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073618"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2343483.2343501"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766947"},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of EUROGRAPHICS\/ACM SIGGRAPH Symposium on Geometry Processing. 109--116","author":"Sorkine Olga","year":"2007","unstructured":"Olga Sorkine and Marc Alexa . 2007 . As-Rigid-As-Possible Surface Modeling . In Proceedings of EUROGRAPHICS\/ACM SIGGRAPH Symposium on Geometry Processing. 109--116 . Olga Sorkine and Marc Alexa. 2007. As-Rigid-As-Possible Surface Modeling. In Proceedings of EUROGRAPHICS\/ACM SIGGRAPH Symposium on Geometry Processing. 109--116."},{"key":"e_1_2_2_40_1","unstructured":"Olga Sorkine-Hornung and Michael Rabinovich. 2016. Least-Squares Rigid Motion Using SVD. (2016). Technical note.  Olga Sorkine-Hornung and Michael Rabinovich. 2016. Least-Squares Rigid Motion Using SVD. (2016). Technical note."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/110835530"},{"key":"e_1_2_2_42_1","volume-title":"Alternating Anderson-Richardson method: An efficient alternative to preconditioned Krylov methods for large, sparse linear systems. arXiv preprint arXiv:1606.08740","author":"Suryanarayana Phanish","year":"2016","unstructured":"Phanish Suryanarayana , Phanisri P Pratapa , and John E Pask . 2016. Alternating Anderson-Richardson method: An efficient alternative to preconditioned Krylov methods for large, sparse linear systems. arXiv preprint arXiv:1606.08740 ( 2016 ). Phanish Suryanarayana, Phanisri P Pratapa, and John E Pask. 2016. Alternating Anderson-Richardson method: An efficient alternative to preconditioned Krylov methods for large, sparse linear systems. arXiv preprint arXiv:1606.08740 (2016)."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601213"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080677"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/130919398"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/10078356X"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_2_2_49_1","first-page":"271","article-title":"Krylov subspace acceleration for nonlinear multigrid schemes","volume":"6","author":"Washio T.","year":"1997","unstructured":"T. Washio and C. W. Oosterlee . 1997 . Krylov subspace acceleration for nonlinear multigrid schemes . Electronic Transactions on Numerical Analysis 6 , 271 -- 290 (1997). T. Washio and C. W. Oosterlee. 1997. Krylov subspace acceleration for nonlinear multigrid schemes. Electronic Transactions on Numerical Analysis 6, 271--290 (1997).","journal-title":"Electronic Transactions on Numerical Analysis"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2014.05.015"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197517.3201290","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3197517.3201290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:44Z","timestamp":1750210784000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197517.3201290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3197517.3201290"],"URL":"https:\/\/doi.org\/10.1145\/3197517.3201290","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}