“A stiffly accurate integrator for elastodynamic problems”
Conference:
Type:
Title:
- A stiffly accurate integrator for elastodynamic problems
Session/Category Title: Sound & Elastics
Presenter(s)/Author(s):
Moderator(s):
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. Google ScholarDigital Library
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. Google ScholarCross Ref
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. Google ScholarDigital Library
4. David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of SIGGRAPH 98. Annual Conference Series, 43–54. Google ScholarDigital Library
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.Google Scholar
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.Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
10. John C. Butcher. 2008. Numerical Methods for Ordinary Differential Equations (2nd ed.). Wiley. Google ScholarCross Ref
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. Google ScholarCross Ref
12. John Certaine. 1960. The Solution of Ordinary Differential Equations with Large Time Constants. In Mathematical Methods for Digital Computers. Wiley, 128–132.Google Scholar
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.Google ScholarDigital Library
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. Google ScholarCross Ref
15. Ricardo Cortez. 2001. The Method of Regularized Stokeslets. SIAM Journal on Scientific Computing 23, 4 (2001), 1204–1225. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarCross Ref
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. Google ScholarCross Ref
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. Google ScholarDigital Library
20. Björn Engquist, Athanasios Fokas, Ernst Hairer, and Arieh Iserles. 2009. Highly Oscillatory Problems. Cambridge University Press. Google ScholarCross Ref
21. Walter Gautschi. 1961. Numerical Integration of Ordinary Differential Equations based on Trigonometric Polynomials. Numerische Mathematik 3 (1961), 381–397. Google ScholarDigital Library
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. Google ScholarCross Ref
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).Google Scholar
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. Google ScholarDigital Library
25. Ernst Hairer, Syvert P. Nørsett, and Gerhard Wanner. 2004. Solving Ordinary Differential Equations I: Nonstiff problems (2nd ed.). Springer.Google Scholar
26. Ernst Hairer and Gerhard Wanner. 2004. Solving Ordinary Differential Equations II: Stiff and Differential Algebraic Problems (2nd ed.). Springer.Google Scholar
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. Google ScholarCross Ref
28. Nicholas J. Higham. 2008. Functions of Matrices: Theory and Computation. SIAM. Google ScholarCross Ref
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. Google ScholarDigital Library
30. Marlis Hochbruck and Alexander Ostermann. 2006. Exponential Integrators of Rosenbrock-type. Oberwolfach Reports 3 (2006), 1107–1110.Google Scholar
31. Marlis Hochbruck, Alexander Ostermann, and Julia Schweitzer. 2009. Exponential Rosenbrock-type Methods. SIAM Journal on Numerical Analysis 47 (2009), 786–803. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google ScholarDigital Library
34. Stein Krogstad. 2005. Generalized Integrating Factor Methods for Stiff PDEs. Journal of Computational Physics 203 (2005), 72–88. Google ScholarDigital Library
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. Google ScholarCross Ref
36. Man Liu and Dadiv G. Gorman. 1995. Formulation of Rayleigh Damping and its Extensions. Computers & Structures 57, 2 (1995), 277–285. Google ScholarCross Ref
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. Google ScholarDigital Library
38. Vu Thai Luan. 2017. Fourth-order Two-stage Explicit Exponential Integrators for Time-dependent PDEs. Applied Numerical Mathematics 112 (2017), 91–103. Google ScholarCross Ref
39. Vu Thai Luan and Alexander Ostermann. 2013. Exponential B-series: The Stiff Case. SIAM Journal on Numerical Analysis 51 (2013), 3431–3445. Google ScholarCross Ref
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. Google ScholarDigital Library
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. Google ScholarDigital Library
42. Vu Thai Luan and Alexander Ostermann. 2016. Parallel Exponential Rosenbrock Methods. Computers & Mathematics with Applications 71 (2016), 1137–1150. Google ScholarDigital Library
43. Dominik L. Michels and Mathieu Desbrun. 2015. A Semi-analytical Approach to Molecular Dynamics. Journal of Computational Physics 303 (2015), 336–354. Google ScholarDigital Library
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.Google Scholar
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. Google ScholarDigital Library
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.Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google ScholarDigital Library
50. Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (2nd ed.). Springer.Google Scholar
51. Dinesh K. Pai. 2002. STRANDS: Interactive Simulation of Thin Solids using Cosserat Models. Comp. Graph. Forum 21, 3 (2002), 347–352.Google ScholarCross Ref
52. David A. Pope. 1963. An Exponential Method of Numerical Integration of Ordinary Differential Equations. Communications of the ACM 6, 8 (1963), 491–493. Google ScholarDigital Library
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. Google ScholarCross Ref
54. Greg Rainwater and Mayya Tokman. 2016a. Designing Efficient Exponential Integrators with EPIRK Framework. In AIP Conference Proceedings of ICNAAM.Google Scholar
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. Google ScholarDigital Library
56. Clarence R. Robbins. 2012. Chemical and Physical Behavior of Human Hair (5th ed.). Springer. Google ScholarCross Ref
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.Google ScholarDigital Library
58. Hang Si. 2015. TetGen, a Delaunay-based Quality Tetrahedral Mesh Generator. ACM Transactions on Mathematical Software 41, 2 (2015), 11:1–11:36.Google ScholarDigital Library
59. Stanford University. 2013. The Stanford 3D Scanning Repository. (2013).Google Scholar
60. Ari Stern and Mathieu Desbrun. 2006. Discrete Geometric Mechanics for Variational Time Integrators. In SIGGRAPH 2006 Courses. 75–80. Google ScholarDigital Library
61. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. In Computer Graphics, Vol. 21. 205–214. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
64. Mayya Tokman and Greg Rainwater. 2014. Four Classes of Exponential EPIRK Integrators. Oberwolfach Reports 14 (2014), 855–858.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarCross Ref
