Computational complexity of iterated maps on the interval

DOI10.1016/J.MATCOM.2012.02.003zbMATH Open1286.37066arXiv1003.6036OpenAlexW1562871781MaRDI QIDQ449664FDOQ449664

Authors: Christoph Spandl 

Publication date: 31 August 2012

Published in: Mathematics and Computers in Simulation (Search for Journal in Brave)

Abstract: The correct computation of orbits of discrete dynamical systems on the interval is considered. Therefore, an arbitrary-precision floating-point approach based on automatic error analysis is chosen and a general algorithm is presented. The correctness of the algorithm is shown and the computational complexity is analyzed. There are two main results. First, the computational complexity measure considered here is related to the Lyapunov exponent of the dynamical system under consideration. Second, the presented algorithm is optimal with regard to that complexity measure.

Full work available at URL: https://arxiv.org/abs/1003.6036

Recommendations

• Computational complexity of iterated maps on the interval (extended abstract)
• Efficient exact computation of iterated maps
• Exact numerical methods in dynamical systems theory
• Publication:5748834
• scientific article; zbMATH DE number 1282264

zbMATH Keywords

discrete dynamical systemsLyapunov exponentarbitrary-precision floating-point arithmetic

Mathematics Subject Classification ID

Numerical chaos (65P20) Simulation of dynamical systems (37M05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• MPFR
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Accuracy and Stability of Numerical Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the abundance of aperiodic behaviour for maps on the interval
• Do numerical orbits of chaotic dynamical processes represent true orbits?
• Fast and parallel interval arithmetic
• Rigorous verification of trajectories for the computer simulation of dynamical systems
• Shadowing of physical trajectories in chaotic dynamics: Containment and refinement
• Rigorous chaos verification in discrete dynamical systems
• Motivations for an arbitrary precision interval arithmetic and the MPFI library
• Precise numerical computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Feasible real random access machines
• Efficient exact computation of iterated maps
• Significance arithmetic: The carrying algorithm
• Exact real arithmetic using centred intervals and bounded error terms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Concepts and results in chaotic dynamics. A short course

Cited In (9)

• Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
• Computing with dynamical systems
• Computational complexity of iterated maps on the interval (extended abstract)
• On the complexity of fitted toral dynamics
• The computational complexity of the Needing invariant of explosive maps of the interval
• On the complexity of Anosov saddle transitions
• Efficient exact computation of iterated maps
• Title not available (Why is that?)
• Interval computing periodic orbits of maps using a piecewise approach

Uses Software

• MPFI
• MPFR
• mctoolbox
• iRRAM

This page was built for publication: Computational complexity of iterated maps on the interval

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q449664)