We address the problem of the stability of the computations of resultants and subresultants of polynomials defined over complete discrete valuation rings (e.g. or where 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 -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. ou où 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 -adiques aléatoires unitaires de même degré.
Revised:
Accepted:
Published online:
Keywords: Euclidean algorithm, ultrametric precision, subresultants
Xavier Caruso 1
CC-BY-ND 4.0
@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, Volume 29 (2017) no. 2, pp. 503-534. doi : 10.5802/jtnb.989. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.989/
[1] The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, 1976, xiv+255 pages
[2] Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, 10, Springer, 2006, x+662 pages
[3] The Magma algebra system. I. The user language., J. Symb. Comput., Volume 24 (1997) no. 3-4, pp. 235-265 | DOI
[4] From Newton sums to coefficients: complexity issues in characteristic , MEGA’05 (2005)
[5] Random matrices over a DVR and LU factorization, J. Symb. Comput., Volume 71 (2015), pp. 98-123 | DOI
[6] Computations with -adic numbers (2017) (preprint)
[7] Tracking -adic precision, LMS J. Comput. Math., Volume 17A (2014), pp. 274-294 | DOI
[8] A course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, 138, Springer, 1993, xxi+534 pages
[9] 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] Two specifications for -adic floating-point arithmetic: a Sage enhancement proposal (personal communication)
[11] On -adic differential equations with separation of variables (2016) (preprint)
[12] PARI/GP version 2.9.0, 2016 (available from http://pari.math.u-bordeaux.fr/)
[13] SageMath, the Sage Mathematics Software System (Version 7.5.1), 2016 (http://www.sagemath.org/)
[14] Polynomial Algorithms in Computer Algebra, Texts and Monographs in Symbolic Computation, Springer, 1996, vii+272 pages
Cited by Sources: