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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

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

[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.  Google Scholar

[8]

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

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[12]

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

[13]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[19]

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

[20]

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

[21]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[26]

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

[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.  Google Scholar

[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.  Google Scholar

[29]

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

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

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

[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.  Google Scholar

[8]

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

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[12]

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

[13]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[19]

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

[20]

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

[21]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[26]

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

[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.  Google Scholar

[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.  Google Scholar

[29]

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

[1]

Mauro Patrão, Luiz A. B. San Martin. Morse decomposition of semiflows on fiber bundles. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Applied Analysis, 2020, 19 (4) : 2235-2255. doi: 10.3934/cpaa.2020098
[12]

Siwei Yu, Jianwei Ma, Stanley Osher. Geometric mode decomposition. Inverse Problems & Imaging, 2018, 12 (4) : 831-852. doi: 10.3934/ipi.2018035
[13]

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

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

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

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

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

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

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

Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057

2020 Impact Factor: 1.327

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences