Analysis of generalized continued fraction algorithms over polynomials

DOI10.1016/J.FFA.2021.101849MaRDI QIDQ2031651zbMATH OpenOpenAlexFDO

Authors Hitoshi Nakada, Rie Natsui, Valérie Berthé, Brigitte Vallée

Publication date 10 June 2021

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ffa.2021.101849

zbMATH Keywords

analytic combinatoricscosts and bit-complexitiesdynamical systemsGaussian lawsgcd algorithms for polynomials over finite fieldsgenerating functionsHaar measureLaurent formal power seriesmultidimensional continued fractionstransfer operators

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Continued fractions and generalizations (11J70) Metric theory of continued fractions (11K50) Metric theory of other algorithms and expansions; measure and Hausdorff dimension (11K55) Relations between ergodic theory and number theory (37A44) Analysis of algorithms (68W40)

Review text

Its well knew that the greatest common divisor (gcd) computation for univariate polynomials is a basic operation in computer algebra and Euclid's algorithm completely solves the problem of gcd computation for two entries. However, there does not exist a canonical generalization of Euclid's algorithm when working with at least three entries. Three generalized Euclidean algorithms for polynomials with coefficients in a finite field, inspired by classical multidimensional continued fraction maps, namely the Jacobi-Perron, the Brun, and the fully subtractive maps were chosen and compared in this paper. The two-dimensional versions of the Jacobi-Perron, the Brun, and the fully subtractive algorithms are associated with continued fraction maps. A unified framework for these algorithms and their associated continued fraction maps are provided. The convergence of the continued fraction maps was discussed. The bivariate generating functions are the main tool of the study. This enables in particular to exhibit asymptotic Gaussian laws. The various costs for the gcd algorithms, including the number of iterations and two versions of the bit-complexity, corresponding to two representations of polynomials analyzed in the paper. The associated two-dimensional continued fraction maps are studied and the invariance and the ergodicity of the Haar measure are proved. The authors obtain corresponding estimates for the costs of truncated trajectories under the action of these continued fraction maps and are compared the two models (gcd algorithms and their associated continued fraction maps).

Recommendations

• Fine costs for Euclid's algorithm on polynomials and Farey maps
• The Computational Complexity of Continued Fractions
• Analysis of Euclidean algorithms for polynomials over finite fields
• Continued fraction algorithms, functional operators, and structure constants
• Gaussian laws for the main parameters of the Euclid algorithms

Cites work

• Analytic combinatorics
• Convergence of the Brun algorithm over the field of formal power series
• Euclidean algorithms are Gaussian
• Euclidean dynamics
• Fine costs for Euclid's algorithm on polynomials and Farey maps
• Gaussian laws for the main parameters of the Euclid algorithms
• scientific article; zbMATH DE number 3615363 (Why is no real title available?)
• scientific article; zbMATH DE number 3622081 (Why is no real title available?)
• scientific article; zbMATH DE number 579715 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 2065019 (Why is no real title available?)
• scientific article; zbMATH DE number 1503600 (Why is no real title available?)
• scientific article; zbMATH DE number 1516956 (Why is no real title available?)
• scientific article; zbMATH DE number 3273002 (Why is no real title available?)
• scientific article; zbMATH DE number 3337789 (Why is no real title available?)
• scientific article; zbMATH DE number 3401014 (Why is no real title available?)
• Interval exchange transformations
• Metric properties and exceptional sets of \(\beta \)-expansions over formal Laurent series
• Non-negative matrices and Markov chains. 2nd ed
• On continued fraction expansions in positive characteristic: equivalence relations and some metric properties
• On convergence rates in the central limit theorems for combinatorial structures
• On Schweiger's problems on fully subtractive algorithms
• On the sum of degrees of digits occurring in continued fraction expansions of Laurent series
• On the thermodynamic formalism for the Gauss map
• Probabilistic analyses of the plain multiple gcd algorithm
• The Brun gcd algorithm in high dimensions is almost always subtractive
• The convergence of the generalised Selmer algorithm
• The exact length of the Euclidean algorithm in [ X ]
• The modified Jacobi-Perron algorithm over \(\mathbb F_q (X)^d\)
• The statistics of continued fractions for polynomials over a finite field
• The three-dimensional Poincaré continued fraction algorithm

Cited in

(8)

• The Brun gcd algorithm in high dimensions is almost always subtractive
• Analysis of performance of symmetric second-order line search algorithms through continued fractions
• Analysis of the Brun GCD algorithm
• The Computational Complexity of Continued Fractions
• An analysis of polynomial sequences and their application to discrete fractional operators
• Analysis and geometry of a GCD-algorithm
• On the continued fraction with rational partial quotients
• Analysis of Euclidean algorithms for polynomials over finite fields

This page was built for publication: Analysis of generalized continued fraction algorithms over polynomials

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