Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2021 | OriginalPaper | Buchkapitel

Exponential Rosenbrock Methods and Their Application in Visual Computing

verfasst von: Vu Thai Luan, Dominik L. Michels

Erschienen in: Rosenbrock—Wanner–Type Methods

Verlag: Springer International Publishing

share
TEILEN

Abstract

We introduce a class of explicit exponential Rosenbrock methods for the time integration of large systems of stiff differential equations. Their application with respect to simulation tasks in the field of visual computing is discussed where these time integrators have shown to be very competitive compared to standard techniques. In particular, we address the simulation of elastic and nonelastic deformations as well as collision scenarios focusing on relevant aspects like stability and energy conservation, large stiffnesses, high fidelity and visual accuracy.
Fußnoten
1
We estimated the error after 60 s of simulated time based on the accumulated Euclidean distances of the individual particles in the position space compared to ground truth values which are computed with a sufficiently small step size.
 
2
In order to detect collisions efficiently, we make use of a standard bounding volume hierarchy.
 
Literatur
1.
Zurück zum Zitat A.H. Al-Mohy, N.J. Higham, Computing the action of the matrix exponential, with an application to exponential integrators. SIAM J. Sci. Comput. 33, 488–511 (2011) MathSciNetCrossRef A.H. Al-Mohy, N.J. Higham, Computing the action of the matrix exponential, with an application to exponential integrators. SIAM J. Sci. Comput. 33, 488–511 (2011) MathSciNetCrossRef
2.
Zurück zum Zitat U. Ascher, S. Ruuth, B. Wetton, Implicit-explicit methods for time-dependent PDEs. SIAM J. Numer. Anal. 32(3), 797–823 (1997) CrossRef U. Ascher, S. Ruuth, B. Wetton, Implicit-explicit methods for time-dependent PDEs. SIAM J. Numer. Anal. 32(3), 797–823 (1997) CrossRef
3.
Zurück zum Zitat D. Baraff, A. Witkin, Large steps in cloth simulation, in ACM Transactions on Graphics, SIGGRAPH’98 (ACM, New York, 1998), pp. 43–54 D. Baraff, A. Witkin, Large steps in cloth simulation, in ACM Transactions on Graphics, SIGGRAPH’98 (ACM, New York, 1998), pp. 43–54
4.
Zurück zum Zitat M. Bergou, M. Wardetzky, S. Robinson, B. Audoly, E. Grinspun, Discrete elastic rods. ACM Trans. Graph. 27(3), 63:1–63:12 (2008) M. Bergou, M. Wardetzky, S. Robinson, B. Audoly, E. Grinspun, Discrete elastic rods. ACM Trans. Graph. 27(3), 63:1–63:12 (2008)
5.
Zurück zum Zitat M. Caliari, A. Ostermann, Implementation of exponential Rosenbrock-type integrators. Appl. Numer. Math. 59(3–4), 568–581 (2009) MathSciNetCrossRef M. Caliari, A. Ostermann, Implementation of exponential Rosenbrock-type integrators. Appl. Numer. Math. 59(3–4), 568–581 (2009) MathSciNetCrossRef
6.
Zurück zum Zitat M. Caliari, P. Kandolf, A. Ostermann, S. Rainer, The Leja method revisited: backward error analysis for the matrix exponential. SIAM J. Sci. Comput. 38(3), A1639–A1661 (2016) MathSciNetCrossRef M. Caliari, P. Kandolf, A. Ostermann, S. Rainer, The Leja method revisited: backward error analysis for the matrix exponential. SIAM J. Sci. Comput. 38(3), A1639–A1661 (2016) MathSciNetCrossRef
7.
Zurück zum Zitat W.L. Chao, J. Solomon, D. Michels, F. Sha, Exponential integration for Hamiltonian Monte Carlo, in Proceedings of the 32nd International Conference on Machine Learning, ed. by F. Bach, D. Blei. Proceedings of Machine Learning Research, vol. 37, pp. 1142–1151 (PMLR, Lille, 2015) W.L. Chao, J. Solomon, D. Michels, F. Sha, Exponential integration for Hamiltonian Monte Carlo, in Proceedings of the 32nd International Conference on Machine Learning, ed. by F. Bach, D. Blei. Proceedings of Machine Learning Research, vol. 37, pp. 1142–1151 (PMLR, Lille, 2015)
8.
Zurück zum Zitat Y.J. Chen, U.M. Ascher, D.K. Pai, Exponential Rosenbrock-Euler integrators for elastodynamic simulation. IEEE Trans. Visual. Comput. Graph. 24(10), 2702–2713 (2018) CrossRef Y.J. Chen, U.M. Ascher, D.K. Pai, Exponential Rosenbrock-Euler integrators for elastodynamic simulation. IEEE Trans. Visual. Comput. Graph. 24(10), 2702–2713 (2018) CrossRef
9.
Zurück zum Zitat S.M. Cox, P.C. Matthews, Exponential time differencing for stiff systems. J. Comput. Phys. 176(2), 430–455 (2002) MathSciNetCrossRef S.M. Cox, P.C. Matthews, Exponential time differencing for stiff systems. J. Comput. Phys. 176(2), 430–455 (2002) MathSciNetCrossRef
10.
Zurück zum Zitat C. Curtiss, J.O. Hirschfelder, Integration of stiff equations. Proc. Natl. Acad. Sci. 38(3), 235–243 (1952) MathSciNetCrossRef C. Curtiss, J.O. Hirschfelder, Integration of stiff equations. Proc. Natl. Acad. Sci. 38(3), 235–243 (1952) MathSciNetCrossRef
11.
Zurück zum Zitat C.F. Curtiss, J.O. Hirschfelder, Integration of stiff equations. Proc. Natl. Acad. Sci. USA 38(3), 235–243 (1952) MathSciNetCrossRef C.F. Curtiss, J.O. Hirschfelder, Integration of stiff equations. Proc. Natl. Acad. Sci. USA 38(3), 235–243 (1952) MathSciNetCrossRef
12.
Zurück zum Zitat B. Eberhardt, O. Etzmuß, M. Hauth, Implicit-explicit schemes for fast animation with particle systems, in Proceedings of the 11th Eurographics Workshop on Computer Animation and Simulation (EGCAS) (Springer, Berlin, 2000), pp. 137–151 B. Eberhardt, O. Etzmuß, M. Hauth, Implicit-explicit schemes for fast animation with particle systems, in Proceedings of the 11th Eurographics Workshop on Computer Animation and Simulation (EGCAS) (Springer, Berlin, 2000), pp. 137–151
13.
Zurück zum Zitat S. Gaudreault, J. Pudykiewicz, An efficient exponential time integration method for the numerical solution of the shallow water equations on the sphere. J. Comput. Phys. 322, 827–848 (2016) MathSciNetCrossRef S. Gaudreault, J. Pudykiewicz, An efficient exponential time integration method for the numerical solution of the shallow water equations on the sphere. J. Comput. Phys. 322, 827–848 (2016) MathSciNetCrossRef
14.
Zurück zum Zitat C. Gear, Numerical Initial Value Problems in Ordinary Differential Equations (Prentice–Hall, Englewood Cliffs, 1971) C. Gear, Numerical Initial Value Problems in Ordinary Differential Equations (Prentice–Hall, Englewood Cliffs, 1971)
15.
Zurück zum Zitat S. Geiger, G. Lord, A. Tambue, Exponential time integrators for stochastic partial differential equations in 3D reservoir simulation. Comput. Geosci. 16(2), 323–334 (2012) CrossRef S. Geiger, G. Lord, A. Tambue, Exponential time integrators for stochastic partial differential equations in 3D reservoir simulation. Comput. Geosci. 16(2), 323–334 (2012) CrossRef
16.
Zurück zum Zitat R. Goldenthal, D. Harmon, R. Fattal, M. Bercovier, E. Grinspun, Efficient simulation of inextensible cloth, in ACM Transactions on Graphics, SIGGRAPH’07 (2007) R. Goldenthal, D. Harmon, R. Fattal, M. Bercovier, E. Grinspun, Efficient simulation of inextensible cloth, in ACM Transactions on Graphics, SIGGRAPH’07 (2007)
17.
Zurück zum Zitat M.A. Gondal, Exponential Rosenbrock integrators for option pricing. J. Comput. Appl. Math. 234(4), 1153–1160 (2010) MathSciNetCrossRef M.A. Gondal, Exponential Rosenbrock integrators for option pricing. J. Comput. Appl. Math. 234(4), 1153–1160 (2010) MathSciNetCrossRef
18.
Zurück zum Zitat E. Hairer, G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems (Springer, New York, 1996) CrossRef E. Hairer, G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems (Springer, New York, 1996) CrossRef
19.
Zurück zum Zitat M. Hauth, O. Etzmuss, A high performance solver for the animation of deformable objects using advanced numerical methods. Comput. Graph. Forum 20, 319–328 (2001) CrossRef M. Hauth, O. Etzmuss, A high performance solver for the animation of deformable objects using advanced numerical methods. Comput. Graph. Forum 20, 319–328 (2001) CrossRef
20.
Zurück zum Zitat N.J. Higham, Functions of Matrices: Theory and Computation (SIAM, Philadelphia, 2008) CrossRef N.J. Higham, Functions of Matrices: Theory and Computation (SIAM, Philadelphia, 2008) CrossRef
21.
Zurück zum Zitat M. Hochbruck, C. Lubich, On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 34, 1911–1925 (1997) MathSciNetCrossRef M. Hochbruck, C. Lubich, On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 34, 1911–1925 (1997) MathSciNetCrossRef
22.
Zurück zum Zitat M. Hochbruck, A. Ostermann, Explicit exponential Runge–Kutta methods for semilinear parabolic problems. SIAM J. Numer. Anal. 43, 1069–1090 (2005) MathSciNetCrossRef M. Hochbruck, A. Ostermann, Explicit exponential Runge–Kutta methods for semilinear parabolic problems. SIAM J. Numer. Anal. 43, 1069–1090 (2005) MathSciNetCrossRef
23.
Zurück zum Zitat M. Hochbruck, A. Ostermann, Explicit integrators of Rosenbrock-type. Oberwolfach Rep. 3, 1107–1110 (2006) M. Hochbruck, A. Ostermann, Explicit integrators of Rosenbrock-type. Oberwolfach Rep. 3, 1107–1110 (2006)
25.
Zurück zum Zitat M. Hochbruck, C. Lubich, H. Selhofer, Exponential integrators for large systems of differential equations. SIAM J. Sci. Comput. 19, 1552–1574 (1998) MathSciNetCrossRef M. Hochbruck, C. Lubich, H. Selhofer, Exponential integrators for large systems of differential equations. SIAM J. Sci. Comput. 19, 1552–1574 (1998) MathSciNetCrossRef
26.
Zurück zum Zitat M. Hochbruck, A. Ostermann, J. Schweitzer, Exponential Rosenbrock-type methods. SIAM J. Numer. Anal. 47, 786–803 (2009) MathSciNetCrossRef M. Hochbruck, A. Ostermann, J. Schweitzer, Exponential Rosenbrock-type methods. SIAM J. Numer. Anal. 47, 786–803 (2009) MathSciNetCrossRef
27.
28.
Zurück zum Zitat M.W. Kutta, Beitrag zur näherungsweisen Integration totaler Differentialgleichungen. Z. Math. Phys. 46, 435–453 (1901) MATH M.W. Kutta, Beitrag zur näherungsweisen Integration totaler Differentialgleichungen. Z. Math. Phys. 46, 435–453 (1901) MATH
29.
Zurück zum Zitat V.T. Luan, Fourth-order two-stage explicit exponential integrators for time-dependent PDEs. Appl. Numer. Math. 112, 91–103 (2017) MathSciNetCrossRef V.T. Luan, Fourth-order two-stage explicit exponential integrators for time-dependent PDEs. Appl. Numer. Math. 112, 91–103 (2017) MathSciNetCrossRef
30.
31.
Zurück zum Zitat V.T. Luan, A. Ostermann, Explicit exponential Runge–Kutta methods of high order for parabolic problems. J. Comput. Appl. Math. 256, 168–179 (2014) MathSciNetCrossRef V.T. Luan, A. Ostermann, Explicit exponential Runge–Kutta methods of high order for parabolic problems. J. Comput. Appl. Math. 256, 168–179 (2014) MathSciNetCrossRef
32.
Zurück zum Zitat V.T. Luan, A. Ostermann, Exponential Rosenbrock methods of order five–construction, analysis and numerical comparisons. J. Comput. Appl. Math. 255, 417–431 (2014) MathSciNetCrossRef V.T. Luan, A. Ostermann, Exponential Rosenbrock methods of order five–construction, analysis and numerical comparisons. J. Comput. Appl. Math. 255, 417–431 (2014) MathSciNetCrossRef
33.
Zurück zum Zitat V.T. Luan, A. Ostermann, Stiff order conditions for exponential Runge–Kutta methods of order five, in Modeling, Simulation and Optimization of Complex Processes - HPSC 2012, H.B. et al. (ed.) (Springer, Berlin, 2014), pp. 133–143 V.T. Luan, A. Ostermann, Stiff order conditions for exponential Runge–Kutta methods of order five, in Modeling, Simulation and Optimization of Complex Processes - HPSC 2012, H.B. et al. (ed.) (Springer, Berlin, 2014), pp. 133–143
34.
Zurück zum Zitat V.T. Luan, A. Ostermann, Parallel exponential Rosenbrock methods. Comput. Math. Appl. 71, 1137–1150 (2016) MathSciNetCrossRef V.T. Luan, A. Ostermann, Parallel exponential Rosenbrock methods. Comput. Math. Appl. 71, 1137–1150 (2016) MathSciNetCrossRef
35.
Zurück zum Zitat V.T. Luan, J.A. Pudykiewicz, D.R. Reynolds, Further development of the efficient and accurate time integration schemes for meteorological models J. Comput. Sci. 376, 817–837 (2018) MathSciNetMATH V.T. Luan, J.A. Pudykiewicz, D.R. Reynolds, Further development of the efficient and accurate time integration schemes for meteorological models J. Comput. Sci. 376, 817–837 (2018) MathSciNetMATH
36.
Zurück zum Zitat D.L. Michels, M. Desbrun, A semi-analytical approach to molecular dynamics. J. Comput. Phys. 303, 336–354 (2015) MathSciNetCrossRef D.L. Michels, M. Desbrun, A semi-analytical approach to molecular dynamics. J. Comput. Phys. 303, 336–354 (2015) MathSciNetCrossRef
37.
Zurück zum Zitat D.L. Michels, J.P.T. Mueller, Discrete computational mechanics for stiff phenomena, in SIGGRAPH ASIA 2016 Courses (2016), pp. 13:1–13:9 D.L. Michels, J.P.T. Mueller, Discrete computational mechanics for stiff phenomena, in SIGGRAPH ASIA 2016 Courses (2016), pp. 13:1–13:9
38.
Zurück zum Zitat D.L. Michels, G.A. Sobottka, A.G. Weber, Exponential integrators for stiff elastodynamic problems. ACM Trans. Graph. 33(1), 7:1–7:20 (2014) D.L. Michels, G.A. Sobottka, A.G. Weber, Exponential integrators for stiff elastodynamic problems. ACM Trans. Graph. 33(1), 7:1–7:20 (2014)
39.
Zurück zum Zitat D.L. Michels, J.P.T. Mueller, G.A. Sobottka, A physically based approach to the accurate simulation of stiff fibers and stiff fiber meshes. Comput. Graph. 53B, 136–146 (2015) CrossRef D.L. Michels, J.P.T. Mueller, G.A. Sobottka, A physically based approach to the accurate simulation of stiff fibers and stiff fiber meshes. Comput. Graph. 53B, 136–146 (2015) CrossRef
40.
Zurück zum Zitat D.L. Michels, V.T. Luan, M. Tokman, A stiffly accurate integrator for elastodynamic problems. ACM Trans. Graph. 36(4), 116 (2017) D.L. Michels, V.T. Luan, M. Tokman, A stiffly accurate integrator for elastodynamic problems. ACM Trans. Graph. 36(4), 116 (2017)
41.
Zurück zum Zitat J. Niesen, W.M. Wright, Algorithm 919: a Krylov subspace algorithm for evaluating the φ-functions appearing in exponential integrators. ACM Trans. Math. Softw. 38, 3 (2012) MathSciNetCrossRef J. Niesen, W.M. Wright, Algorithm 919: a Krylov subspace algorithm for evaluating the φ-functions appearing in exponential integrators. ACM Trans. Math. Softw. 38, 3 (2012) MathSciNetCrossRef
42.
Zurück zum Zitat D.A. Pope, An exponential method of numerical integration of ordinary differential equations. Commun. ACM 6, 491–493 (1963) MathSciNetCrossRef D.A. Pope, An exponential method of numerical integration of ordinary differential equations. Commun. ACM 6, 491–493 (1963) MathSciNetCrossRef
43.
44.
Zurück zum Zitat A. Stern, M. Desbrun, Discrete geometric mechanics for variational time integrators, in SIGGRAPH 2006 Courses (2006), pp. 75–80 A. Stern, M. Desbrun, Discrete geometric mechanics for variational time integrators, in SIGGRAPH 2006 Courses (2006), pp. 75–80
45.
Zurück zum Zitat A. Stern, E. Grinspun, Implicit-explicit variational integration of highly oscillatory problems. Multiscale Model. Simul. 7, 1779–1794 (2009) MathSciNetCrossRef A. Stern, E. Grinspun, Implicit-explicit variational integration of highly oscillatory problems. Multiscale Model. Simul. 7, 1779–1794 (2009) MathSciNetCrossRef
46.
Zurück zum Zitat A. Tambue, I. Berre, J.M. Nordbotten, Efficient simulation of geothermal processes in heterogeneous porous media based on the exponential Rosenbrock–Euler and Rosenbrock-type methods. Adv. Water Resour. 53, 250–262 (2013) CrossRef A. Tambue, I. Berre, J.M. Nordbotten, Efficient simulation of geothermal processes in heterogeneous porous media based on the exponential Rosenbrock–Euler and Rosenbrock-type methods. Adv. Water Resour. 53, 250–262 (2013) CrossRef
47.
Zurück zum Zitat D. Terzopoulos, J. Platt, A. Barr, K. Fleischer, Elastically deformable models. ACM Trans. Graph. 21, 205–214 (1987) D. Terzopoulos, J. Platt, A. Barr, K. Fleischer, Elastically deformable models. ACM Trans. Graph. 21, 205–214 (1987)
48.
Zurück zum Zitat M. Tokman, J. Loffeld, P. Tranquilli, New adaptive exponential propagation iterative methods of Runge-Kutta type. SIAM J. Sci. Comput. 34, A2650–A2669 (2012) MathSciNetCrossRef M. Tokman, J. Loffeld, P. Tranquilli, New adaptive exponential propagation iterative methods of Runge-Kutta type. SIAM J. Sci. Comput. 34, A2650–A2669 (2012) MathSciNetCrossRef
49.
Zurück zum Zitat H. Zhuang, I. Kang, X. Wang, J.H. Lin, C.K. Cheng, Dynamic analysis of power delivery network with nonlinear components using matrix exponential method, in 2015 IEEE Symposium on Electromagnetic Compatibility and Signal Integrity (IEEE, Piscataway, 2015), pp. 248–252 H. Zhuang, I. Kang, X. Wang, J.H. Lin, C.K. Cheng, Dynamic analysis of power delivery network with nonlinear components using matrix exponential method, in 2015 IEEE Symposium on Electromagnetic Compatibility and Signal Integrity (IEEE, Piscataway, 2015), pp. 248–252
Metadaten
Titel
Exponential Rosenbrock Methods and Their Application in Visual Computing
verfasst von
Vu Thai Luan
Dominik L. Michels
Copyright-Jahr
2021
DOI
https://doi.org/10.1007/978-3-030-76810-2_3

Premium Partner