Search the site

Xavier Caruso
Numerical stability of Euclidean algorithm over ultrametric fields
Journal de théorie des nombres de Bordeaux, 29 no. 2 (2017), p. 503-534, doi: 10.5802/jtnb.989
Article PDF
Class. Math.: 11S99, 11Y99, 68W30
Keywords: Euclidean algorithm, ultrametric precision, subresultants

Résumé - Abstract

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{[\hspace{-1.49994pt}[} t{]\hspace{-1.4444pt}]}$ 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.

Bibliography

[1] George E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, 1976
[2] Saugata Basu, Richard Pollack & Marie-Françoise Roy, Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics 10, Springer, 2006
[3] Wieb Bosma, John Cannon & Catherine Playoust, The Magma algebra system. I. The user language., J. Symb. Comput. 24 (1997), p. 235-265 Article
[4] Alin Bostan, Laureano González-Vega, Hervé Perdry & Éric Schost, From Newton sums to coefficients: complexity issues in characteristic $p$, in MEGA’05, 2005
[5] Xavier Caruso, Random matrices over a DVR and LU factorization, J. Symb. Comput. 71 (2015), p. 98-123 Article |  MR 3345317
[6] Xavier Caruso, “Computations with $p$-adic numbers”, preprint, 2017
[7] Xavier Caruso, David Roe & Tristan Vaccon, Tracking $p$-adic precision, LMS J. Comput. Math. 17A (2014), p. 274-294 Article
[8] Henri Cohen, A course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer, 1993
[9] Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky–Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), p. 323-338
[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”, preprint, 2016
[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