A stiffly accurate integrator for elastodynamic problems

Abstract

We present a new integration algorithm for the accurate and efficient solution of stiff elastodynamic problems governed by the second-order ordinary differential equations of structural mechanics. Current methods have the shortcoming that their performance is highly dependent on the numerical stiffness of the underlying system that often leads to unrealistic behavior or a significant loss of efficiency. To overcome these limitations, we present a new integration method which is based on a mathematical reformulation of the underlying differential equations, an exponential treatment of the full nonlinear forcing operator as opposed to more standard partially implicit or exponential approaches, and the utilization of the concept of stiff accuracy which ensures that the efficiency of the simulations is significantly less sensitive to increased stiffness. As a consequence, we are able to tremendously accelerate the simulation of stiff systems compared to established integrators and significantly increase the overall accuracy. The advantageous behavior of this approach is demonstrated on a broad spectrum of complex examples like deformable bodies, textiles, bristles, and human hair. Our easily parallelizable integrator enables more complex and realistic models to be explored in visual computing without compromising efficiency.

References

1. Awad H. Al-Mohy and Nicholas J. Higham. 2011. Computing the Action of the Matrix Exponential, with an Application to Exponential Integrators. SIAM Journal on Scientific Computing 33 (2011), 488--511.
2. Walter E. Arnoldi. 1951. The Principle of Minimized Iteration in the Solution of the Matrix Eigenvalue Problem. Quarterly of Applied Mathematics 9 (1951), 17--29.
3. Uri M. Ascher, Steven J. Ruuth, and Brian T.R. Wetton. 1995. Implicit-explicit Methods for Time-dependent Partial Differential Equations. SIAM Journal on Numerical Analysis 32, 3 (1995), 797--823.
4. David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of SIGGRAPH 98. Annual Conference Series, 43--54.
5. Luca Bergamaschi, Marco Caliari, and Marco Vianello. 2004. The ReLPM Exponential Integrator for FE Discretizations of Advection-Diffusion Equations. International Conference on Computational Science 3039 (2004), 434--442.
6. Miklós Bergou, Max Wardetzky, Stephen Robinson, Basile Audoly, and Eitan Grinspun. 2008. Discrete Elastic Rods. ACM Transactions on Graphics 27, 3 (2008), 63:1--63:12.
7. Florence Bertails, Basile Audoly, Marie-Paule Cani, Bernard Querleux, Frédéric Leroy, and Jean-Luc Lévêque. 2006. Super-helices for Predicting the Dynamics of Natural Hair. ACM Transactions on Graphics 25, 3 (2006), 1180--1187.
8. Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust Treatment of Collisions, Contact and Friction for Cloth Animation. ACM Transactions on Graphics 21, 3 (2002), 594--603.
9. Simone Buchholz, Ludwig Gauckler, Volker Grimm, Marlis Hochbruck, and Tobias Jahnke. 2017. Closing the Gap between Trigonometric Integrators and Splitting Methods for Highly Oscillatory Differential Equations. SIAM Journal on Numerical Analysis (2017), 1--18.
10. John C. Butcher. 2008. Numerical Methods for Ordinary Differential Equations (2nd ed.). Wiley.
11. Marco Caliari, Peter Kandolf, Alexander Ostermann, and Stefan Rainer. 2016. The Leja Method Revisited: Backward Error Analysis for the Matrix Exponential. SIAM Journal on Scientific Computation 38, 3 (2016), 1639--1661.
12. John Certaine. 1960. The Solution of Ordinary Differential Equations with Large Time Constants. In Mathematical Methods for Digital Computers. Wiley, 128--132.
13. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A Simple Geometric Model for Elastic Deformations. ACM Transactions on Graphics 29, 4 (2010), 38:1--38:6.
14. G. Chen and D. L. Russell. 1982. A Mathematical Model for Linear Elastic Systems with Structural Damping. Quarterly of Applied Mathematics 39, 4 (1982), 433--454.
15. Ricardo Cortez. 2001. The Method of Regularized Stokeslets. SIAM Journal on Scientific Computing 23, 4 (2001), 1204--1225.
16. Ricardo Cortez, Lisa Fauci, Nathaniel Cowen, and Robert Dillon. 2004. Simulation of Swimming Organisms: Coupling Internal Mechanics with External Fluid Dynamics. Computing in Science and Engineering 6, 3 (2004), 38--45.
17. Peter Deuflhard. 1979. A Study of Extrapolation Methods based on Multistep Schemes without Parasitic Solutions. Journal of Applied Mathematics and Physics 30 (1979), 177--189.
18. Bernd Eberhardt, Olaf Etzmuß, and Michael Hauth. 2000. Implicit-Explicit Schemes for Fast Animation with Particle Systems. In Proceedings of the Eurographics Workshop on Computer Animation and Simulation. 137--151.
19. Lukas Einkemmer, Mayya Tokman, and John Loffeld. 2017. On the Performance of Exponential Integrators for Problems in Magnetohydrodynamics. Journal of Computational Physics 330 (2017), 550--565.
20. Björn Engquist, Athanasios Fokas, Ernst Hairer, and Arieh Iserles. 2009. Highly Oscillatory Problems. Cambridge University Press.
21. Walter Gautschi. 1961. Numerical Integration of Ordinary Differential Equations based on Trigonometric Polynomials. Numerische Mathematik 3 (1961), 381--397.
22. Tanja Göckler and Volker Grimm. 2013. Convergence Analysis of an Extended Krylov Subspace Method for the Approximation of Operator Functions in Exponential Integration. SIAM Journal on Numerical Analysis 51, 4 (2013), 2189--2213.
23. Rony Goldenthal, David Harmon, Raanan Fattal, Michel Bercovier, and Eitan Grinspun. 2014. Efficient Simulation of Inextensible Cloth. ACM Transactions on Graphics 26, 3 (2014).
24. Ernst Hairer and Christian Lubich. 1999. Long-time Energy Conservation of Numerical Methods for Oscillatory Differential Equations. SIAM Journal on Numerical Analysis 38 (1999), 414--441.
25. Ernst Hairer, Syvert P. Nørsett, and Gerhard Wanner. 2004. Solving Ordinary Differential Equations I: Nonstiff problems (2nd ed.). Springer.
26. Ernst Hairer and Gerhard Wanner. 2004. Solving Ordinary Differential Equations II: Stiff and Differential Algebraic Problems (2nd ed.). Springer.
27. Michael Hauth and Olaf Etzmuss. 2001. A High Performance Solver for the Animation of Deformable Objects using Advanced Numerical Methods. Computer Graphics Forum 20 (2001), 319--328.
28. Nicholas J. Higham. 2008. Functions of Matrices: Theory and Computation. SIAM.
29. Marlis Hochbruck and Alexander Ostermann. 2005. Explicit Exponential Runge-Kutta Methods for Semilinear Parabolic Problems. SIAM Journal on Numerical Analysis 43 (2005), 1069--1090.
30. Marlis Hochbruck and Alexander Ostermann. 2006. Exponential Integrators of Rosenbrock-type. Oberwolfach Reports 3 (2006), 1107--1110.
31. Marlis Hochbruck, Alexander Ostermann, and Julia Schweitzer. 2009. Exponential Rosenbrock-type Methods. SIAM Journal on Numerical Analysis 47 (2009), 786--803.
32. Aly-Khan Kassam and Lloyd N. Trefethen. 2005. Fourth-order Time Stepping for Stiff PDEs. SIAM Journal on Scientific Computing 26, 4 (2005), 1214--1233.
33. Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, and Eitan Grinspun. 2014. Adaptive Nonlinearity for Collisions in Complex Rod Assemblies. ACM Transactions on Graphics 33, 4 (2014), 123:1--123:12.
34. Stein Krogstad. 2005. Generalized Integrating Factor Methods for Stiff PDEs. Journal of Computational Physics 203 (2005), 72--88.
35. John D. Lawson. 1967. Generalized Runge-Kutta Processes for Stable Systems with Large Lipschitz Constants. SIAM Journal on Numerical Analysis 4, 3 (1967), 372--380.
36. Man Liu and Dadiv G. Gorman. 1995. Formulation of Rayleigh Damping and its Extensions. Computers & Structures 57, 2 (1995), 277--285.
37. John Loffeld and Mayya Tokman. 2013. Comparative Performance of Exponential, Implicit, and Explicit Integrators for Stiff Systems of ODEs. Journal of Computational and Applied Mathematics 241 (2013), 45--67.
38. Vu Thai Luan. 2017. Fourth-order Two-stage Explicit Exponential Integrators for Time-dependent PDEs. Applied Numerical Mathematics 112 (2017), 91--103.
39. Vu Thai Luan and Alexander Ostermann. 2013. Exponential B-series: The Stiff Case. SIAM Journal on Numerical Analysis 51 (2013), 3431--3445.
40. Vu Thai Luan and Alexander Ostermann. 2014a. Explicit Exponential Runge-Kutta Methods of High Order for Parabolic Problems. Journal of Computational and Applied Mathematics 256 (2014), 168--179.
41. Vu Thai Luan and Alexander Ostermann. 2014b. Exponential Rosenbrock Methods of Order Five - Construction, Analysis and Numerical Comparisons. Journal of Computational and Applied Mathematics 255 (2014), 417--431.
42. Vu Thai Luan and Alexander Ostermann. 2016. Parallel Exponential Rosenbrock Methods. Computers & Mathematics with Applications 71 (2016), 1137--1150.
43. Dominik L. Michels and Mathieu Desbrun. 2015. A Semi-analytical Approach to Molecular Dynamics. Journal of Computational Physics 303 (2015), 336--354.
44. Dominik L. Michels and J. Paul T. Mueller. 2016. Discrete Computational Mechanics for Stiff Phenomena. In SIGGRAPH ASIA 2016 Courses. 13:1--13:9.
45. Dominik L. Michels, J. Paul T. Mueller, and Gerrit A. Sobottka. 2015. A Physically Based Approach to the Accurate Simulation of Stiff Fibers and Stiff Fiber Meshes. Computers & Graphics 53B (2015), 136--146.
46. Dominik L. Michels, Gerrit A. Sobottka, and Andreas G. Weber. 2014. Exponential Integrators for Stiff Elastodynamic Problems. ACM Transactions on Graphics 33, 1 (2014), 7:1--7:20.
47. Cleve Moler and Charles Van Loan. 2003. Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-five Years Later. SIAM Review 45, 1 (2003), 3--49.
48. Matthias Müller, Julie Dorsey, Leonard McMillan, Robert Jagnow, and Barbara Cutler. 2002. Stable Real-Time Deformations. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 49--54.
49. Jitse Niesen and Will M. Wright. 2012. Algorithm 919: A Krylov Subspace Algorithm for Evaluating the Functions Appearing in Exponential Integrators. ACM Transactions on Mathematical Software 38, 3 (2012), 22:1--22:19.
50. Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (2nd ed.). Springer.
51. Dinesh K. Pai. 2002. STRANDS: Interactive Simulation of Thin Solids using Cosserat Models. Comp. Graph. Forum 21, 3 (2002), 347--352.
52. David A. Pope. 1963. An Exponential Method of Numerical Integration of Ordinary Differential Equations. Communications of the ACM 6, 8 (1963), 491--493.
53. Greg Rainwater and Mayya Tokman. 2014. A new Class of Split Exponential Propagation Iterative Methods of Runge-Kutta Type (sEPIRK) for Semilinear Systems of ODEs. Journal of Computational Physics 269 (2014), 40--60.
54. Greg Rainwater and Mayya Tokman. 2016a. Designing Efficient Exponential Integrators with EPIRK Framework. In AIP Conference Proceedings of ICNAAM.
55. Greg Rainwater and Mayya Tokman. 2016b. A new Approach to Constructing Efficient Stiffly Accurate EPIRK Methods. Journal of Computational Physics 323 (2016), 283--309.
56. Clarence R. Robbins. 2012. Chemical and Physical Behavior of Human Hair (5th ed.). Springer.
57. Andrew Selle, Michael Lentine, and Ronald Fedkiw. 2008. A Mass Spring Model for Hair Simulation. ACM Transactions on Graphics 27, 3 (2008), 64:1--64:11.
58. Hang Si. 2015. TetGen, a Delaunay-based Quality Tetrahedral Mesh Generator. ACM Transactions on Mathematical Software 41, 2 (2015), 11:1--11:36.
59. Stanford University. 2013. The Stanford 3D Scanning Repository. (2013).
60. Ari Stern and Mathieu Desbrun. 2006. Discrete Geometric Mechanics for Variational Time Integrators. In SIGGRAPH 2006 Courses. 75--80.
61. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. In Computer Graphics, Vol. 21. 205--214.
62. Mayya Tokman. 2006. Efficient Integration of Large Stiff Systems of ODEs with Exponential Propagation Iterative (EPI) Methods. Journal of Computational Physics 213 (2006), 748--776.
63. Mayya Tokman. 2011. A new Class of Exponential Propagation Iterative Methods of Runge-Kutta Type (EPIRK). Journal of Computational Physics 230 (2011), 8762--8778.
64. Mayya Tokman and Greg Rainwater. 2014. Four Classes of Exponential EPIRK Integrators. Oberwolfach Reports 14 (2014), 855--858.
65. Henk A. van der Vorst. 1987. An Iterative Solution Method for Solving f(A)x = b, using Krylov Subspace Information obtained for the Symmetric Positive Definite Matrix A. Journal of Computational and Applied Mathematics 18, 2 (1987), 249--263.
66. Gerald A. Wempner. 1969. Finite Elements, Finite Rotations and Small Strains of Flexible Shells. International Journal of Solids and Structures 5, 2 (1969), 117--153.

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Physics

• Mathematics of computing

  • Mathematical analysis

    • Differential equations

      • Ordinary differential equations

  • Mathematical software

    • Solvers