“Exponential Integrators for Stiff Elastodynamic Problems” by Michels, Sobottka and Weber

  • ©Dominik L. Michels, Gerrit Sobottka, and Andreas Weber

Conference:


Type:


Title:

    Exponential Integrators for Stiff Elastodynamic Problems

Session/Category Title: Stretching & Flowing

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We investigate the application of exponential integrators to stiff elastodynamic problems governed by second-order differential equations. Classical explicit numerical integration schemes have the shortcoming that the stepsizes are limited by the highest frequency that occurs within the solution spectrum of the governing equations, while implicit methods suffer from an inevitable and mostly uncontrollable artificial viscosity that often leads to a nonphysical behavior. In order to overcome these specific detriments, we devise an appropriate class of exponential integrators that solve the stiff part of the governing equations of motion by employing a closed-form solution. As a consequence, we are able to handle up to three orders of magnitude larger time-steps as with conventional implicit integrators and at the same time achieve a tremendous increase in the overall long-term stability due to a strict energy conservation. The advantageous behavior of our approach is demonstrated on a broad spectrum of complex deformable models like fibers, textiles, and solids, including collision response, friction, and damping.

References:


    1. Fabian Aiteanu, Patrick Degener, and Reinhard Klein. 2010. Efficient non-linear editing of large point clouds. In Proceedings of the International Conference on Computer Graphics, Visualization and Computer Vision (WSCG’10).
    2. Hans C. Andersen. 1983. A velocity version of the shake algorithm for molecular dynamics calculations. J. Comput. Phys. 52, 24–34.
    3. Stuart S. Antman. 1995. Nonlinear problems of elasticity. Appl. Math. Sci. 107.
    4. W. E. Arnoldi. 1951. The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quart. Appl. Math. 9, 17–29.
    5. David Baraff and Andrew Witkin. 1998. Large steps in cloth simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’98). ACM Press, New York, 43–54.
    6. T. Belytschko and B. Hsieh. 1979. Application of higher order corotational stretch theories to nonlinear finite element analysis. Comput. Struct. 10, 175–182.
    7. M. Bergou, M. Wardetzky, S. Robinson, B. Audoly, and E. Grinspun. 2008. Discrete elastic rods. In Proceedings of the Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’08). ACM Press, New York, 1–12.
    8. David Brydon, John Pearson, and Michael Marder. 1998. Solving stiff differential equations with the method of patches. J. Comput. Phys. 144, 280–298.
    9. J. Certaine. 1960. The solution of ordinary differential equations with large time constants. In Mathematical Methods for Digital Computers, Wiley, New York, 128–132.
    10. C. F. Curtiss and J. O. Hirschfelder. 1952. Integration of stiff equations. Proc. Nat. Acad. Sci. Unit. Stat. Amer. 38, 3, 235–243.
    11. P. Deuflhard. 1979. A study of extrapolation methods based on multi-step schemes without parasititc solutions. J. App. Math. Phys. 30, 177–189.
    12. Bernd Eberhardt, Olaf Etzmuss, and Michael Hauth. 2000. Implicit-explicit schemes for fast animation with particle systems. In Proceedings of the 11th EuroGraphics Workshop on Computer Animation and Simulation (EGCAS’00). Springer, New York, 137–151.
    13. O. Etzmuss, M. Keckeisen, and W. Strasser. 2003. A fast finite element solution for cloth modelling. In Proceedings of the Pacific Conference on Computer Graphics and Applications. 244.
    14. A. Friedli. 1978. Verallgemeinerte Runge-Kutta verfahren zur losung steifer differentialgleichungen. In Lecture Notes in Mathematics, vol. 631, 214–219.
    15. B. García-Archilla, J. M. Sanz-Serna, and R. D. Skeel. 1999. Long-time-step methods for oscillatory differential equations. SIAM J. Sci. Comput. 20, 930–963.
    16. Walter Gautschi. 1961. Numerical integration of ordinary differential equations based on trigonometric polynomials. Numerische Mathematik 3, 381–397.
    17. Rony Goldenthal, David Harmon, Raanan Fattal, Michel Bercovier, and Eitan Grinspun. 2007. Efficient simulation of inextensible cloth. In ACM SIGGRAPH Papers. ACM Press, New York.
    18. Michael Griebel, Stephan Knapek, and Gerhard Zumbusch. 2007. Numerical Simulation in Molecular Dynamics: Numerics, Algorithms, Parallelization, Applications. Springer.
    19. Volker Grimm and Marlis Hochbruck. 2006. Error analysis of exponential integrators for oscillatory second-order differential equations. J. Phys. A: Math. Gen. 39, 5495–5507.
    20. Ernst Hairer and Christian Lubich. 2000. Long-time energy conservation of numerical methods for oscillatory differential equations. SIAM J. Numer. Anal. 38, 414–441.
    21. E. Hairer, C. Lubich, and G. Wanner. 2006. Geometric Numerical Integration: Structure-Preserving Algorithms for Oscillatory Differential Equations. Springer Series in Computational Mathematics.
    22. Michael Hauth and Olaf Etzmuss. 2001. A high performance solver for the animation of deformable objects using advanced numerical methods. Comput. Graph. Forum 20, 319–328.
    23. Joseph Hersch. 1958. Contribution a la methode des equations aux differences. Zeitschrift Angewandte Mathematik Physik 9, 129–180.
    24. Marlis Hochbruck and Christian Lubich. 1997. On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 34, 1911–1925.
    25. Marlis Hochbruck and Christian Lubich. 1999. A gautschi-type method for oscillatory second-order differential equations. Numer. Math. 83, 3, 403-426.
    26. Marlis Hochbruck, C. Lubich, and H. Selfhofer. 1998. Exponential integrators for large systems of differential equations. SIAM J. Sci. Comput. 19, 1552–1574.
    27. Marlis Hochbruck and Alexander Ostermann. 2010. Exponential integrators. Acta Numerica 19, 209–286.
    28. G. Irving, J. Teran, and R. Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the ACM SIGGRAPH/EuroGraphics Symposium on Computer Animation. 131–140.
    29. Firas Khatib, Frank DiMaio, Seth Cooper, Maciej Kazmierczyk, Miroslaw Gilski, Szymon Krzywda, Helena Zabranska, Iva Pichova, James Thompson, Zoran Popović, Mariusz Jaskolski, and David Baker. 2011. Crystal structure of a monomeric retroviral protease solved by protein folding game players. Nat. Struct. Molec. Biol. 18, 10, 1175–1177.
    30. J. Lagrange. 1809. Supplement au Memoire sur la Theorie Generale de la Variation des Constantes Arbitraires, dans Tous les Problemes de la Mecanique. Memoires de la Classe des Sciences Mathematiques et Physiques.
    31. J. Lawson. 1967. Generalized runge-kutta processes for stable systems with large lipschitz constants. SIAM J. Numer. Anal. 4, 370–372.
    32. R. McLachlan and D. O’Neale. 2007. Implicit-explicit variational integration of highly oscillatory problems. Preprint N107052-HOP.
    33. Cleve Moler and Charles Van Loan. 1978. Nineteen dubious ways to compute the exponential of a matrix. SIAM Rev. 20, 801–836.
    34. Cleve Moler and Charles Van Loan. 2003. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Rev. 45, 1, 3–49.
    35. 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 (SCA’02). ACM Press, New York, 49–54.
    36. Andrew Nealen, Matthias Müller, Richard Keiser, Eddy Boxerman, and Mark Carlson. 2006. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 809–836.
    37. S. Nørsett. 1969. An a-stable modification of the adams-bashforth methods. In Lecture Notes in Mathematics, vol. 109, 214–219.
    38. David A. Pope. 1963. An exponential method of numerical integration of ordinary differential equations. Comm. ACM 6, 8, 491–493.
    39. RCSB PDB. 2013. RCSB protein data bank. http://www.rcsb.org/pdb/static.do?p=general_information/news_publications/articles/index.html.
    40. H. H. Rosenbrock. 1963. Some general implicit processes for the numerical solution of differential equations. Comput. J. 5, 4, 329–330.
    41. Y. Saad. 1992. Analysis of some krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 29, 209–228.
    42. R. Sidje. 1998. Expokit: A software package for computing matrix exponentials. ACM Trans. Math. Softw. 24, 1, 130–156.
    43. Stanford University. 2013. The stanford 3D scanning repository. http://graphics.stanford.edu/data/3Dscanrep/.
    44. Ari Stern and Eitan Grinspun. 2009. Implicit-explicit variational integration of highly oscillatory problems. Multiscale Model. Simul. 7, 1779–1794.
    45. Jonathan Su, Rahul Sheth, and Ronald Fedkiw. 2012. Energy conservation for the simulation of deformable bodies. IEEE Trans. Vis. Comput. Graph. 19, 2, 189–200.
    46. Mark C. Surles. 1992. An algorithm with linear complexity for interactive, physically-based modeling of large proteins. In Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’92). ACM Press, New York, 221–230.
    47. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’87). ACM Press, New York, 205–214.
    48. G. Wempner. 1969. Finite elements, finite rotations and small strains of flexible shells. Int. J. Solids Struct. 5, 117–153.

ACM Digital Library Publication:


Overview Page: