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

Previous Article
Computing coherent sets using the Fokker-Planck equation
JCD Home
This Issue
Next Article
Rigorous bounds for polynomial Julia sets

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

Abstract
Related Papers

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-10251. doi: 10.1073/pnas.112329799.
[2]	G. Beylkin and M. J. Mohlenkamp, Algorithms for numerical analysis in high dimensions, SIAM Journal on Scientific Computing, 26 (2005), 2133-2159. doi: 10.1137/040604959.
[3]	E. M. Bollt and N. Santitissadeekorn, Applied and Computational Measurable Dynamics, Society for Industrial and Applied Mathematics, 2013. doi: 10.1137/1.9781611972641.
[4]	M. Budišić, R. Mohr and I. Mezić, Applied koopmanism, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22.
[5]	G. Chen and T. Ueta (eds.), Chaos in Circuits and Systems, World Scientific Series on Nonlinear Science, Series B, Volume 11, World Scientific, 2002. doi: 10.1142/9789812705303.
[6]	M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - Set oriented numerical methods for dynamical systems, in Ergodic theory, analysis, and efficient simulation of dynamical systems, Springer, 2001, 145-174.
[7]	M. Dellnitz and O. Junge, On the approximation of complicated dynamical behavior, SIAM Journal on Numerical Analysis, 36 (1999), 491-515. doi: 10.1137/S0036142996313002.
[8]	J. Ding, Q. Du and T.-Y. Li, High order approximation of the Frobenius-Perron operator, Applied Mathematics and Computation, 53 (1993), 151-171. doi: 10.1016/0096-3003(93)90099-Z.
[9]	G. Friesecke, O. Junge and P. Koltai, Mean field approximation in conformation dynamics, Multiscale Modeling & Simulation, 8 (2009), 254-268. doi: 10.1137/080745262.
[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-1846. doi: 10.1137/130943637.
[11]	G. Froyland, G. A. Gottwald and A. Hammerlindl, A trajectory-free framework for analysing multiscale systems, ArXiv e-prints.
[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-502. doi: 10.1016/j.jcp.2016.03.025.
[13]	G. H. Golub and C. F. V. Loan, Matrix Computations, 4th edition, Johns Hopkins University Press, 2013.
[14]	L. Grasedyck, D. Kressner and C. Tobler, A literature survey of low-rank tensor approximation techniques, GAMM-Mitt., 36 (2013), 53-78. doi: 10.1002/gamm.201310004.
[15]	W. Hackbusch, Numerical tensor calculus, Acta Numerica, 23 (2014), 651-742. doi: 10.1017/S0962492914000087.
[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), A683-A713. doi: 10.1137/100818893.
[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-79. doi: 10.3934/jcd.2016003.
[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-1752.
[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.
[20]	I. V. Oseledets, Tensor-train decomposition, SIAM Journal on Scientific Computing, 33 (2011), 2295-2317. doi: 10.1137/090752286.
[21]	I. V. Oseledets, TT-toolbox 2.0: Fast multidimensional Array Operations in TT Format, 2011.
[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, Technical Report 154, 2004.
[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, American Mathematical Society, 2013. doi: 10.1090/cln/024.
[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-1346. doi: 10.1007/s00332-015-9258-5.
[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-265. doi: 10.3934/jcd.2015005.

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-10251. doi: 10.1073/pnas.112329799.
[2]	G. Beylkin and M. J. Mohlenkamp, Algorithms for numerical analysis in high dimensions, SIAM Journal on Scientific Computing, 26 (2005), 2133-2159. doi: 10.1137/040604959.
[3]	E. M. Bollt and N. Santitissadeekorn, Applied and Computational Measurable Dynamics, Society for Industrial and Applied Mathematics, 2013. doi: 10.1137/1.9781611972641.
[4]	M. Budišić, R. Mohr and I. Mezić, Applied koopmanism, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22.
[5]	G. Chen and T. Ueta (eds.), Chaos in Circuits and Systems, World Scientific Series on Nonlinear Science, Series B, Volume 11, World Scientific, 2002. doi: 10.1142/9789812705303.
[6]	M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - Set oriented numerical methods for dynamical systems, in Ergodic theory, analysis, and efficient simulation of dynamical systems, Springer, 2001, 145-174.
[7]	M. Dellnitz and O. Junge, On the approximation of complicated dynamical behavior, SIAM Journal on Numerical Analysis, 36 (1999), 491-515. doi: 10.1137/S0036142996313002.
[8]	J. Ding, Q. Du and T.-Y. Li, High order approximation of the Frobenius-Perron operator, Applied Mathematics and Computation, 53 (1993), 151-171. doi: 10.1016/0096-3003(93)90099-Z.
[9]	G. Friesecke, O. Junge and P. Koltai, Mean field approximation in conformation dynamics, Multiscale Modeling & Simulation, 8 (2009), 254-268. doi: 10.1137/080745262.
[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-1846. doi: 10.1137/130943637.
[11]	G. Froyland, G. A. Gottwald and A. Hammerlindl, A trajectory-free framework for analysing multiscale systems, ArXiv e-prints.
[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-502. doi: 10.1016/j.jcp.2016.03.025.
[13]	G. H. Golub and C. F. V. Loan, Matrix Computations, 4th edition, Johns Hopkins University Press, 2013.
[14]	L. Grasedyck, D. Kressner and C. Tobler, A literature survey of low-rank tensor approximation techniques, GAMM-Mitt., 36 (2013), 53-78. doi: 10.1002/gamm.201310004.
[15]	W. Hackbusch, Numerical tensor calculus, Acta Numerica, 23 (2014), 651-742. doi: 10.1017/S0962492914000087.
[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), A683-A713. doi: 10.1137/100818893.
[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-79. doi: 10.3934/jcd.2016003.
[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-1752.
[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.
[20]	I. V. Oseledets, Tensor-train decomposition, SIAM Journal on Scientific Computing, 33 (2011), 2295-2317. doi: 10.1137/090752286.
[21]	I. V. Oseledets, TT-toolbox 2.0: Fast multidimensional Array Operations in TT Format, 2011.
[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, Technical Report 154, 2004.
[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, American Mathematical Society, 2013. doi: 10.1090/cln/024.
[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-1346. doi: 10.1007/s00332-015-9258-5.
[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-265. doi: 10.3934/jcd.2015005.

[1]	Stefan Klus, Péter Koltai, Christof Schütte. On the numerical approximation of the Perron-Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (1) : 51-79. doi: 10.3934/jcd.2016003
[2]	Saikat Mazumdar. Struwe's decomposition for a polyharmonic operator on a compact Riemannian manifold with or without boundary. Communications on Pure and Applied Analysis, 2017, 16 (1) : 311-330. doi: 10.3934/cpaa.2017015
[3]	Jonathan H. Tu, Clarence W. Rowley, Dirk M. Luchtenburg, Steven L. Brunton, J. Nathan Kutz. On dynamic mode decomposition: Theory and applications. Journal of Computational Dynamics, 2014, 1 (2) : 391-421. doi: 10.3934/jcd.2014.1.391
[4]	Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002
[5]	Hao Zhang, Scott T. M. Dawson, Clarence W. Rowley, Eric A. Deem, Louis N. Cattafesta. Evaluating the accuracy of the dynamic mode decomposition. Journal of Computational Dynamics, 2020, 7 (1) : 35-56. doi: 10.3934/jcd.2020002
[6]	Mickaël D. Chekroun, Jean Roux. Homeomorphisms group of normed vector space: Conjugacy problems and the Koopman operator. Discrete and Continuous Dynamical Systems, 2013, 33 (9) : 3957-3980. doi: 10.3934/dcds.2013.33.3957
[7]	Christopher Bose, Rua Murray. The exact rate of approximation in Ulam's method. Discrete and Continuous Dynamical Systems, 2001, 7 (1) : 219-235. doi: 10.3934/dcds.2001.7.219
[8]	Jiu Ding, Noah H. Rhee. A unified maximum entropy method via spline functions for Frobenius-Perron operators. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 235-245. doi: 10.3934/naco.2013.3.235
[9]	Rua Murray. Ulam's method for some non-uniformly expanding maps. Discrete and Continuous Dynamical Systems, 2010, 26 (3) : 1007-1018. doi: 10.3934/dcds.2010.26.1007
[10]	Paweł Góra, Abraham Boyarsky. Stochastic perturbations and Ulam's method for W-shaped maps. Discrete and Continuous Dynamical Systems, 2013, 33 (5) : 1937-1944. doi: 10.3934/dcds.2013.33.1937
[11]	Liejune Shiau, Roland Glowinski. Operator splitting method for friction constrained dynamical systems. Conference Publications, 2005, 2005 (Special) : 806-815. doi: 10.3934/proc.2005.2005.806
[12]	Siwei Yu, Jianwei Ma, Stanley Osher. Geometric mode decomposition. Inverse Problems and Imaging, 2018, 12 (4) : 831-852. doi: 10.3934/ipi.2018035
[13]	Mojtaba F. Fathi, Ahmadreza Baghaie, Ali Bakhshinejad, Raphael H. Sacho, Roshan M. D'Souza. Time-resolved denoising using model order reduction, dynamic mode decomposition, and kalman filter and smoother. Journal of Computational Dynamics, 2020, 7 (2) : 469-487. doi: 10.3934/jcd.2020019
[14]	Mustaffa Alfatlawi, Vaibhav Srivastava. An incremental approach to online dynamic mode decomposition for time-varying systems with applications to EEG data modeling. Journal of Computational Dynamics, 2020, 7 (2) : 209-241. doi: 10.3934/jcd.2020009
[15]	Martin Lustig, Caglar Uyanik. Perron-Frobenius theory and frequency convergence for reducible substitutions. Discrete and Continuous Dynamical Systems, 2017, 37 (1) : 355-385. doi: 10.3934/dcds.2017015
[16]	Gary Froyland, Ognjen Stancevic. Escape rates and Perron-Frobenius operators: Open and closed dynamical systems. Discrete and Continuous Dynamical Systems - B, 2010, 14 (2) : 457-472. doi: 10.3934/dcdsb.2010.14.457
[17]	Marianne Akian, Stéphane Gaubert, Antoine Hochart. A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors. Discrete and Continuous Dynamical Systems, 2020, 40 (1) : 207-231. doi: 10.3934/dcds.2020009
[18]	Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013
[19]	Lijian Jiang, Craig C. Douglas. Analysis of an operator splitting method in 4D-Var. Conference Publications, 2009, 2009 (Special) : 394-403. doi: 10.3934/proc.2009.2009.394
[20]	Berat Karaagac. Numerical treatment of Gray-Scott model with operator splitting method. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2373-2386. doi: 10.3934/dcdss.2020143

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Stefan Klus Christof Schütte
on Google Scholar
Stefan Klus Christof Schütte

[Back to Top]