research-article

A stiffly accurate integrator for elastodynamic problems

Authors:

Dominik L. Michels,

Mayya TokmanAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 36, Issue 4

Article No.: 116, Pages 1 - 14

https://doi.org/10.1145/3072959.3073706

Published: 20 July 2017 Publication History

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.

Digital 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.

[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.

Digital Library

[4]

David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of SIGGRAPH 98. Annual Conference Series, 43--54.

Digital 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.

[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.

Digital 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.

Digital 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.

Digital 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.

[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.

Digital 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.

[15]

Ricardo Cortez. 2001. The Method of Regularized Stokeslets. SIAM Journal on Scientific Computing 23, 4 (2001), 1204--1225.

Digital 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.

Digital 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.

[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.

Digital Library

[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.

Digital 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.

[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.

Digital Library

[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.

Digital Library

[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.

Digital 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.

Digital 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.

Digital Library

[34]

Stein Krogstad. 2005. Generalized Integrating Factor Methods for Stiff PDEs. Journal of Computational Physics 203 (2005), 72--88.

Digital 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.

[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.

Digital Library

[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.

Digital 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.

Digital Library

[42]

Vu Thai Luan and Alexander Ostermann. 2016. Parallel Exponential Rosenbrock Methods. Computers & Mathematics with Applications 71 (2016), 1137--1150.

Digital Library

[43]

Dominik L. Michels and Mathieu Desbrun. 2015. A Semi-analytical Approach to Molecular Dynamics. Journal of Computational Physics 303 (2015), 336--354.

Digital 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.

[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.

Digital 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.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[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.

Digital 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.

[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.

Digital Library

[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.

Digital 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.

Digital Library

[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.

Digital Library

[61]

Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. In Computer Graphics, Vol. 21. 205--214.

Digital 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.

Digital 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.

Digital Library

[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.

Digital 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.

Cited By

Deka PMoriggl AEinkemmer L(2025)LeXInt: GPU-accelerated exponential integrators packageSoftwareX10.1016/j.softx.2024.10194929(101949)Online publication date: Feb-2025
https://doi.org/10.1016/j.softx.2024.101949
Rist FWang ZPellis DPalma MLiu DGrinspun EMichels D(2024)A Flexible Mold for Facade Panel FabricationACM Transactions on Graphics10.1145/368790643:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687906
Luan VHoang NEhigie J(2024)Efficient exponential methods for genetic regulatory systemsJournal of Computational and Applied Mathematics10.1016/j.cam.2023.115424436(115424)Online publication date: Jan-2024
https://doi.org/10.1016/j.cam.2023.115424
Show More Cited By

Index Terms

A stiffly accurate integrator for elastodynamic problems
1. Applied computing
  1. Physical sciences and engineering
    1. Physics
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Ordinary differential equations
  2. Mathematical software
    1. Solvers

Recommendations

On the construction of stiffly accurate and B-stable Runge-Kutta methods
Abstract
In the solution of stiff ODEs and especially DAEs it is desirable that the method used is stiffly accurate and B-stable. In this paper guidelines for the construction of Runge-Kutta methods with these properties are presented.
Two classes of implicit-explicit multistep methods for nonlinear stiff initial-value problems

The initial value problems of nonlinear ordinary differential equations which contain stiff and nonstiff terms often arise from many applications. In order to reduce the computation cost, implicit-explicit (IMEX) methods are often applied to these ...
Semi-analytical Time Differencing Methods for Stiff Problems

A semi-analytical method is developed based on conventional integrating factor (IF) and exponential time differencing (ETD) schemes for stiff problems. The latter means that there exists a thin layer with a large variation in their solutions. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 36, Issue 4

August 2017

2155 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3072959

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2017

Published in TOG Volume 36, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
693
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)6

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deka PMoriggl AEinkemmer L(2025)LeXInt: GPU-accelerated exponential integrators packageSoftwareX10.1016/j.softx.2024.10194929(101949)Online publication date: Feb-2025
https://doi.org/10.1016/j.softx.2024.101949
Rist FWang ZPellis DPalma MLiu DGrinspun EMichels D(2024)A Flexible Mold for Facade Panel FabricationACM Transactions on Graphics10.1145/368790643:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687906
Luan VHoang NEhigie J(2024)Efficient exponential methods for genetic regulatory systemsJournal of Computational and Applied Mathematics10.1016/j.cam.2023.115424436(115424)Online publication date: Jan-2024
https://doi.org/10.1016/j.cam.2023.115424
Ji YXing Y(2023)Highly Accurate and Efficient Time Integration Methods with Unconditional Stability and Flexible Numerical DissipationMathematics10.3390/math1103059311:3(593)Online publication date: 23-Jan-2023
https://doi.org/10.3390/math11030593
Deka PEinkemmer LTokman M(2023)LeXInt: Package for exponential integrators employing Leja interpolationSoftwareX10.1016/j.softx.2022.10130221(101302)Online publication date: Feb-2023
https://doi.org/10.1016/j.softx.2022.101302
Cetinaslan O(2023)ESBD: Exponential Strain-based Dynamics using XPBD algorithmComputers & Graphics10.1016/j.cag.2023.09.014116(500-512)Online publication date: Nov-2023
https://doi.org/10.1016/j.cag.2023.09.014
Ascher ULarionov ESheen SPai D(2022)Simulating deformable objects for computer animation: A numerical perspectiveJournal of Computational Dynamics10.3934/jcd.20210219:2(47)Online publication date: 2022
https://doi.org/10.3934/jcd.2021021
Luan VMichels D(2022)Efficient exponential time integration for simulating nonlinear coupled oscillatorsJournal of Computational and Applied Mathematics10.1016/j.cam.2021.113429391:COnline publication date: 23-Apr-2022
https://dl.acm.org/doi/10.1016/j.cam.2021.113429
Kee MUm KJeong WHan J(2021)Constrained projective dynamicsACM Transactions on Graphics10.1145/3450626.345987840:4(1-12)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459878
Buvoli T(2021)Exponential Polynomial Block MethodsSIAM Journal on Scientific Computing10.1137/20M132134643:3(A1692-A1722)Online publication date: 13-May-2021
https://doi.org/10.1137/20M1321346
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents