“Decomposed optimization time integrator for large-step elastodynamics” by Li, Gao, Langlois, Jiang and Kaufman
Conference:
Type:
Title:
- Decomposed optimization time integrator for large-step elastodynamics
Session/Category Title: Deformation and FEM
Presenter(s)/Author(s):
Abstract:
Simulation methods are rapidly advancing the accuracy, consistency and controllability of elastodynamic modeling and animation. Critical to these advances, we require efficient time step solvers that reliably solve all implicit time integration problems for elastica. While available time step solvers succeed admirably in some regimes, they become impractically slow, inaccurate, unstable, or even divergent in others — as we show here. Towards addressing these needs we present the Decomposed Optimization Time Integrator (DOT), a new domain-decomposed optimization method for solving the per time step, nonlinear problems of implicit numerical time integration. DOT is especially suitable for large time step simulations of deformable bodies with nonlinear materials and high-speed dynamics. It is efficient, automated, and robust at large, fixed-size time steps, thus ensuring stable, continued progress of high-quality simulation output. Across a broad range of extreme and mild deformation dynamics, using frame-rate size time steps with widely varying object shapes and mesh resolutions, we show that DOT always converges to user-set tolerances, generally well-exceeding and always close to the best wall-clock times across all previous nonlinear time step solvers, irrespective of the deformation applied.
References:
1. A. Abdelfattah, A. Haidar, S. Tomov, and J. Dongarra. 2017. Fast Cholesky factorization on GPUs for batch and native modes in MAGMA. J of Comp Sci 20 (2017).Google Scholar
2. U. M Ascher. 2008. Numerical methods for evolutionary differential equations. Google ScholarDigital Library
3. S. Bouaziz, S. Martin, T. Liu, L. Kavan, and M. Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Trans Graph 33, 4 (2014). Google ScholarDigital Library
4. S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning 3, 1 (2011). Google ScholarDigital Library
5. J. Brown and P. Brune. 2013. Low-rank quasi-Newton updates for robust Jacobian lagging in Newton-type methods. In Int Conf Math Comp Meth App Nucl Sci Eng.Google Scholar
6. J. C. Butcher. 2016. Numerical methods for ordinary differential equations.Google Scholar
7. I. Chao, U. Pinkall, P. Sanan, and P. Schröder. 2010. A simple geometric model for elastic deformations. ACM Trans Graph (SIGGRAPH) 29, 4 (2010). Google ScholarDigital Library
8. Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam. 2008. Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. ACM Trans on Mathematical Software (TOMS) 35, 3 (2008). Google ScholarDigital Library
9. P. Deufihard. 2011. Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms. Google ScholarDigital Library
10. V. Dolean, P. Jolivet, and F. Nataf. 2015. An introduction to domain decomposition methods: algorithms, theory and parallel implementation. Google ScholarDigital Library
11. T. Gast, C. Schroeder, A. Stomakhin, C. Jiang, and J. M Teran. 2015. Optimization integrator for large time steps. IEEE Trans Vis Comp Graph 21, 10 (2015). Google ScholarDigital Library
12. E. Hairer, C. Lubich, and G. Wanner. 2006. Geometric Numerical Integration.Google Scholar
13. E. Hairer, S. P Nørsett, and G. Wanner. 2008. Solving Ordinary Differential Equations I. Google ScholarDigital Library
14. E. Hairer and G. Wanner. 1996. Solving Ordinary Differential Equations II.Google Scholar
15. F. Hecht, Y.J. Lee, J. R. Shewchuk, and J. F. O’Brien. 2012. Updated Sparse Cholesky Factors for Corotational Elastodynamics. ACM Trans Graph 31, 5 (2012). Google ScholarDigital Library
16. J. Huang, X. Liu, H. Bao, B. Guo, and H. Shum. 2006. An efficient large deformation method using domain decomposition. Comp & Graph 30, 6 (2006). Google ScholarDigital Library
17. C. Kane, J. E Marsden, M. Ortiz, and M. West. 2000. Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. Int J for Numer Meth in Eng 49, 10 (2000).Google ScholarCross Ref
18. G. Karypis and V. Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J on Sci Comp 20 (1998). Google ScholarDigital Library
19. L. Kharevych, W. Yang, Y. Tong, E. Kanso, J. E Marsden, P. Schröder, and M. Desbrun. 2006. Geometric, variational integrators for computer animation. In Symp Comp Anim. Google ScholarDigital Library
20. T. Kim and D. L James. 2012. Physics-based character skinning using multidomain subspace deformations. IEEE Trans on visualization and Comp Graph 18, 8 (2012). Google ScholarDigital Library
21. H. Liu, N. Mitchell, M. Aanjaneya, and E. Sifakis. 2016. A scalable schur-complement fluids solver for heterogeneous compute platforms. ACM Trans Graph 35, 6 (2016). Google ScholarDigital Library
22. T. Liu, A. W. Bargteil, J. F. O’Brien, and L. Kavan. 2013. Fast Simulation of Mass-Spring Systems. ACM Trans Graph 32, 6 (2013). Proc of ACM SIGGRAPH Asia. Google ScholarDigital Library
23. T. Liu, S. Bouaziz, and L. Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans Graph 36, 4 (2017).Google Scholar
24. M. Macklin, M. Müller, and N. Chentanez. 2016. XPBD: position-based simulation of compliant constrained dynamics. In Proc of the 9th Int Conf on Motion in Games. Google ScholarDigital Library
25. S. Martin, B. Thomaszewski, E. Grinspun, and M. Gross. 2011. Example-based elastic materials. ACM Trans Graph (SIGGRAPH) 30, 4 (2011). Google ScholarDigital Library
26. A. McAdams, A. Selle, R. Tamstorf, J. Teran, and E. Sifakis. 2011. Computing the singular value decomposition of 3X 3 matrices with minimal branching and elementary floating point operations. University of Wisconsin Madison (2011).Google Scholar
27. M. Müller, B. Heidelberger, M. Hennix, and J. Ratcliff. 2007. Position based dynamics. J. Vis. Commun. Imag Represent. 18, 2 (2007). Google ScholarDigital Library
28. R. Narain, M. Overby, and G. E Brown. 2016. ADMM ⊇ projective dynamics: fast simulation of general constitutive models.. In Symp on Comp Anim. Google ScholarDigital Library
29. JW Neuberger. 1985. Steepest descent and differential equations. J of the Mathematical Society of Japan 37, 2 (1985).Google Scholar
30. J. Nocedal and S. Wright. 2006. Numerical Optimization.Google Scholar
31. M. Ortiz and L. Stainier. 1999. The variational formulation of viscoplastic constitutive updates. Comp Meth in App Mech and Eng 171, 3–4 (1999).Google ScholarCross Ref
32. M. Overby, G. E Brown, J. Li, and R. Narain. 2017. ADMM ⊇ Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints. IEEE Trans Vis Comp Graph 23, 10 (2017).Google ScholarDigital Library
33. N. Parikh and S. Boyd. 2012. Block splitting for distributed optimization.Google Scholar
34. A. Quarteroni, A. Valli, and P.M.A. Valli. 1999. Domain Decomposition Methods for Partial Differential Equations.Google Scholar
35. T. Schneider, Y. Hu, J. Dumas, X. Gao, D. Panozzo, and D. Zorin. 2018. Decoupling simulation accuracy from mesh quality. ACM Trans Graph (2018). Google ScholarDigital Library
36. S. Sellán, H. Y. Cheng, Y. Ma, M. Dembowski, and A. Jacobson. 2018. Solid Geometry Processing on Deconstructed Domains. CoRR (2018).Google Scholar
37. VE Shamanskii. 1967. A modification of Newton’s method. Ukrainian Mathematical J 19, 1 (1967).Google Scholar
38. A. Shtengel, R. Poranne, O. Sorkine-Hornung, S. Z. Kovalsky, and Y. Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Trans Graph 36, 4 (2017). Google ScholarDigital Library
39. B. Smith, F. De Goes, and T. Kim. 2018. Stable Neo-Hookean Flesh Simulation. ACM Trans Graph 37, 2 (2018). Google ScholarDigital Library
40. A. Stomakhin, R. Howes, C. Schroeder, and J. M Teran. 2012. Energetically consistent invertible elasticity. In Symp Comp Anim. Google ScholarDigital Library
41. J. Teran, E. Sifakis, G. Irving, and R. Fedkiw. 2005. Robust Quasistatic Finite Elements and Flesh Simulation. In Symp Comp Anim. Google ScholarDigital Library
42. C. Xiao-Chuan and D. Maksymilian. 1994. Domain Decomposition Methods for Monotone Nonlinear Elliptic Problems. In Contemporary Math.Google Scholar
43. Y. Zhu, R. Bridson, and D. M. Kaufman. 2018. Blended Cured Quasi-Newton for Distortion Optimization. ACM Trans. on Graph (SIGGRAPH) (2018). Google ScholarDigital Library
