Numerical stability of Euclidean algorithm over ultrametric fields
Xavier Caruso1
1 Université Rennes 1, IRMAR 35042 Rennes Cedex, France
Journal de théorie des nombres de Bordeaux, Tome 29 (2017) no. 2, pp. 503-534.

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.

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]] où 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é.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/jtnb.989
Classification : 11S99, 11Y99, 68W30
Keywords: Euclidean algorithm, ultrametric precision, subresultants

Xavier Caruso 1

1 Université Rennes 1, IRMAR 35042 Rennes Cedex, France
Licence : CC-BY-ND 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@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/}
}
TY  - JOUR
AU  - Xavier Caruso
TI  - Numerical stability of Euclidean algorithm  over ultrametric fields
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2017
SP  - 503
EP  - 534
VL  - 29
IS  - 2
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.989/
DO  - 10.5802/jtnb.989
LA  - en
ID  - JTNB_2017__29_2_503_0
ER  - 
%0 Journal Article
%A Xavier Caruso
%T Numerical stability of Euclidean algorithm  over ultrametric fields
%J Journal de théorie des nombres de Bordeaux
%D 2017
%P 503-534
%V 29
%N 2
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.989/
%R 10.5802/jtnb.989
%G en
%F JTNB_2017__29_2_503_0
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, 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 | DOI

[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 | DOI

[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 | DOI

[8] Henri Cohen A course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, 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

Cité par Sources :