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

Efficient computation of Lyapunov functions for Morse decompositions

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

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

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

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

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

[6]

C. Conley, Isolated Invariant Sets and the Morse Index,, CBMS Regional Conference Series in Mathematics, (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. doi: 10.1080/10236190410001652739.

[8]

E. W. Dijkstra, A note on two problems in connexion with graphs,, Numerische mathematik, 1 (1959), 269. 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. 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, (8504), 326. doi: 10.1007/978-3-319-07959-2_28.

[11]

A. Goullet, S. Harker, D. Kasti, W. Kalies and K. Mischaikow, Supplementary materials,, , (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), 549. 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. 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. 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. 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. doi: 10.1080/00207210500171620.

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

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

[24]

R. C. Robinson, An Introduction to Dynamical Systems-Continuous and Discrete,, Second edition, (2012).

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

[26]

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

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

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

[29]

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

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

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

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

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

[6]

C. Conley, Isolated Invariant Sets and the Morse Index,, CBMS Regional Conference Series in Mathematics, (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. doi: 10.1080/10236190410001652739.

[8]

E. W. Dijkstra, A note on two problems in connexion with graphs,, Numerische mathematik, 1 (1959), 269. 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. 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, (8504), 326. doi: 10.1007/978-3-319-07959-2_28.

[11]

A. Goullet, S. Harker, D. Kasti, W. Kalies and K. Mischaikow, Supplementary materials,, , (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), 549. 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. 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. 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. 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. doi: 10.1080/00207210500171620.

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

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

[24]

R. C. Robinson, An Introduction to Dynamical Systems-Continuous and Discrete,, Second edition, (2012).

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

[26]

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

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

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

[29]

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

[1]

Mauro Patrão, Luiz A. B. San Martin. Morse decomposition of semiflows on fiber bundles. Discrete & Continuous Dynamical Systems - A, 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 - A, 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 - A, 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 - A, 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]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109

[18]

David Kazhdan and Yakov Varshavsky. Endoscopic decomposition of characters of certain cuspidal representations. Electronic Research Announcements, 2004, 10: 11-20.

[19]

Nataša Djurdjevac Conrad, Ralf Banisch, Christof Schütte. Modularity of directed networks: Cycle decomposition approach. Journal of Computational Dynamics, 2015, 2 (1) : 1-24. doi: 10.3934/jcd.2015.2.1

[20]

George Dassios, Michalis N. Tsampas. Vector ellipsoidal harmonics and neuronal current decomposition in the brain. Inverse Problems & Imaging, 2009, 3 (2) : 243-257. doi: 10.3934/ipi.2009.3.243

2018 Impact Factor: 1.008

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (2)

[Back to Top]