Numerical stability of Euclidean algorithm over ultrametric fields

Caruso, Xavier

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. ${\mathbb{Z}}_p$ ou $k\left[\right[t\left]\right]$ 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é.

We address the problem of the stability of the computations of resultants and subresultants of polynomials defined over complete discrete valuation rings (e.g. ${\mathbb{Z}}_p$ or $k\left[\right[t\left]\right]$ 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.

Classification : 11S99, 11Y99, 68W30
Mots clés : Euclidean algorithm, ultrametric precision, subresultants

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

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

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

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

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

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

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

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

[9] Kedlaya, Kiran S. 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] Kedlaya, Kiran S.; Roe, David Two specifications for $p$-adic floating-point arithmetic: a Sage enhancement proposal (personal communication)

[11] Lairez, Pierre; Vaccon, Tristan 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] Winkler, Franz Polynomial Algorithms in Computer Algebra, Texts and Monographs in Symbolic Computation, Springer, 1996, vii+272 pages