American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Grid refinement in the construction of Lyapunov functions using radial basis functions
  • DCDS-B Home
  • This Issue
  • Next Article
    Polynomial optimization with applications to stability analysis and control - Alternatives to sum of squares
October  2015, 20(8): 2419-2451. doi: 10.3934/dcdsb.2015.20.2419

Efficient computation of Lyapunov functions for Morse decompositions

Arnaud Goullet 1, , Shaun Harker 1, , Konstantin Mischaikow 1, , William D. Kalies 2, and  Dinesh Kasti 3,

1. 

Rutgers University, 110 Frelinghusen Road, Piscataway, NJ 08854, United States, United States
2. 

Department of Mathematical Sciences, Florida Atlantic University, 777 Glades Road, 33431 Boca Raton
3. 

Florida Atlantic University, 777 Glades Road, Boca Raton, FL 33431, United States

Received  June 2014 Revised  February 2015 Published  August 2015

We present an efficient algorithm for constructing piecewise constant Lyapunov functions for dynamics generated by a continuous nonlinear map defined on a compact metric space. We provide a memory efficient data structure for storing nonuniform grids on which the Lyapunov function is defined and give bounds on the complexity of the algorithm for both time and memory. We prove that if the diameters of the grid elements go to zero, then the sequence of piecewise constant Lyapunov functions generated by our algorithm converge to a continuous Lyapunov function for the dynamics generated the nonlinear map. We conclude by applying these techniques to two problems from population biology.
Keywords: combinatorial dynamics, Morse decomposition, Conley's decomposition theorem, algorithms., Lyapunov function.
Mathematics Subject Classification: Primary: 37B25; Secondary: 37B30, 37B35, 37M9.
Citation: Arnaud Goullet, Shaun Harker, Konstantin Mischaikow, William D. Kalies, Dinesh Kasti. Efficient computation of Lyapunov functions for Morse decompositions. Discrete and Continuous Dynamical Systems - B, 2015, 20 (8) : 2419-2451. doi: 10.3934/dcdsb.2015.20.2419
References:
[1]

Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka and P. Pilarczyk, A database schema for the analysis of global dynamics of multiparameter systems, SIAM Journal on Applied Dynamical Systems, 8 (2009), 757-789. doi: 10.1137/080734935.

[2]

L. Arge, The buffer tree: A technique for designing batched external data structures, Algorithmica, 37 (2003), 1-24. doi: 10.1007/s00453-003-1021-x.

[3]

H. Ban and W. D. Kalies, A computational approach to Conley's decomposition theorem, Journal of Computational Nonlinear Dynamics, 1 (2006), 312-319. doi: 10.1115/1.2338651.

[4]

J. Bush, M. Gameiro, S. Harker, H. Kokubu, K. Mischaikow, I. Obayashi and P. Pilarczyk, Combinatorial-topological framework for the analysis of global dynamics, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 (2012), 047508. doi: 10.1063/1.4767672.

[5]

F. Claude and G. Navarro, Practical rank/select queries over arbitrary sequences, in String Processing and Information Retrieval, Lecture Notes in Comput. Sci., 5280, Springer, Berlin, 2008, 176-187. doi: 10.1007/978-3-540-89097-3_18.

[6]

C. Conley, Isolated Invariant Sets and the Morse Index, CBMS Regional Conference Series in Mathematics, 38, American Mathematical Society, Providence, R.I., 1978.

[7]

J. M. Cushing, S. Levarge, N. Chitnis and S. M. Henson, Some discrete competition models and the competitive exclusion principle, Journal of difference Equations and Applications, 10 (2004), 1139-1151. doi: 10.1080/10236190410001652739.

[8]

E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische mathematik, 1 (1959), 269-271. doi: 10.1007/BF01386390.

[9]

M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), 34 (1987), 596-615. doi: 10.1145/28869.28874.

[10]

S. Gog, T. Beller, A. Moffat and M. Petri, From theory to practice: Plug and play with succinct data structures, in Experimental Algorithms, Lecture Notes in Computer Science, 8504, Springer International Publishing, Switzerland, 2014, 326-337. doi: 10.1007/978-3-319-07959-2_28.

[11]

A. Goullet, S. Harker, D. Kasti, W. Kalies and K. Mischaikow, Supplementary materials, http://chomp.rutgers.edu/Archives/Lyapunov/SupplementalMaterials.html, 2014.

[12]

S. Harker, Space efficient variants of Tarjan's algorithm for strongly connected components, 2014.

[13]

S, Harker and A, Goullet, et al., Conley-Morse-Database software package, 2014.

[14]

G. Jacobson, Space-efficient static trees and graphs, in Foundations of Computer Science, 1989., 30th Annual Symposium on, IEEE, 1989, 549-554. doi: 10.1109/SFCS.1989.63533.

[15]

J. Jansson, K. Sadakane and W.-K. Sung, Ultra-succinct representation of ordered trees with applications, Journal of Computer and System Sciences, 78 (2012), 619-631. doi: 10.1016/j.jcss.2011.09.002.

[16]

B. Jiang, I/O-and CPU-optimal recognition of strongly connected components, Information Processing Letters, 45 (1993), 111-115. doi: 10.1016/0020-0190(93)90011-W.

[17]

W. D. Kalies, K. Mischaikow, and R. C. A. M. VanderVorst, An algorithmic approach to chain recurrence, Found. Comput. Math., 5 (2005), 409-449. doi: 10.1007/s10208-004-0163-9.

[18]

W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, Lattice structures for attractors I, Journal of Computational Dynamics, 2014.

[19]

W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, Lattice structures for attractors II, in preparation, 2014.

[20]

W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, Lattice structures for attractors III, in preparation, 2014.

[21]

R. P. McGehee and T. Wiandt, Conley decomposition for closed relations, J. Difference Equ. Appl., 12 (2006), 1-47. doi: 10.1080/00207210500171620.

[22]

R. McGehee, Attractors for closed relations on compact Hausdorff spaces, Indiana Univ. Math. J., 41 (1992), 1165-1209. doi: 10.1512/iumj.1992.41.41058.

[23]

J. I. Munro and V. Raman, Succinct representation of balanced parentheses and static trees, SIAM Journal on Computing, 31 (2001), 762-776. doi: 10.1137/S0097539799364092.

[24]

R. C. Robinson, An Introduction to Dynamical Systems-Continuous and Discrete, Second edition, Pure and Applied Undergraduate Texts, 19, American Mathematical Society, Providence, RI, 2012.

[25]

A. Szymczak, A combinatorial procedure for finding isolating neighbourhoods and index pairs, Proc. Roy. Soc. Edinburgh Sect. A, 127 (1997), 1075-1088. doi: 10.1017/S0308210500026901.

[26]

R. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1 (1972), 146-160. doi: 10.1137/0201010.

[27]

I. Ugarcovici and H. Weiss, Chaotic dynamics of a nonlinear density dependent population model, Nonlinearity, 17 (2004), 1689-1711. doi: 10.1088/0951-7715/17/5/007.

[28]

J. S. Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, 2 (2008), 305-474. doi: 10.1561/0400000014.

[29]

T. Wiandt, Liapunov functions for closed relations, J. Difference Equ. Appl., 14 (2008), 705-722. doi: 10.1080/10236190701809315.

show all references

References:
[1]

Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka and P. Pilarczyk, A database schema for the analysis of global dynamics of multiparameter systems, SIAM Journal on Applied Dynamical Systems, 8 (2009), 757-789. doi: 10.1137/080734935.

[2]

L. Arge, The buffer tree: A technique for designing batched external data structures, Algorithmica, 37 (2003), 1-24. doi: 10.1007/s00453-003-1021-x.

[3]

H. Ban and W. D. Kalies, A computational approach to Conley's decomposition theorem, Journal of Computational Nonlinear Dynamics, 1 (2006), 312-319. doi: 10.1115/1.2338651.

[4]

J. Bush, M. Gameiro, S. Harker, H. Kokubu, K. Mischaikow, I. Obayashi and P. Pilarczyk, Combinatorial-topological framework for the analysis of global dynamics, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22 (2012), 047508. doi: 10.1063/1.4767672.

[5]

F. Claude and G. Navarro, Practical rank/select queries over arbitrary sequences, in String Processing and Information Retrieval, Lecture Notes in Comput. Sci., 5280, Springer, Berlin, 2008, 176-187. doi: 10.1007/978-3-540-89097-3_18.

[6]

C. Conley, Isolated Invariant Sets and the Morse Index, CBMS Regional Conference Series in Mathematics, 38, American Mathematical Society, Providence, R.I., 1978.

[7]

J. M. Cushing, S. Levarge, N. Chitnis and S. M. Henson, Some discrete competition models and the competitive exclusion principle, Journal of difference Equations and Applications, 10 (2004), 1139-1151. doi: 10.1080/10236190410001652739.

[8]

E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische mathematik, 1 (1959), 269-271. doi: 10.1007/BF01386390.

[9]

M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), 34 (1987), 596-615. doi: 10.1145/28869.28874.

[10]

S. Gog, T. Beller, A. Moffat and M. Petri, From theory to practice: Plug and play with succinct data structures, in Experimental Algorithms, Lecture Notes in Computer Science, 8504, Springer International Publishing, Switzerland, 2014, 326-337. doi: 10.1007/978-3-319-07959-2_28.

[11]

A. Goullet, S. Harker, D. Kasti, W. Kalies and K. Mischaikow, Supplementary materials, http://chomp.rutgers.edu/Archives/Lyapunov/SupplementalMaterials.html, 2014.

[12]

S. Harker, Space efficient variants of Tarjan's algorithm for strongly connected components, 2014.

[13]

S, Harker and A, Goullet, et al., Conley-Morse-Database software package, 2014.

[14]

G. Jacobson, Space-efficient static trees and graphs, in Foundations of Computer Science, 1989., 30th Annual Symposium on, IEEE, 1989, 549-554. doi: 10.1109/SFCS.1989.63533.

[15]

J. Jansson, K. Sadakane and W.-K. Sung, Ultra-succinct representation of ordered trees with applications, Journal of Computer and System Sciences, 78 (2012), 619-631. doi: 10.1016/j.jcss.2011.09.002.

[16]

B. Jiang, I/O-and CPU-optimal recognition of strongly connected components, Information Processing Letters, 45 (1993), 111-115. doi: 10.1016/0020-0190(93)90011-W.

[17]

W. D. Kalies, K. Mischaikow, and R. C. A. M. VanderVorst, An algorithmic approach to chain recurrence, Found. Comput. Math., 5 (2005), 409-449. doi: 10.1007/s10208-004-0163-9.

[18]

W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, Lattice structures for attractors I, Journal of Computational Dynamics, 2014.

[19]

W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, Lattice structures for attractors II, in preparation, 2014.

[20]

W. D. Kalies, K. Mischaikow and R. C. A. M. VanderVorst, Lattice structures for attractors III, in preparation, 2014.

[21]

R. P. McGehee and T. Wiandt, Conley decomposition for closed relations, J. Difference Equ. Appl., 12 (2006), 1-47. doi: 10.1080/00207210500171620.

[22]

R. McGehee, Attractors for closed relations on compact Hausdorff spaces, Indiana Univ. Math. J., 41 (1992), 1165-1209. doi: 10.1512/iumj.1992.41.41058.

[23]

J. I. Munro and V. Raman, Succinct representation of balanced parentheses and static trees, SIAM Journal on Computing, 31 (2001), 762-776. doi: 10.1137/S0097539799364092.

[24]

R. C. Robinson, An Introduction to Dynamical Systems-Continuous and Discrete, Second edition, Pure and Applied Undergraduate Texts, 19, American Mathematical Society, Providence, RI, 2012.

[25]

A. Szymczak, A combinatorial procedure for finding isolating neighbourhoods and index pairs, Proc. Roy. Soc. Edinburgh Sect. A, 127 (1997), 1075-1088. doi: 10.1017/S0308210500026901.

[26]

R. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1 (1972), 146-160. doi: 10.1137/0201010.

[27]

I. Ugarcovici and H. Weiss, Chaotic dynamics of a nonlinear density dependent population model, Nonlinearity, 17 (2004), 1689-1711. doi: 10.1088/0951-7715/17/5/007.

[28]

J. S. Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, 2 (2008), 305-474. doi: 10.1561/0400000014.

[29]

T. Wiandt, Liapunov functions for closed relations, J. Difference Equ. Appl., 14 (2008), 705-722. doi: 10.1080/10236190701809315.

[1]

Mauro Patrão, Luiz A. B. San Martin. Morse decomposition of semiflows on fiber bundles. Discrete and Continuous Dynamical Systems, 2007, 17 (3) : 561-587. doi: 10.3934/dcds.2007.17.561
[2]

Stefano Bianchini, Daniela Tonon. A decomposition theorem for $BV$ functions. Communications on Pure and Applied Analysis, 2011, 10 (6) : 1549-1566. doi: 10.3934/cpaa.2011.10.1549
[3]

Hahng-Yun Chu, Se-Hyun Ku, Jong-Suh Park. Conley's theorem for dispersive systems. Discrete and Continuous Dynamical Systems - S, 2015, 8 (2) : 313-321. doi: 10.3934/dcdss.2015.8.313
[4]

Tomás Caraballo, Juan C. Jara, José A. Langa, José Valero. Morse decomposition of global attractors with infinite components. Discrete and Continuous Dynamical Systems, 2015, 35 (7) : 2845-2861. doi: 10.3934/dcds.2015.35.2845
[5]

Tomoharu Suda. Construction of Lyapunov functions using Helmholtz–Hodge decomposition. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2437-2454. doi: 10.3934/dcds.2019103
[6]

Thiago Ferraiol, Mauro Patrão, Lucas Seco. Jordan decomposition and dynamics on flag manifolds. Discrete and Continuous Dynamical Systems, 2010, 26 (3) : 923-947. doi: 10.3934/dcds.2010.26.923
[7]

Yifan Xu. Algorithms by layer-decomposition for the subgraph recognition problem with attributes. Journal of Industrial and Management Optimization, 2005, 1 (3) : 337-343. doi: 10.3934/jimo.2005.1.337
[8]

Carlos Conca, Luis Friz, Jaime H. Ortega. Direct integral decomposition for periodic function spaces and application to Bloch waves. Networks and Heterogeneous Media, 2008, 3 (3) : 555-566. doi: 10.3934/nhm.2008.3.555
[9]

Yejuan Wang, Tomás Caraballo. Morse decomposition for gradient-like multi-valued autonomous and nonautonomous dynamical systems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (8) : 2303-2326. doi: 10.3934/dcdss.2020092
[10]

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
[11]

Janusz Mierczyński, Sylvia Novo, Rafael Obaya. Lyapunov exponents and Oseledets decomposition in random dynamical systems generated by systems of delay differential equations. Communications on Pure and Applied Analysis, 2020, 19 (4) : 2235-2255. doi: 10.3934/cpaa.2020098
[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]

Quentin De Mourgues. A combinatorial approach to Rauzy-type dynamics II: The labelling method and a second proof of the KZB classification theorem. Discrete and Continuous Dynamical Systems, 2022, 42 (7) : 3465-3538. doi: 10.3934/dcds.2022022
[14]

Konstantin Mischaikow, Marian Mrozek, Frank Weilandt. Discretization strategies for computing Conley indices and Morse decompositions of flows. Journal of Computational Dynamics, 2016, 3 (1) : 1-16. doi: 10.3934/jcd.2016001
[15]

M. C. Carbinatto, K. Mischaikow. Horseshoes and the Conley index spectrum - II: the theorem is sharp. Discrete and Continuous Dynamical Systems, 1999, 5 (3) : 599-616. doi: 10.3934/dcds.1999.5.599
[16]

Antonio Siconolfi, Gabriele Terrone. A metric proof of the converse Lyapunov theorem for semicontinuous multivalued dynamics. Discrete and Continuous Dynamical Systems, 2012, 32 (12) : 4409-4427. doi: 10.3934/dcds.2012.32.4409
[17]

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
[18]

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
[19]

Fritz Colonius, Paulo Régis C. Ruffino. Nonlinear Iwasawa decomposition of control flows. Discrete and Continuous Dynamical Systems, 2007, 18 (2&3) : 339-354. doi: 10.3934/dcds.2007.18.339
[20]

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

2021 Impact Factor: 1.497

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy