Numerical stability of Euclidean algorithm over ultrametric fields
Journal de Théorie des Nombres de Bordeaux, Tome 29 (2017) no. 2, pp. 503-534.

Nous étudions le problème de la stabilité du calcul des résultants et sous-résultants des polynômes définis sur des anneaux de valuation discrète complets (e.g. p ou k[[t]]k est un corps). Nous démontrons que les algorithmes de type Euclide sont très instables en moyenne et, dans de nombreux cas, nous expliquons comment les rendre stables sans dégrader la complexité. Chemin faisant, nous déterminons la loi de la valuation des sous-résultants de deux polynômes p-adiques aléatoires unitaires de même degré.

We address the problem of the stability of the computations of resultants and subresultants of polynomials defined over complete discrete valuation rings (e.g. p or k[[t]] where k is a field). We prove that Euclidean-like algorithms are highly unstable on average and we explain, in many cases, how one can stabilize them without sacrifying the complexity. On the way, we completely determine the distribution of the valuation of the subresultants of two random monic p-adic polynomials having the same degree.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.989
Classification : 11S99,  11Y99,  68W30
Mots clés : Euclidean algorithm, ultrametric precision, subresultants
@article{JTNB_2017__29_2_503_0,
     author = {Xavier Caruso},
     title = {Numerical stability of {Euclidean} algorithm  over ultrametric fields},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {503--534},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {29},
     number = {2},
     year = {2017},
     doi = {10.5802/jtnb.989},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.989/}
}
Xavier Caruso. Numerical stability of Euclidean algorithm  over ultrametric fields. Journal de Théorie des Nombres de Bordeaux, Tome 29 (2017) no. 2, pp. 503-534. doi : 10.5802/jtnb.989. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.989/

[1] George E. Andrews The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, 1976, xiv+255 pages

[2] Saugata Basu; Richard Pollack; Marie-Françoise Roy Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, Volume 10, Springer, 2006, x+662 pages

[3] Wieb Bosma; John Cannon; Catherine Playoust The Magma algebra system. I. The user language., J. Symb. Comput., Volume 24 (1997) no. 3-4, pp. 235-265 | Article

[4] Alin Bostan; Laureano González-Vega; Hervé Perdry; Éric Schost From Newton sums to coefficients: complexity issues in characteristic p, MEGA’05 (2005)

[5] Xavier Caruso Random matrices over a DVR and LU factorization, J. Symb. Comput., Volume 71 (2015), pp. 98-123 | Article

[6] Xavier Caruso Computations with p-adic numbers (2017) (preprint)

[7] Xavier Caruso; David Roe; Tristan Vaccon Tracking p-adic precision, LMS J. Comput. Math., Volume 17A (2014), pp. 274-294 | Article

[8] Henri Cohen A course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, Volume 138, Springer, 1993, xxi+534 pages

[9] Kiran S. Kedlaya Counting points on hyperelliptic curves using Monsky–Washnitzer cohomology, J. Ramanujan Math. Soc., Volume 16 (2001) no. 4, pp. 323-338 (errata in ibid., 18 (2003), no. 4, 417-418)

[10] Kiran S. Kedlaya; David Roe Two specifications for p-adic floating-point arithmetic: a Sage enhancement proposal (personal communication)

[11] Pierre Lairez; Tristan Vaccon On p-adic differential equations with separation of variables (2016) (preprint)

[12] The PARI Group PARI/GP version 2.9.0, 2016 (available from http://pari.math.u-bordeaux.fr/)

[13] The Sage Developers SageMath, the Sage Mathematics Software System (Version 7.5.1), 2016 (http://www.sagemath.org/)

[14] Franz Winkler Polynomial Algorithms in Computer Algebra, Texts and Monographs in Symbolic Computation, Springer, 1996, vii+272 pages