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.  doi: 10.1137/080734935.  Google Scholar

[2]

L. Arge, The buffer tree: A technique for designing batched external data structures,, Algorithmica, 37 (2003), 1.  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.  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).  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, (5280), 176.  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, (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.  doi: 10.1080/10236190410001652739.  Google Scholar

[8]

E. W. Dijkstra, A note on two problems in connexion with graphs,, Numerische mathematik, 1 (1959), 269.  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.  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, (8504), 326.  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,, , (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), 549.  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.  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.  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.  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.  doi: 10.1080/00207210500171620.  Google Scholar

[22]

R. McGehee, Attractors for closed relations on compact Hausdorff spaces,, Indiana Univ. Math. J., 41 (1992), 1165.  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.  doi: 10.1137/S0097539799364092.  Google Scholar

[24]

R. C. Robinson, An Introduction to Dynamical Systems-Continuous and Discrete,, Second edition, (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.  doi: 10.1017/S0308210500026901.  Google Scholar

[26]

R. Tarjan, Depth-first search and linear graph algorithms,, SIAM Journal on Computing, 1 (1972), 146.  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.  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.  doi: 10.1561/0400000014.  Google Scholar

[29]

T. Wiandt, Liapunov functions for closed relations,, J. Difference Equ. Appl., 14 (2008), 705.  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.  doi: 10.1137/080734935.  Google Scholar

[2]

L. Arge, The buffer tree: A technique for designing batched external data structures,, Algorithmica, 37 (2003), 1.  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.  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).  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, (5280), 176.  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, (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.  doi: 10.1080/10236190410001652739.  Google Scholar

[8]

E. W. Dijkstra, A note on two problems in connexion with graphs,, Numerische mathematik, 1 (1959), 269.  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.  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, (8504), 326.  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,, , (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), 549.  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.  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.  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.  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.  doi: 10.1080/00207210500171620.  Google Scholar

[22]

R. McGehee, Attractors for closed relations on compact Hausdorff spaces,, Indiana Univ. Math. J., 41 (1992), 1165.  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.  doi: 10.1137/S0097539799364092.  Google Scholar

[24]

R. C. Robinson, An Introduction to Dynamical Systems-Continuous and Discrete,, Second edition, (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.  doi: 10.1017/S0308210500026901.  Google Scholar

[26]

R. Tarjan, Depth-first search and linear graph algorithms,, SIAM Journal on Computing, 1 (1972), 146.  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.  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.  doi: 10.1561/0400000014.  Google Scholar

[29]

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

[1]

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

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

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076
[4]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374
[5]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006
[6]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378
[7]

Jing Qin, Shuang Li, Deanna Needell, Anna Ma, Rachel Grotheer, Chenxi Huang, Natalie Durgin. Stochastic greedy algorithms for multiple measurement vectors. Inverse Problems & Imaging, 2021, 15 (1) : 79-107. doi: 10.3934/ipi.2020066
[8]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331
[9]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[10]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[11]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[12]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363
[13]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276
[14]

Isabeau Birindelli, Françoise Demengel, Fabiana Leoni. Boundary asymptotics of the ergodic functions associated with fully nonlinear operators through a Liouville type theorem. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020395
[15]

Hong Fu, Mingwu Liu, Bo Chen. Supplier's investment in manufacturer's quality improvement with equity holding. Journal of Industrial & Management Optimization, 2021, 17 (2) : 649-668. doi: 10.3934/jimo.2019127
[16]

Skyler Simmons. Stability of broucke's isosceles orbit. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021015
[17]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443
[18]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[19]

François Ledrappier. Three problems solved by Sébastien Gouëzel. Journal of Modern Dynamics, 2020, 16: 373-387. doi: 10.3934/jmd.2020015
[20]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404

2019 Impact Factor: 1.27

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences