Quadratic dynamical systems
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 304-313
- https://doi.org/10.1109/sfcs.1992.267761
Abstract
The paper promotes the study of computational aspects, primarily the convergence rate, of nonlinear dynamical systems from a combinatorial perspective. The authors identify the class of symmetric quadratic systems. Such systems have been widely used to model phenomena in the natural sciences, and also provide an appropriate framework for the study of genetic algorithms in combinatorial optimisation. They prove several fundamental general properties of these systems, notably that every trajectory converges to a fixed point. They go on to give a detailed analysis of a quadratic system defined in a natural way on probability distributions over the set of matchings in a graph. In particular, they prove that convergence to the limit requires only polynomial time when the graph is a tree. This result demonstrates that such systems, though nonlinear, are amenable to quantitative analysis.Keywords
This publication has 8 references indexed in Scilit:
- Adaptation in Natural and Artificial SystemsPublished by MIT Press ,1992
- Quadratic dynamical systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Approximating the PermanentSIAM Journal on Computing, 1989
- A random polynomial time algorithm for approximating the volume of convex bodiesPublished by Association for Computing Machinery (ACM) ,1989
- The time complexity of maximum matching by simulated annealingJournal of the ACM, 1988
- Deterministic simulation in LOGSPACEPublished by Association for Computing Machinery (ACM) ,1987
- Quadratic transformations: a model for population growth. IAdvances in Applied Probability, 1970