American Institute of Mathematical Sciences

Advanced
June  2016, 3(2): 139-161. doi: 10.3934/jcd.2016007

Towards tensor-based methods for the numerical approximation of the Perron--Frobenius and Koopman operator

Stefan Klus 1, and  Christof Schütte 1,

1. 

Department of Mathematics and Computer Science, Freie Universität Berlin

Received  November 2015 Revised  August 2016 Published  November 2016

The global behavior of dynamical systems can be studied by analyzing the eigenvalues and corresponding eigenfunctions of linear operators associated with the system. Two important operators which are frequently used to gain insight into the system's behavior are the Perron--Frobenius operator and the Koopman operator. Due to the curse of dimensionality, computing the eigenfunctions of high-dimensional systems is in general infeasible. We will propose a tensor-based reformulation of two numerical methods for computing finite-dimensional approximations of the aforementioned infinite-dimensional operators, namely Ulam's method and Extended Dynamic Mode Decomposition (EDMD). The aim of the tensor formulation is to approximate the eigenfunctions by low-rank tensors, potentially resulting in a significant reduction of the time and memory required to solve the resulting eigenvalue problems, provided that such a low-rank tensor decomposition exists. Typically, not all variables of a high-dimensional dynamical system contribute equally to the system's behavior, often the dynamics can be decomposed into slow and fast processes, which is also reflected in the eigenfunctions. Thus, the weak coupling between different variables might be approximated by low-rank tensor cores. We will illustrate the efficiency of the tensor-based formulation of Ulam's method and EDMD using simple stochastic differential equations.
Keywords: Perron--Frobenius operator, TT format., Ulam's method, Koopman operator, extended dynamic mode decomposition.
Mathematics Subject Classification: Primary: 37N25, 37L65, 15A6.
Citation: Stefan Klus, Christof Schütte. Towards tensor-based methods for the numerical approximation of the Perron--Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (2) : 139-161. doi: 10.3934/jcd.2016007
References:
[1]

G. Beylkin and M. J. Mohlenkamp, Numerical operator calculus in higher dimensions,, Proceedings of the National Academy of Sciences, 99 (2002), 10246.  doi: 10.1073/pnas.112329799.  Google Scholar

[2]

G. Beylkin and M. J. Mohlenkamp, Algorithms for numerical analysis in high dimensions,, SIAM Journal on Scientific Computing, 26 (2005), 2133.  doi: 10.1137/040604959.  Google Scholar

[3]

E. M. Bollt and N. Santitissadeekorn, Applied and Computational Measurable Dynamics,, Society for Industrial and Applied Mathematics, (2013).  doi: 10.1137/1.9781611972641.  Google Scholar

[4]

M. Budišić, R. Mohr and I. Mezić, Applied koopmanism,, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 ().   Google Scholar

[5]

G. Chen and T. Ueta (eds.), Chaos in Circuits and Systems,, World Scientific Series on Nonlinear Science, (2002).  doi: 10.1142/9789812705303.  Google Scholar

[6]

M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - Set oriented numerical methods for dynamical systems,, in Ergodic theory, (2001), 145.   Google Scholar

[7]

M. Dellnitz and O. Junge, On the approximation of complicated dynamical behavior,, SIAM Journal on Numerical Analysis, 36 (1999), 491.  doi: 10.1137/S0036142996313002.  Google Scholar

[8]

J. Ding, Q. Du and T.-Y. Li, High order approximation of the Frobenius-Perron operator,, Applied Mathematics and Computation, 53 (1993), 151.  doi: 10.1016/0096-3003(93)90099-Z.  Google Scholar

[9]

G. Friesecke, O. Junge and P. Koltai, Mean field approximation in conformation dynamics,, Multiscale Modeling & Simulation, 8 (2009), 254.  doi: 10.1137/080745262.  Google Scholar

[10]

G. Froyland, G. Gottwald and A. Hammerlindl, A computational method to extract macroscopic variables and their dynamics in multiscale systems,, SIAM Journal on Applied Dynamical Systems, 13 (2014), 1816.  doi: 10.1137/130943637.  Google Scholar

[11]

G. Froyland, G. A. Gottwald and A. Hammerlindl, A trajectory-free framework for analysing multiscale systems,, ArXiv e-prints., ().   Google Scholar

[12]

P. Gelß, S. Matera and C. Schütte, Solving the master equation without kinetic Monte Carlo: Tensor train approximations for a CO oxidation model,, Journal of Computational Physics, 314 (2016), 489.  doi: 10.1016/j.jcp.2016.03.025.  Google Scholar

[13]

G. H. Golub and C. F. V. Loan, Matrix Computations,, 4th edition, (2013).   Google Scholar

[14]

L. Grasedyck, D. Kressner and C. Tobler, A literature survey of low-rank tensor approximation techniques,, GAMM-Mitt., 36 (2013), 53.  doi: 10.1002/gamm.201310004.  Google Scholar

[15]

W. Hackbusch, Numerical tensor calculus,, Acta Numerica, 23 (2014), 651.  doi: 10.1017/S0962492914000087.  Google Scholar

[16]

S. Holtz, T. Rohwedder and R. Schneider, The alternating linear scheme for tensor optimization in the tensor train format,, SIAM Journal on Scientific Computing, 34 (2012).  doi: 10.1137/100818893.  Google Scholar

[17]

S. Klus, P. Koltai and C. Schütte, On the numerical approximation of the Perron-Frobenius and Koopman operator,, Journal of Computational Dynamics, 3 (2016), 51.  doi: 10.3934/jcd.2016003.  Google Scholar

[18]

F. Nüske, B. G. Keller, G. Pérez-Hernández, A. S. J. S. Mey and F. Noé, Variational approach to molecular kinetics,, Journal of Chemical Theory and Computation, 10 (2014), 1739.   Google Scholar

[19]

F. Nüske, R. Schneider, F. Vitalini and F. Noé, Variational tensor approach for approximating the rare-event kinetics of macromolecular systems,, The Journal of Chemical Physics, 144 ().   Google Scholar

[20]

I. V. Oseledets, Tensor-train decomposition,, SIAM Journal on Scientific Computing, 33 (2011), 2295.  doi: 10.1137/090752286.  Google Scholar

[21]

I. V. Oseledets, TT-toolbox 2.0: Fast multidimensional Array Operations in TT Format,, 2011., ().   Google Scholar

[22]

R. Preis, M. Dellnitz, M. Hessel, C. Schütte and E. Meerbach, Dominant Paths Between Almost Invariant Sets of Dynamical Systems,, DFG Schwerpunktprogramm 1095, (1095).   Google Scholar

[23]

C. Schütte and M. Sarich, Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches,, no. 24 in Courant Lecture Notes, (2013).  doi: 10.1090/cln/024.  Google Scholar

[24]

M. O. Williams, I. G. Kevrekidis and C. W. Rowley, A data-driven approximation of the Koopman operator: Extending dynamic mode decomposition,, J. Nonlinear Sci., 25 (2015), 1307.  doi: 10.1007/s00332-015-9258-5.  Google Scholar

[25]

M. O. Williams, C. W. Rowley and I. G. Kevrekidis, A kernel-based approach to data-driven Koopman spectral analysis,, J. Comput. Dyn., 2 (2015), 247.  doi: 10.3934/jcd.2015005.  Google Scholar

show all references

References:
[1]

G. Beylkin and M. J. Mohlenkamp, Numerical operator calculus in higher dimensions,, Proceedings of the National Academy of Sciences, 99 (2002), 10246.  doi: 10.1073/pnas.112329799.  Google Scholar

[2]

G. Beylkin and M. J. Mohlenkamp, Algorithms for numerical analysis in high dimensions,, SIAM Journal on Scientific Computing, 26 (2005), 2133.  doi: 10.1137/040604959.  Google Scholar

[3]

E. M. Bollt and N. Santitissadeekorn, Applied and Computational Measurable Dynamics,, Society for Industrial and Applied Mathematics, (2013).  doi: 10.1137/1.9781611972641.  Google Scholar

[4]

M. Budišić, R. Mohr and I. Mezić, Applied koopmanism,, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 ().   Google Scholar

[5]

G. Chen and T. Ueta (eds.), Chaos in Circuits and Systems,, World Scientific Series on Nonlinear Science, (2002).  doi: 10.1142/9789812705303.  Google Scholar

[6]

M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - Set oriented numerical methods for dynamical systems,, in Ergodic theory, (2001), 145.   Google Scholar

[7]

M. Dellnitz and O. Junge, On the approximation of complicated dynamical behavior,, SIAM Journal on Numerical Analysis, 36 (1999), 491.  doi: 10.1137/S0036142996313002.  Google Scholar

[8]

J. Ding, Q. Du and T.-Y. Li, High order approximation of the Frobenius-Perron operator,, Applied Mathematics and Computation, 53 (1993), 151.  doi: 10.1016/0096-3003(93)90099-Z.  Google Scholar

[9]

G. Friesecke, O. Junge and P. Koltai, Mean field approximation in conformation dynamics,, Multiscale Modeling & Simulation, 8 (2009), 254.  doi: 10.1137/080745262.  Google Scholar

[10]

G. Froyland, G. Gottwald and A. Hammerlindl, A computational method to extract macroscopic variables and their dynamics in multiscale systems,, SIAM Journal on Applied Dynamical Systems, 13 (2014), 1816.  doi: 10.1137/130943637.  Google Scholar

[11]

G. Froyland, G. A. Gottwald and A. Hammerlindl, A trajectory-free framework for analysing multiscale systems,, ArXiv e-prints., ().   Google Scholar

[12]

P. Gelß, S. Matera and C. Schütte, Solving the master equation without kinetic Monte Carlo: Tensor train approximations for a CO oxidation model,, Journal of Computational Physics, 314 (2016), 489.  doi: 10.1016/j.jcp.2016.03.025.  Google Scholar

[13]

G. H. Golub and C. F. V. Loan, Matrix Computations,, 4th edition, (2013).   Google Scholar

[14]

L. Grasedyck, D. Kressner and C. Tobler, A literature survey of low-rank tensor approximation techniques,, GAMM-Mitt., 36 (2013), 53.  doi: 10.1002/gamm.201310004.  Google Scholar

[15]

W. Hackbusch, Numerical tensor calculus,, Acta Numerica, 23 (2014), 651.  doi: 10.1017/S0962492914000087.  Google Scholar

[16]

S. Holtz, T. Rohwedder and R. Schneider, The alternating linear scheme for tensor optimization in the tensor train format,, SIAM Journal on Scientific Computing, 34 (2012).  doi: 10.1137/100818893.  Google Scholar

[17]

S. Klus, P. Koltai and C. Schütte, On the numerical approximation of the Perron-Frobenius and Koopman operator,, Journal of Computational Dynamics, 3 (2016), 51.  doi: 10.3934/jcd.2016003.  Google Scholar

[18]

F. Nüske, B. G. Keller, G. Pérez-Hernández, A. S. J. S. Mey and F. Noé, Variational approach to molecular kinetics,, Journal of Chemical Theory and Computation, 10 (2014), 1739.   Google Scholar

[19]

F. Nüske, R. Schneider, F. Vitalini and F. Noé, Variational tensor approach for approximating the rare-event kinetics of macromolecular systems,, The Journal of Chemical Physics, 144 ().   Google Scholar

[20]

I. V. Oseledets, Tensor-train decomposition,, SIAM Journal on Scientific Computing, 33 (2011), 2295.  doi: 10.1137/090752286.  Google Scholar

[21]

I. V. Oseledets, TT-toolbox 2.0: Fast multidimensional Array Operations in TT Format,, 2011., ().   Google Scholar

[22]

R. Preis, M. Dellnitz, M. Hessel, C. Schütte and E. Meerbach, Dominant Paths Between Almost Invariant Sets of Dynamical Systems,, DFG Schwerpunktprogramm 1095, (1095).   Google Scholar

[23]

C. Schütte and M. Sarich, Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches,, no. 24 in Courant Lecture Notes, (2013).  doi: 10.1090/cln/024.  Google Scholar

[24]

M. O. Williams, I. G. Kevrekidis and C. W. Rowley, A data-driven approximation of the Koopman operator: Extending dynamic mode decomposition,, J. Nonlinear Sci., 25 (2015), 1307.  doi: 10.1007/s00332-015-9258-5.  Google Scholar

[25]

M. O. Williams, C. W. Rowley and I. G. Kevrekidis, A kernel-based approach to data-driven Koopman spectral analysis,, J. Comput. Dyn., 2 (2015), 247.  doi: 10.3934/jcd.2015005.  Google Scholar

[1]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[2]

Xing-Bin Pan. Variational and operator methods for Maxwell-Stokes system. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3909-3955. doi: 10.3934/dcds.2020036
[3]

Ole Løseth Elvetun, Bjørn Fredrik Nielsen. A regularization operator for source identification for elliptic PDEs. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021006
[4]

Laure Cardoulis, Michel Cristofol, Morgan Morancey. A stability result for the diffusion coefficient of the heat operator defined on an unbounded guide. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020054
[5]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020391
[6]

Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436
[7]

Yoshitsugu Kabeya. Eigenvalues of the Laplace-Beltrami operator under the homogeneous Neumann condition on a large zonal domain in the unit sphere. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3529-3559. doi: 10.3934/dcds.2020040
[8]

Hongyan Guo. Automorphism group and twisted modules of the twisted Heisenberg-Virasoro vertex operator algebra. Electronic Research Archive, , () : -. doi: 10.3934/era.2021008
[9]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[10]

Tomáš Oberhuber, Tomáš Dytrych, Kristina D. Launey, Daniel Langr, Jerry P. Draayer. Transformation of a Nucleon-Nucleon potential operator into its SU(3) tensor form using GPUs. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1111-1122. doi: 10.3934/dcdss.2020383
[11]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[12]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[13]

Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020127
[14]

Maika Goto, Kazunori Kuwana, Yasuhide Uegata, Shigetoshi Yazaki. A method how to determine parameters arising in a smoldering evolution equation by image segmentation for experiment's movies. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 881-891. doi: 10.3934/dcdss.2020233
[15]

Wen Li, Wei-Hui Liu, Seak Weng Vong. Perron vector analysis for irreducible nonnegative tensors and its applications. Journal of Industrial & Management Optimization, 2021, 17 (1) : 29-50. doi: 10.3934/jimo.2019097
[16]

Yi Guan, Michal Fečkan, Jinrong Wang. Periodic solutions and Hyers-Ulam stability of atmospheric Ekman flows. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1157-1176. doi: 10.3934/dcds.2020313
[17]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098
[18]

Yujuan Li, Huaifu Wang, Peipei Zhou, Guoshuang Zhang. Some properties of the cycle decomposition of WG-NLFSR. Advances in Mathematics of Communications, 2021, 15 (1) : 155-165. doi: 10.3934/amc.2020050
[19]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321
[20]

Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021002

 Impact Factor: 

Tools

Metrics

  • PDF downloads (108)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences