“Decomposed optimization time integrator for large-step elastodynamics” by Li, Gao, Langlois, Jiang and Kaufman

  • ©Minchen Li, Ming Gao, Timothy R. Langlois, Chenfanfu Jiang, and Danny M. Kaufman



Session Title:

    Deformation and FEM


    Decomposed optimization time integrator for large-step elastodynamics



    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.


    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

ACM Digital Library Publication:

Overview Page: