staple
Avec cedram.org

Rechercher dans le site

Table des matières de ce fascicule | Article précédent | Article suivant
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
Mots clés: Euclidean algorithm, ultrametric precision, subresultants

Résumé - Abstract

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

Bibliographie

[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