February  2006, 15(1): 281-352. doi: 10.3934/dcds.2006.15.281

Euclidean dynamics

1. 

GREYC, UMR CNRS 6072, University of Caen, Batiment Sciences 3, Campus II, F-14032 Caen, France

Received  December 2004 Revised  October 2005 Published  February 2006

We study a general class of Euclidean algorithms which compute the greatest common divisor [gcd], and we perform probabilistic analyses of their main parameters. We view an algorithm as a dynamical system restricted to rational inputs, and combine tools imported from dynamics, such as transfer operators, with various tools of analytic combinatorics: generating functions, Dirichlet series, Tauberian theorems, Perron's formula and quasi-powers theorems. Such dynamical analyses can be used to perform the average-case analysis of algorithms, but also (dynamical) analysis in distribution.
Citation: Brigitte Vallée. Euclidean dynamics. Discrete & Continuous Dynamical Systems - A, 2006, 15 (1) : 281-352. doi: 10.3934/dcds.2006.15.281
[1]

Bin Wang, Arieh Iserles. Dirichlet series for dynamical systems of first-order ordinary differential equations. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 281-298. doi: 10.3934/dcdsb.2014.19.281

[2]

Chantelle Blachut, Cecilia González-Tokman. A tale of two vortices: How numerical ergodic theory and transfer operators reveal fundamental changes to coherent structures in non-autonomous dynamical systems. Journal of Computational Dynamics, 2020, 7 (2) : 369-399. doi: 10.3934/jcd.2020015

[3]

Annalisa Pascarella, Alberto Sorrentino, Cristina Campi, Michele Piana. Particle filtering, beamforming and multiple signal classification for the analysis of magnetoencephalography time series: a comparison of algorithms. Inverse Problems & Imaging, 2010, 4 (1) : 169-190. doi: 10.3934/ipi.2010.4.169

[4]

Xiaoming Wang. Numerical algorithms for stationary statistical properties of dissipative dynamical systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4599-4618. doi: 10.3934/dcds.2016.36.4599

[5]

Marta Štefánková. Inheriting of chaos in uniformly convergent nonautonomous dynamical systems on the interval. Discrete & Continuous Dynamical Systems - A, 2016, 36 (6) : 3435-3443. doi: 10.3934/dcds.2016.36.3435

[6]

Frédéric Naud. The Ruelle spectrum of generic transfer operators. Discrete & Continuous Dynamical Systems - A, 2012, 32 (7) : 2521-2531. doi: 10.3934/dcds.2012.32.2521

[7]

Boris Paneah. Noncommutative dynamical systems with two generators and their applications in analysis. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1411-1422. doi: 10.3934/dcds.2003.9.1411

[8]

Gary Froyland, Ognjen Stancevic. Escape rates and Perron-Frobenius operators: Open and closed dynamical systems. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 457-472. doi: 10.3934/dcdsb.2010.14.457

[9]

Robert Stephen Cantrell, Suzanne Lenhart, Yuan Lou, Shigui Ruan. Preface on the special issue of Discrete and Continuous Dynamical Systems- Series B in honor of Chris Cosner on the occasion of his 60th birthday. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : i-ii. doi: 10.3934/dcdsb.2014.19.1i

[10]

Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 581-598. doi: 10.3934/dcds.2004.11.581

[11]

Damien Thomine. A spectral gap for transfer operators of piecewise expanding maps. Discrete & Continuous Dynamical Systems - A, 2011, 30 (3) : 917-944. doi: 10.3934/dcds.2011.30.917

[12]

Vesselin Petkov, Luchezar Stoyanov. Ruelle transfer operators with two complex parameters and applications. Discrete & Continuous Dynamical Systems - A, 2016, 36 (11) : 6413-6451. doi: 10.3934/dcds.2016077

[13]

Matthew M. Dunlop, Andrew M. Stuart. The Bayesian formulation of EIT: Analysis and algorithms. Inverse Problems & Imaging, 2016, 10 (4) : 1007-1036. doi: 10.3934/ipi.2016030

[14]

Isabeau Birindelli, Francoise Demengel. The dirichlet problem for singluar fully nonlinear operators. Conference Publications, 2007, 2007 (Special) : 110-121. doi: 10.3934/proc.2007.2007.110

[15]

Oktay Veliev. Spectral expansion series with parenthesis for the nonself-adjoint periodic differential operators. Communications on Pure & Applied Analysis, 2019, 18 (1) : 397-424. doi: 10.3934/cpaa.2019020

[16]

Hui Li, Manjun Ma. Corrigendum on “H. Li and M. Ma, global dynamics of a virus infection model with repulsive effect, Discrete and Continuous Dynamical Systems, Series B, 24(9) 4783-4797, 2019”. Discrete & Continuous Dynamical Systems - B, 2020, 25 (12) : 4925-4925. doi: 10.3934/dcdsb.2020299

[17]

Mark F. Demers, Hong-Kun Zhang. Spectral analysis of the transfer operator for the Lorentz gas. Journal of Modern Dynamics, 2011, 5 (4) : 665-709. doi: 10.3934/jmd.2011.5.665

[18]

Dong Han Kim. The dynamical Borel-Cantelli lemma for interval maps. Discrete & Continuous Dynamical Systems - A, 2007, 17 (4) : 891-900. doi: 10.3934/dcds.2007.17.891

[19]

Gary Froyland, Cecilia González-Tokman, Anthony Quas. Detecting isolated spectrum of transfer and Koopman operators with Fourier analytic tools. Journal of Computational Dynamics, 2014, 1 (2) : 249-278. doi: 10.3934/jcd.2014.1.249

[20]

Doug Hensley. Continued fractions, Cantor sets, Hausdorff dimension, and transfer operators and their analytic extension. Discrete & Continuous Dynamical Systems - A, 2012, 32 (7) : 2417-2436. doi: 10.3934/dcds.2012.32.2417

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (66)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]