“Accelerated complex-step finite difference for expedient deformable simulation” by Luo, Xu, Shao, Xu and Yang
Conference:
Type(s):
Title:
- Accelerated complex-step finite difference for expedient deformable simulation
Session/Category Title: Accelerated Physics
Presenter(s)/Author(s):
Moderator(s):
Abstract:
In deformable simulation, an important computing task is to calculate the gradient and derivative of the strain energy function in order to infer the corresponding internal force and tangent stiffness matrix. The standard numerical routine is the finite difference method, which evaluates the target function multiple times under a small real-valued perturbation. Unfortunately, the subtractive cancellation prevents us from setting this perturbation sufficiently small, and the regular finite difference is doomed for computing problems requiring a high-accuracy derivative evaluation. In this paper, we graft a new finite difference scheme, namely the complex-step finite difference (CSFD), with physics-based animation. CSFD is based on the complex Taylor series expansion, which avoids subtractions in first-order derivative approximation. As a result, one can use a very small perturbation to calculate the numerical derivative that is as accurate as its analytic counterpart. We accelerate the original CSFD method so that it is also as efficient as the analytic derivative. This is achieved by discarding high-order error terms, decoupling real and imaginary calculations, replacing costly functions based on the theory of equivalent infinitesimal, and isolating the propagation of the perturbation in composite/nesting functions. CSFD can be further augmented with multicomplex Taylor expansion and Cauchy-Riemann formula to handle higher-order derivatives and tensor-valued functions. We demonstrate the accuracy, convenience, and efficiency of this new numerical routine in the context of deformable simulation – one can easily deploy a robust simulator for general hyperelastic materials, including user-crafted ones to cater specific needs in different applications. Higher-order derivatives of the energy can be readily computed to construct modal derivative bases for reduced real-time simulation. Inverse simulation problems can also be conveniently solved using gradient/Hessian-based optimization procedures.
References:
1. Mark J Ablowitz and Athanassios S Fokas. 2003. Complex variables: introduction and applications. Cambridge University Press.Google Scholar
2. Rafael Abreu, Zeming Su, Jochen Kamm, and Jinghuai Gao. 2018. On the accuracy of the Complex-Step-Finite-Difference method. J. Comput. Appl. Math. 340 (2018), 390–403.Google ScholarCross Ref
3. Lars V Ahlfors. 1973. Complex Analysis. 1979. (1973).Google Scholar
4. W Kyle Anderson, James C Newman, David L Whitfield, and Eric J Nielsen. 2001. Sensitivity analysis for Navier-Stokes equations on unstructured meshes using complex variables. AIAA journal 39, 1 (2001), 56–63.Google ScholarCross Ref
5. RL Bagley. 2006. On Fourier differentiation – a numerical tool for implicit functions. International Journal of Applied Mathematics 19, 3 (2006), 255.Google Scholar
6. David Baraff. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In ACM SIGGRAPH Computer Graphics, Vol. 23. ACM, 223–232.Google ScholarDigital Library
7. David Baraff. 1991. Coping with friction for non-penetrating rigid body simulation. ACM SIGGRAPH computer graphics 25, 4 (1991), 31–41.Google Scholar
8. David Baraff and Andrew Witkin. 1998. Large steps in cloth simulation. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques. ACM, 43–54.Google ScholarDigital Library
9. Jernej Barbič and Doug L James. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. In ACM transactions on graphics (TOG), Vol. 24. ACM, 982–990.Google Scholar
10. Jernej Barbič, Funshing Sin, and Eitan Grinspun. 2012. Interactive editing of deformable simulations. ACM Transactions on Graphics (TOG) 31, 4 (2012), 70.Google ScholarDigital Library
11. Jernej Barbič, Fun Shing Sin, and Daniel Schroeder. 2012. Vega FEM Library. (2012).Google Scholar
12. Atilim Gunes Baydin and Barak A Pearlmutter. 2014. Automatic differentiation of algorithms for machine learning. arXiv preprint arXiv:1404.7456 (2014).Google Scholar
13. Bradley M Bell. 2012. CppAD: a package for C++ algorithmic differentiation. Computational Infrastructure for Operations Research 57 (2012), 10.Google Scholar
14. Michael Betancourt. 2018. A Geometric Theory of Higher-Order Automatic Differentiation. arXiv preprint arXiv:1812.11592 (2018).Google Scholar
15. Javier Bonet and Richard D Wood. 1997. Nonlinear continuum mechanics for finite element analysis. Cambridge university press.Google Scholar
16. Patrick Brezillon, Jean-François Staub, Anne-Marie Perault-Staub, and Gérard Milhaud. 1981. Numerical estimation of the first order derivative: approximate evaluation of an optimal step. Computers & Mathematics with Applications 7, 4 (1981), 333–347.Google ScholarCross Ref
17. Robert Bridson. 2015. Fluid simulation for computer graphics. AK Peters/CRC Press.Google Scholar
18. N Butuk and J-P Pemba. 2003. computing CHEMKIN sensitivities using complex variables. Journal of engineering for gas turbines and power 125, 3 (2003), 854–858.Google ScholarCross Ref
19. Steve Capell, Seth Green, Brian Curless, Tom Duchamp, and Zoran Popović. 2002. Interactive skeleton-driven dynamic deformations. In ACM transactions on graphics (TOG), Vol. 21. ACM, 586–593.Google Scholar
20. 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), 95.Google ScholarDigital Library
21. Jeffrey Fike and Juan Alonso. 2011. The development of hyper-dual numbers for exact second-derivative calculations. In 49th AIAA Aerospace Sciences Meeting including the New Horizons Forum and Aerospace Exposition. 886.Google ScholarCross Ref
22. Jeffrey Alan Fike. 2013. Multi-objective optimization using hyper-dual numbers. Ph.D. Dissertation. Stanford university.Google Scholar
23. N Fleury, M Rausch Detraubenberg, and RM Yamaleev. 1993. Commutative extended complex numbers and connected trigonometry. Journal of mathematical analysis and applications 180, 2 (1993), 431–457.Google ScholarCross Ref
24. Rony Goldenthal, David Harmon, Raanan Fattal, Michel Bercovier, and Eitan Grinspun. 2007. Efficient simulation of inextensible cloth. In ACM Transactions on Graphics (TOG), Vol. 26. ACM, 49.Google ScholarDigital Library
25. Andreas Griewank, David Juedes, and Jean Utke. 1996. Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++. ACM Transactions on Mathematical Software (TOMS) 22, 2 (1996), 131–167.Google ScholarDigital Library
26. Andreas Griewank and Andrea Walther. 2008. Evaluating derivatives: principles and techniques of algorithmic differentiation. Vol. 105. Siam.Google Scholar
27. Eitan Grinspun, Anil N Hirani, Mathieu Desbrun, and Peter Schröder. 2003. Discrete shells. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation. Eurographics Association, 62–67.Google ScholarDigital Library
28. Gael Guennebaud, Benoit Jacob, et al. 2014. Eigen: a c++ linear algebra library. URL http://eigen.tuxfamily.org, Accessed 22 (2014).Google Scholar
29. Brian Guenter. 2007. Efficient symbolic differentiation for graphics applications. In ACM Transactions on Graphics (TOG), Vol. 26. ACM, 108.Google ScholarDigital Library
30. Fabian Hahn, Sebastian Martin, Bernhard Thomaszewski, Robert Sumner, Stelian Coros, and Markus Gross. 2012. Rig-space physics. ACM transactions on graphics (TOG) 31, 4 (2012), 72.Google Scholar
31. Fabian Hahn, Bernhard Thomaszewski, Stelian Coros, Robert W Sumner, and Markus Gross. 2013. Efficient simulation of secondary motion in rig-space. In Proceedings of the 12th ACM SIGGRAPH/eurographics symposium on computer animation. ACM, 165–171.Google ScholarDigital Library
32. Robert Hecht-Nielsen. 1992. Theory of the backpropagation neural network. In Neural networks for perception. Elsevier, 65–93.Google ScholarDigital Library
33. Robin J Hogan. 2014. Fast reverse-mode automatic differentiation using expression templates in C++. ACM Transactions on Mathematical Software (TOMS) 40, 4 (2014), 26.Google ScholarDigital Library
34. IEEE. 1985. IEEE standard for binary floating-point arithmetic. Institute of Electrical and Electronic Engineers.Google Scholar
35. Geoffrey Irving, Joseph Teran, and Ronald Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation. Eurographics Association, 131–140.Google ScholarDigital Library
36. Sanghaun Kim, Junghyun Ryu, and Maenghyo Cho. 2011. Numerically generated tangent stiffness matrices using the complex variable derivative method for nonlinear structural analysis. Computer Methods in Applied Mechanics and Engineering 200, 1–4 (2011), 403–413.Google ScholarCross Ref
37. Yuki Koyama, Kenshi Takayama, Nobuyuki Umetani, and Takeo Igarashi. 2012. Real-time example-based elastic deformation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Eurographics Association, 19–24.Google Scholar
38. Edna E Kramer. 1930. Polygenic functions of the dual variable w= u+ jv. American Journal of Mathematics 52, 2 (1930), 370–376.Google ScholarCross Ref
39. K-L Lai and JL Crassidis. 2008. Extensions of the first and second complex-step derivative approximations. J. Comput. Appl. Math. 219, 1 (2008), 276–293.Google ScholarDigital Library
40. Gregory Lantoine, Ryan P Russell, and Thierry Dargent. 2012. Using multicomplex variables for automatic computation of high-order derivatives. ACM Transactions on Mathematical Software (TOMS) 38, 3 (2012), 16.Google ScholarDigital Library
41. Sonia Lebofsky. 2013. Numerically Generated Tangent Stiffness Matrices for Geometrically Non-Linear Structures. Ph.D. Dissertation.Google Scholar
42. Abraham Lee. 2013. ad: Fast, transparent first- and second-order automatic differentiation. (2013). http://pythonhosted.org/adGoogle Scholar
43. Tiantian Liu, Adam W Bargteil, James F O’Brien, and Ladislav Kavan. 2013. Fast simulation of mass-spring systems. ACM Transactions on Graphics (TOG) 32, 6 (2013), 214.Google ScholarDigital Library
44. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-newton methods for real-time simulation of hyperelastic materials. ACM Transactions on Graphics (TOG) 36, 4 (2017), 116a.Google ScholarDigital Library
45. JN Lyness. 1968. Differentiation formulas for analytic functions. Math. Comp. (1968), 352–362.Google Scholar
46. James N Lyness. 1967. Numerical algorithms based on the theory of complex variable. In Proceedings of the 1967 22nd national conference. ACM, 125–133.Google ScholarDigital Library
47. V Maple. 1994. Waterloo maple software. University of Waterloo, Version 5 (1994).Google Scholar
48. Charles C Margossian. 2018. A Review of automatic differentiation and its efficient implementation. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery (2018), e1305.Google Scholar
49. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based elastic materials. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 72.Google ScholarDigital Library
50. Joaquim RRA Martins, Peter Sturdza, and Juan J Alonso. 2003. The complex-step derivative approximation. ACM Transactions on Mathematical Software (TOMS) 29, 3 (2003), 245–262.Google ScholarDigital Library
51. Don Mitchell and Pat Hanrahan. 1992. Illumination from curved reflectors. In ACM SIGGRAPH Computer Graphics, Vol. 26. ACM, 283–291.Google ScholarDigital Library
52. Arturo Montoya, Randal Fielder, Armando Gomez-Farias, and Harry Millwater. 2014. Finite-element sensitivity for plasticity using complex variable methods. Journal of Engineering Mechanics 141, 2 (2014), 04014118.Google ScholarCross Ref
53. HM Nasir. 2013. A new class of multicomplex algebra with applications. Mathematical Sciences International Research Journal 2, 2 (2013), 163–168.Google Scholar
54. Richard D Neidinger. 2010. Introduction to automatic differentiation and MATLAB object-oriented programming. SIAM review 52, 3 (2010), 545–563.Google Scholar
55. Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer Science & Business Media.Google Scholar
56. Alex Pentland and John Williams. 1989. Good vibrations: Modal dynamics for graphics and animation. Vol. 23. ACM.Google Scholar
57. Agustí Pérez-Foguet, Antonio Rodríguez-Ferran, and Antonio Huerta. 2000. Numerical differentiation for local and global tangent operators in computational plasticity. Computer Methods in Applied Mechanics and Engineering 189, 1 (2000), 277–296.Google ScholarCross Ref
58. Griffith Baley Price. 1991. An introduction to multicomplex spaces and functions. M. Dekker.Google Scholar
59. Louis B Rall. 1981. Automatic differentiation: Techniques and applications. (1981).Google Scholar
60. Michael Renardy and Robert C Rogers. 2006. An introduction to partial differential equations. Vol. 13. Springer Science & Business Media.Google Scholar
61. Boris Schäling. 2011. The boost C++ libraries. Boris Schäling.Google Scholar
62. Adriana Schulz, Jie Xu, Bo Zhu, Changxi Zheng, Eitan Grinspun, and Wojciech Matusik. 2017. Interactive design space exploration and optimization for cad models. ACM Transactions on Graphics (TOG) 36, 4 (2017), 157.Google ScholarDigital Library
63. Ken Shoemake. 1985. Animating rotation with quaternion curves. In ACM SIGGRAPH computer graphics, Vol. 19. ACM, 245–254.Google Scholar
64. 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. ACM, 20.Google ScholarDigital Library
65. Breannan Smith, Fernando De Goes, and Theodore Kim. 2018. Stable Neo-Hookean Flesh Simulation. ACM Transactions on Graphics (TOG) 37, 2 (2018), 12.Google ScholarDigital Library
66. William Squire and George Trapp. 1998. Using complex variables to estimate derivatives of real functions. SIAM review 40, 1 (1998), 110–112.Google Scholar
67. Ari Stern and Mathieu Desbrun. 2006. Discrete geometric mechanics for variational time integrators. In ACM SIGGRAPH 2006 Courses. ACM, 75–80.Google ScholarDigital Library
68. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models. ACM Siggraph Computer Graphics 21, 4 (1987), 205–214.Google ScholarDigital Library
69. Christoph W Ueberhuber. 2012. Numerical computation 1: methods, software, and analysis. Springer Science & Business Media.Google Scholar
70. Andrew Voorhees, Harry Millwater, and Ronald Bagley. 2011. Complex variable methods for shape sensitivity of finite element models. Finite elements in analysis and design 47, 10 (2011), 1146–1156.Google Scholar
71. Huamin Wang and Yin Yang. 2016. Descent methods for elastic body simulation on the GPU. ACM Transactions on Graphics (TOG) 35, 6 (2016), 212.Google ScholarDigital Library
72. Andrew Witkin. 1997. Physically Based Modeling: Principles and Practice Particle System Dynamics. SIGGRAPH Course notes (1997).Google Scholar
73. Stephen Wolfram et al. 1996. Mathematica. Cambridge university press Cambridge.Google Scholar
74. Hongyi Xu, Funshing Sin, Yufeng Zhu, and Jernej Barbič. 2015. Nonlinear material design using principal stretches. ACM Transactions on Graphics (TOG) 34, 4 (2015), 75.Google ScholarDigital Library
75. Guowei Yan, Wei Li, Ruigang Yang, and Huamin Wang. 2018. Inexact descent methods for elastic parameter optimization. In SIGGRAPH Asia 2018 Technical Papers. ACM, 253.Google Scholar
76. Yin Yang, Dingzeyu Li, Weiwei Xu, Yuan Tian, and Changxi Zheng. 2015. Expediting precomputation for reduced deformable simulation. ACM Transactions on graphics (TOG) 34, 6 (2015).Google Scholar
