“Anderson acceleration for geometry optimization and physics simulation”
Conference:
Type:
Entry Number: 42
Title:
- Anderson acceleration for geometry optimization and physics simulation
Presenter(s)/Author(s):
Abstract:
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.
References:
1. Hengbin An, Xiaowei Jia, and Homer F. Walker. 2017. Anderson acceleration and application to the three-temperature energy equations. J. Comput. Phys. 347 (2017), 1–19.Google ScholarCross Ref
2. Donald G. Anderson. 1965. Iterative Procedures for Nonlinear Integral Equations. J. ACM 12, 4 (1965), 547–560. Google ScholarDigital Library
3. A. Beck. 2017. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA. Google ScholarDigital Library
4. Amir Beck and Luba Tetruashvili. 2013. On the Convergence of Block Coordinate Descent Type Methods. SIAM Journal on Optimization 23, 4 (2013), 2037–2060.Google ScholarDigital Library
5. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-Up: Shaping Discrete Geometry with Projections. Comput. Graph. Forum 31, 5 (2012), 1657–1667. Google ScholarDigital Library
6. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Trans. Graph. 33, 4 (2014), 154:1–154:11. Google ScholarDigital Library
7. Bailin Deng, Sofien Bouaziz, Mario Deuss, Alexandre Kaspar, Yuliy Schwartzburg, and Mark Pauly. 2015. Interactive design exploration for constrained meshes. Computer-Aided Design 61, Supplement C (2015), 13–23. Google ScholarDigital Library
8. Qiang Du, Maria Emelianenko, and Lili Ju. 2006. Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations. SIAM J. Numer. Anal. 44, 1 (2006), 102–119. Google ScholarDigital Library
9. Qiang Du, Vance Faber, and Max Gunzburger. 1999. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Rev. 41, 4 (1999), 637–676. Google ScholarDigital Library
10. V. Eyert. 1996. A Comparative Study on Methods for Convergence Acceleration of Iterative Vector Sequences. J. Comput. Phys. 124, 2 (1996), 271–285. Google ScholarDigital Library
11. Haw-ren Fang and Yousef Saad. 2009. Two classes of multisecant methods for nonlinear acceleration. Numerical Linear Algebra with Applications 16, 3 (2009), 197–221.Google ScholarCross Ref
12. Akash Garg, Andrew O. Sageman-Furnas, Bailin Deng, Yonghao Yue, Eitan Grinspun, Mark Pauly, and Max Wardetzky. 2014. Wire mesh design. ACM Trans. Graph. 33, 4 (2014), 66:1–66:12. Google ScholarDigital Library
13. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org. (2010).Google Scholar
14. Nicholas J. Higham and Nataša Strabić. 2016. Anderson acceleration of the alternating projections method for computing the nearest correlation matrix. Numerical Algorithms 72, 4 (2016), 1021–1042. Google ScholarDigital Library
15. Nguyenho Ho, Sarah D. Olson, and Homer F. Walker. 2017. Accelerating the Uzawa Algorithm. SIAM Journal on Scientific Computing 39, 5 (2017), S461–S476.Google ScholarCross Ref
16. Alec Jacobson, Daniele Panozzo, et al. 2016. libigl: A simple C++ geometry processing library. (2016). http://libigl.github.io/libigl/.Google Scholar
17. C. Kelley. 1995. Iterative Methods for Linear and Nonlinear Equations. Society for Industrial and Applied Mathematics.Google Scholar
18. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated quadratic proxy for geometric optimization. ACM Trans. Graph. 35, 4 (2016), 134:1–134:11. Google ScholarDigital Library
19. K. Lipnikov, D. Svyatskiy, and Y. Vassilevski. 2013. Anderson Acceleration for Nonlinear Finite Volume Scheme for Advection-Diffusion Problems. SIAM Journal on Scientific Computing 35, 2 (2013), A1120–A1136.Google ScholarCross Ref
20. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A Local/Global Approach to Mesh Parameterization. Computer Graphics Forum 27, 5 (2008), 1495–1504. Google ScholarDigital Library
21. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast Simulation of Mass-spring Systems. ACM Trans. Graph. 32, 6 (2013), 214:1–214:7. Google ScholarDigital Library
22. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans. Graph. 36, 3 (2017), 23:1–23:16. Google ScholarDigital Library
23. Yang Liu, Helmut Pottmann, Johannes Wallner, Yong-Liang Yang, and Wenping Wang. 2006. Geometric Modeling with Conical Meshes and Developable Surfaces. ACM Trans. Graph. 25, 3 (2006), 681–689. Google ScholarDigital Library
24. Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, Dong-Ming Yan, Lin Lu, and Chenglei Yang. 2009. On Centroidal Voronoi Tessellation—Energy Smoothness and Fast Computation. ACM Trans. Graph. 28, 4 (2009), 101:1–101:17. Google ScholarDigital Library
25. Yang Liu, Weiwei Xu, Jun Wang, Lifeng Zhu, Baining Guo, Falai Chen, and Guoping Wang. 2011. General Planar Quadrilateral Mesh Design Using Conjugate Direction Field. ACM Trans. Graph. 30, 6 (2011), 140:1–140:10. Google ScholarDigital Library
26. Yurii Nesterov. 1983. A method of solving a convex programming problem with convergence rate O (1/k2). Soviet Mathematics Doklady 27 (1983), 372–376.Google Scholar
27. Jorge Nocedal and Stephen J. Wright. 2006. Numerical optimization (2nd ed.). Springer-Verlag New York.Google Scholar
28. C. W. Oosterlee and T. Washio. 2000. Krylov Subspace Acceleration of Nonlinear Multigrid with Application to Recirculating Flows. SIAM Journal on Scientific Computing 21, 5 (2000), 1670–1690. Google ScholarDigital Library
29. M. Overby, G. E. Brown, J. Li, and R. Narain. 2017. ADMM ⊇ Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints. IEEE Transactions on Visualization and Computer Graphics 23, 10 (2017), 2222–2234.Google ScholarDigital Library
30. Florian A. Potra and Hans Engler. 2013. A characterization of the behavior of the Anderson acceleration on linear problems. Linear Algebra Appl. 438, 3 (2013), 1002–1011.Google ScholarCross Ref
31. Phanisri P. Pratapa, Phanish Suryanarayana, and John E. Pask. 2016. Anderson acceleration of the Jacobi iterative method: An efficient alternative to Krylov methods for large, sparse linear systems. J. Comput. Phys. 306 (2016), 43–54. Google ScholarDigital Library
32. Péter Pulay. 1980. Convergence acceleration of iterative sequences. the case of SCF iteration. Chemical Physics Letters 73, 2 (1980), 393–398.Google ScholarCross Ref
33. P. Pulay. 1982. Improved SCF convergence acceleration. Journal of Computational Chemistry 3, 4 (1982), 556–560.Google ScholarCross Ref
34. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2 (2017), 16:1–16:16. Google ScholarDigital Library
35. Thorsten Rohwedder and Reinhold Schneider. 2011. Ananalysis for the DIIS acceleration method used in quantum chemistry calculations. Journal of Mathematical Chemistry 49, 9 (2011), 1889–1914.Google ScholarCross Ref
36. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric optimization via composite majorization. ACM Trans. Graph. 36, 4 (2017), 38:1–38:11. Google ScholarDigital Library
37. Eftychios Sifakis and Jernej Barbič. 2012. FEM Simulation of 3D Deformable Solids: A Practitioner’s Guide to Theory, Discretization and Model Reduction. In ACM SIGGRAPH 2012 Courses. 20:1–20:50. Google ScholarDigital Library
38. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4 (2015), 70:1–70:9. Google ScholarDigital Library
39. Olga Sorkine and Marc Alexa. 2007. As-Rigid-As-Possible Surface Modeling. In Proceedings of EUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing. 109–116. Google ScholarDigital Library
40. Olga Sorkine-Hornung and Michael Rabinovich. 2016. Least-Squares Rigid Motion Using SVD. (2016). Technical note.Google Scholar
41. H. De Sterck. 2012. A Nonlinear GMRES Optimization Algorithm for Canonical Tensor Decomposition. SIAM Journal on Scientific Computing 34, 3 (2012), A1351–A1379.Google ScholarCross Ref
42. 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).Google Scholar
43. Chengcheng Tang, Xiang Sun, Alexandra Gomes, Johannes Wallner, and Helmut Pottmann. 2014. Form-finding with Polyhedral Meshes Made Simple. ACM Trans. Graph. 33, 4 (2014), 70:1–70:9. Google ScholarDigital Library
44. Alex Toth, J. Austin Ellis, Tom Evans, Steven Hamilton, C. T. Kelley, Roger Pawlowski, and Stuart Slattery. 2017. Local Improvement Results for Anderson Acceleration with Inaccurate Function Evaluations. SIAM Journal on Scientific Computing 39, 5 (2017), S47–S65.Google ScholarCross Ref
45. Alex Toth and C. T. Kelley. 2015. Convergence Analysis for Anderson Acceleration. SIAM J. Numer. Anal. 53, 2 (2015), 805–819.Google ScholarCross Ref
46. Homer F. Walker and Peng Ni. 2011. Anderson Acceleration for Fixed-Point Iterations. SIAM J. Numer. Anal. 49, 4 (2011), 1715–1735. Google ScholarDigital Library
47. Huamin Wang. 2015. A chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Trans. Graph. 34, 6 (2015), 246:1–246:9. Google ScholarDigital Library
48. Huamin Wang and Yin Yang. 2016. Descent Methods for Elastic Body Simulation on the GPU. ACM Trans. Graph. 35, 6 (2016), 212:1–212:10. Google ScholarDigital Library
49. T. Washio and C. W. Oosterlee. 1997. Krylov subspace acceleration for nonlinear multigrid schemes. Electronic Transactions on Numerical Analysis 6, 271–290 (1997).Google Scholar
50. Jeffrey Willert, William T. Taitano, and Dana Knoll. 2014. Leveraging Anderson Acceleration for improved convergence of iterative solutions to transport systems. J. Comput. Phys. 273 (2014), 278–286. Google ScholarDigital Library
