“SANM: a symbolic asymptotic numerical solver with applications in mesh deformation” by Jia

Solving nonlinear systems is an important problem. Numerical continuation methods efficiently solve certain nonlinear systems. The Asymptotic Numerical Method (ANM) is a powerful continuation method that usually converges faster than Newtonian methods. ANM explores the landscape of the function by following a parameterized solution curve approximated with a high-order power series. Although ANM has successfully solved a few graphics and engineering problems, prior to our work, applying ANM to new problems required significant effort because the standard ANM assumes quadratic functions, while manually deriving the power series expansion for nonquadratic systems is a tedious and challenging task.This paper presents a novel solver, SANM, that applies ANM to solve symbolically represented nonlinear systems. SANM solves such systems in a fully automated manner. SANM also extends ANM to support many nonquadratic operators, including intricate ones such as singular value decomposition. Furthermore, SANM generalizes ANM to support the implicit homotopy form. Moreover, SANM achieves high computing performance via optimized system design and implementation.We deploy SANM to solve forward and inverse elastic force equilibrium problems and controlled mesh deformation problems with a few constitutive models. Our results show that SANM converges faster than Newtonian solvers, requires little programming effort for new problems, and delivers comparable or better performance than a hand-coded, specialized ANM solver. While we demonstrate on mesh deformation problems, SANM is generic and potentially applicable to many tasks.

1. Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016. Tensorflow: A system for large-scale machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16). 265–283.Google ScholarDigital Library
2. H Abichou, H Zahrouni, and M Potier-Ferry. 2002. Asymptotic numerical method for problems coupling several nonlinearities. Computer Methods in Applied Mechanics and Engineering 191, 51–52 (2002), 5795–5810.Google ScholarCross Ref
3. Eugene L Allgower and Kurt Georg. 2003. Introduction to numerical continuation methods. SIAM.Google Scholar
4. L Azrar, EH Boutyour, and M Potier-Ferry. 2002. Non-linear forced vibrations of plates by an asymptotic-numerical method. Journal of Sound and Vibration 252, 4 (2002), 657–674.Google ScholarCross Ref
5. L Azrar, B Cochelin, N Damil, and M Potier-Ferry. 1993. An asymptotic-numerical method to compute the postbuckling behaviour of elastic plates and shells. International journal for numerical methods in engineering 36, 8 (1993), 1251–1277.Google ScholarCross Ref
6. JL Basdevant. 1972. The Padé approximation and its physical applications. Fortschritte der Physik 20, 5 (1972), 283–331.Google ScholarCross Ref
7. Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. 2018. Automatic Differentiation in Machine Learning: a Survey. Journal of Machine Learning Research 18, 153 (2018), 1–43. http://jmlr.org/papers/v18/17-468.htmlGoogle ScholarDigital Library
8. Jan Bender, Matthias Müller, Miguel A Otaduy, Matthias Teschner, and Miles Macklin. 2014. A survey on position-based simulation methods in computer graphics. In Computer graphics forum, Vol. 33. Wiley Online Library, 228–251.Google Scholar
9. Javier Bonet and Richard D. Wood. 2008. Nonlinear Continuum Mechanics for Finite Element Analysis (2 ed.). Cambridge University Press. Google ScholarCross Ref
10. Joseph-Frédéric Bonnans, Jean Charles Gilbert, Claude Lemaréchal, and Claudia A Sagastizábal. 2006. Numerical optimization: theoretical and practical aspects. Springer Science & Business Media.Google Scholar
11. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: fusing constraint projections for fast simulation. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–11.Google ScholarDigital Library
12. EH Boutyour, H Zahrouni, M Potier-Ferry, and M Boudi. 2004. Bifurcation points and bifurcated branches by an asymptotic numerical method and Padé approximants. Internat. J. Numer Methods Engrg. 60, 12 (2004), 1987–2012.Google ScholarCross Ref
13. Richard P Brent. 2013. Algorithms for minimization without derivatives. Courier Corporation.Google Scholar
14. Richard P Brent and Hsiang T Kung. 1978. Fast algorithms for manipulating formal power series. Journal of the ACM (JACM) 25, 4 (1978), 581–595.Google ScholarDigital Library
15. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. ACM transactions on graphics (TOG) 29, 4 (2010), 1–6.Google Scholar
16. Isabelle Charpentier, Arnaud Lejeune, and Michel Potier-Ferry. 2008. The diamant approach for an efficient automatic differentiation of the asymptotic numerical method. In Advances in automatic differentiation. Springer, 139–149.Google Scholar
17. Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, et al. 2018. TVM: An automated end-to-end optimizing compiler for deep learning. In 13th USENIX Symposium on Operating Systems Design and Implementation OSDI 18). 578–594.Google Scholar
18. Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. 2016. Training deep nets with sublinear memory cost. arXiv preprint arXiv:1604.06174 (2016).Google Scholar
19. Xiang Chen, Changxi Zheng, Weiwei Xu, and Kun Zhou. 2014. An asymptotic numerical method for inverse elastic shape design. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–11.Google ScholarDigital Library
20. Min Gyu Choi and Hyeong-Seok Ko. 2005. Modal warping: Real-time simulation of large rotational deformation and manipulation. IEEE Transactions on Visualization and Computer Graphics 11, 1 (2005), 91–101.Google ScholarDigital Library
21. Bruno Cochelin.1994. A path-following technique via an asymptotic-numerical method. Computers & structures 53, 5 (1994), 1181–1192.Google Scholar
22. Bruno Cochelin, Noureddine Damil, and Michel Potier-Ferry. 1994a. Asymptotic-numerical methods and Padé approximants for non-linear elastic structures. International journal for numerical methods in engineerings 37, 7 (1994), 1187–1213.Google ScholarCross Ref
23. Bruno Cochelin, Noureddine Damil, and Michel Potier-Ferry. 1994b. The asymptotic-numerical method: an efficient perturbation technique for nonlinear structural mechanics. Revue européenne des éléments finis 3, 2 (1994), 281–297.Google Scholar
24. Noureddine Damil and Michel Potier-Ferry. 1990. A new method to compute perturbed bifurcations: application to the buckling of imperfect elastic structures. International Journal of Engineering Science 28, 9 (1990), 943–957.Google ScholarCross Ref
25. EM Daya and M Potier-Ferry. 2001. A numerical method for nonlinear eigenvalue problems application to vibrations of viscoelastic structures. Computers & Structures 79, 5 (2001), 533–541.Google ScholarCross Ref
26. Simon Duenser, Roi Poranne, Bernhard Thomaszewski, and Stelian Coros. 2020. Robo-Cut: hot-wire cutting with robot-controlled flexible rods. ACM Transactions on Graphics (TOG) 39, 4 (2020), 98–1.Google ScholarDigital Library
27. Ahmad Elhage-Hussein, Michel Potier-Ferry, and Noureddine Damil. 2000. A numerical continuation method based on Padé approximants. International Journal of Solids and Structures 37, 46–47 (2000), 6981–7001.Google ScholarCross Ref
28. Benjamin Gilles, Guillaume Bousquet, Francois Faure, and Dinesh K Pai. 2011. Frame-based elastic models. ACM transactions on graphics (TOG) 30, 2 (2011), 1–12.Google Scholar
29. Gene H Golub and TN Robertson. 1967. A generalized Bairstow algorithm. Commun. ACM 10, 6 (1967), 371–373.Google ScholarDigital Library
30. Andreas Griewank and Andrea Walther. 2008. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM.Google Scholar
31. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
32. Louis Guillot, Bruno Cochelin, and Christophe Vergez. 2019. A generic and efficient Taylor series-based continuation method using a quadratic recast of smooth nonlinear systems. International Journal for numerical methods in Engineering 119, 4 (2019), 261–280.Google ScholarCross Ref
33. M Hromčík and M Šebekt. 1999. New algorithm for polynomial matrix determinant based on FFT. In 1999 European Control Conference (ECC). IEEE, 4173–4177.Google ScholarCross Ref
34. Norman P. Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, Rick Boyle, Pierre-luc Cantin, Clifford Chao, Chris Clark, Jeremy Coriell, Mike Daley, Matt Dau, Jeffrey Dean, Ben Gelb, Tara Vazir Ghaemmaghami, Rajendra Gottipati, William Gulland, Robert Hagmann, C. Richard Ho, Doug Hogberg, John Hu, Robert Hundt, Dan Hurt, Julian Ibarz, Aaron Jaffey, Alek Jaworski, Alexander Kaplan, Harshit Khaitan, Daniel Killebrew, Andy Koch, Naveen Kumar, Steve Lacy, James Laudon, James Law, Diemthu Le, Chris Leary, Zhuyuan Liu, Kyle Lucke, Alan Lundin, Gordon MacKean, Adriana Maggiore, Maire Mahony, Kieran Miller, Rahul Nagarajan, Ravi Narayanaswami, Ray Ni, Kathy Nix, Thomas Norrie, Mark Omernick, Narayana Penukonda, Andy Phelps, Jonathan Ross, Matt Ross, Amir Salek, Emad Samadiani, Chris Severn, Gregory Sizikov, Matthew Snelham, Jed Souter, Dan Steinberg, Andy Swing, Mercedes Tan, Gregory Thorson, Bo Tian, Horia Toma, Erick Tuttle, Vijay Vasudevan, Richard Walter, Walter Wang, Eric Wilcox, and Doe Hyun Yoon. 2017. In-Datacenter Performance Analysis of a Tensor Processing Unit. In Proceedings of the 44th Annual International Symposium on Computer Architecture (Toronto, ON, Canada) (ISCA ’17). Association for Computing Machinery, New York, NY, USA, 1–12. Google ScholarDigital Library
35. Theodore Kim and David Eberle. 2020. Dynamic deformables: implementation and production practicalities. In ACM SIGGRAPH 2020 Courses. 1–182.Google ScholarDigital Library
36. Theodore Kim and Doug L James. 2009. Skipping steps in deformable simulation with online model reduction. In ACM SIGGRAPH Asia 2009 papers. 1–9.Google Scholar
37. Chris Lattner and Vikram Adve. 2004. LLVM: A compilation framework for lifelong program analysis & transformation. In International Symposium on Code Generation and Optimization, 2004. CGO 2004. IEEE, 75–86.Google ScholarCross Ref
38. Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. 2020. MLIR: A compiler infrastructure for the end of Moore’s law. arXiv preprint arXiv:2002.11054 (2020).Google Scholar
39. Arnaud Lazarus, JT Miller, and Pedro M Reis. 2013. Continuation of equilibria and stability of slender elastic rods using an asymptotic numerical method. Journal of the Mechanics and Physics of Solids 61, 8 (2013), 1712–1736.Google ScholarCross Ref
40. Arnaud Lejeune, Fabien Béchet, Hakim Boudaoud, Norman Mathieu, and Michel Potier-Ferry. 2012. Object-oriented design to automate a high order non-linear solver based on asymptotic numerical method. Advances in Engineering Software 48 (2012), 70–88.Google ScholarDigital Library
41. Hai-Jun Liao, Jin-Guo Liu, Lei Wang, and Tao Xiang. 2019. Differentiable programming tensor networks. Physical Review X 9, 3 (2019), 031041.Google Scholar
42. Alex Limpaecher, Nicolas Feltman, Adrien Treuille, and Michael Cohen. 2013. Real-time drawing assistance through crowdsourcing. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–8.Google ScholarDigital Library
43. A Najah, B Cochelin, N Damil, and M Potier-Ferry. 1998. A critical review of asymptotic numerical methods. Archives of Computational Methods in Engineering 5, 1 (1998), 31–50.Google ScholarCross Ref
44. Théodore Papadopoulo and Manolis IA Lourakis. 2000. Estimating the jacobian of the singular value decomposition: Theory and applications. In European Conference on Computer Vision. Springer, 554–570.Google ScholarCross Ref
45. Steven Roman. 1980. The formula of Fàa di Bruno. The American Mathematical Monthly 87, 10 (1980), 805–809.Google ScholarCross Ref
46. Matthias Seeger, Asmus Hetzel, Zhenwen Dai, Eric Meissner, and Neil D Lawrence. 2017. Auto-differentiating linear algebra. arXiv preprint arXiv:1710.08717 (2017).Google Scholar
47. 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.Google ScholarDigital Library
48. Eftychios Sifakis and Jernej Barbic. 2012. FEM simulation of 3D deformable solids: a practitioner’s guide to theory, discretization and model reduction. In Acm siggraph 2012 courses. 1–50.Google Scholar
49. Breannan Smith, Fernando De Goes, and Theodore Kim. 2019. Analytic Eigensystems for Isotropic Distortion Energies. ACM Transactions on Graphics (TOG) 38, 1 (2019), 1–15.Google ScholarDigital Library
50. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, Vol. 4. 109–116.Google ScholarDigital Library
51. Theano Development Team. 2016. Theano: A Python framework for fast computation of mathematical expressions. arXiv e-prints abs/1605.02688 (May 2016). http://arxiv.org/abs/1605.02688Google Scholar
52. Joshua Trzasko and Armando Manduca. 2008. Highly Undersampled Magnetic Resonance Image Reconstruction via Homotopic l0-Minimization. IEEE Transactions on Medical imaging 28, 1 (2008), 106–121.Google ScholarCross Ref
53. Nobuyuki Umetani, Danny M Kaufman, Takeo Igarashi, and Eitan Grinspun. 2011. Sensitive couture for interactive garment modeling and editing. ACM Trans. Graph. 30, 4 (2011), 90.Google ScholarDigital Library
54. KangKang Yin, Stelian Coros, Philippe Beaudoin, and Michiel van de Panne. 2008. Continuation methods for adapting simulated skills. In ACM SIGGRAPH 2008 papers. 1–7.Google Scholar
55. H Zahrouni, B Cochelin, and M Potier-Ferry. 1999. Computing finite rotations of shells by an asymptotic-numerical method. Computer methods in applied mechanics and engineering 175, 1–2 (1999), 71–85.Google Scholar