Let be a polynomial of total degree defined over a perfect field of characteristic zero or greater than . Assuming separable with respect to , we provide an algorithm that computes all singular parts of Puiseux series of above in an expected operations in , where is the valuation of the resultant of and its partial derivative with respect to . To this aim, we use a divide and conquer strategy and replace univariate factorisation by dynamic evaluation. As a first main corollary, we compute the irreducible factors of in up to an arbitrary precision with arithmetic operations. As a second main corollary, we compute the genus of the plane curve defined by with arithmetic operations and, if , with bit operations using probabilistic algorithms, where is the logarithmic height of .
Soit un polynôme de degré total défini au dessus d’un corps parfait de caractéristique zéro ou plus grande que . Sous l’hypothèse que est séparable par rapport à la variable , nous décrivons un algorithme qui calcule l’ensemble des parties singulières des séries de Puiseux de au-dessus de avec un nombre moyen d’opérations sur borné par , où est la valuation du résultant de et sa dérivée partielle en . Pour se faire, nous utilisons une stratégie de type “diviser pour régner” et nous remplaçons l’utilisation de factorisation univariée par l’évaluation dynamique. Comme premier corollaire principal, nous calculons les facteurs irréductibles de dans à precision en opérations arithmétiques. Comme second corollaire, nous calculons le genre de la courbe algébrique plane définie par en opérations arithmétiques, et, si , en opérations binaires via des algorithmes probabilites, où est la taille logarithmique de .
Revised:
Accepted:
Published online:
Mots-clés : Puiseux series, complexity, dynamic evaluation
@article{AHL_2021__4__1061_0, author = {Poteaux, Adrien and Weimann, Martin}, title = {Computing {Puiseux} series: a fast divide and conquer algorithm}, journal = {Annales Henri Lebesgue}, pages = {1061--1102}, publisher = {\'ENS Rennes}, volume = {4}, year = {2021}, doi = {10.5802/ahl.97}, language = {en}, url = {http://www.numdam.org/articles/10.5802/ahl.97/} }
TY - JOUR AU - Poteaux, Adrien AU - Weimann, Martin TI - Computing Puiseux series: a fast divide and conquer algorithm JO - Annales Henri Lebesgue PY - 2021 SP - 1061 EP - 1102 VL - 4 PB - ÉNS Rennes UR - http://www.numdam.org/articles/10.5802/ahl.97/ DO - 10.5802/ahl.97 LA - en ID - AHL_2021__4__1061_0 ER -
Poteaux, Adrien; Weimann, Martin. Computing Puiseux series: a fast divide and conquer algorithm. Annales Henri Lebesgue, Volume 4 (2021), pp. 1061-1102. doi : 10.5802/ahl.97. http://www.numdam.org/articles/10.5802/ahl.97/
[AAMM17] On the Extended Hensel Construction and Its Application to the Computation of Limit Points, Proceedings of the 42nd international symposium on symbolic and algebraic computation, ISSAC 2017, Kaiserslautern, Germany, July 25–28, 2017, Association for Computing Machinery (2017), pp. 13-20 | DOI | Zbl
[Abh89] Irreducibility criterion for germs of analytic functions of two complex variables, Adv. Math., Volume 74 (1989) no. 2, pp. 190-257 | DOI | MR | Zbl
[Abh90] Algebraic Geometry for Scientists and Engineers, Mathematical Surveys and Monographs, 35, American Mathematical Society, 1990 | MR | Zbl
[BCS + 07] Differential Equations for Algebraic Functions, ISSAC 2007. Proceedings of the 32nd international symposium on symbolic and algebraic computation (ISSAC 2007), Waterloo, ON, Canada, July 29–August 1, 2007 (2007), pp. 25-32 | Zbl
[BGY80] Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, Volume 1 (1980) no. 3, pp. 259-295 | DOI | Zbl
[BK86] Plane Algebraic Curves, Birkhäuser, 1986 (translated from the German by John Stillwell) | DOI | Zbl
[BNS13] Complexity of the OM Factorizations of Polynomials over Local Fields, LMS J. Comput. Math., Volume 16 (2013), pp. 139-171 | DOI | MR | Zbl
[BP94] Polynomial and matrix computations. Fundamental algorithms. Vol. 1., Progress in Theoretical Computer Science, Birkhäuser, 1994 | Zbl
[Cas86] Local Fields, London Mathematical Society Student Texts, 3, Cambridge University Press, 1986 | Zbl
[Che51] Introduction to the Theory of Algebraic Functions of One Variable, Mathematical Surveys, 6, American Mathematical Society, 1951 | Zbl
[CK91] On fast multiplication of polynomials over arbitrary algebras, Acta Inf., Volume 28 (1991) no. 7, pp. 693-701 | DOI | MR | Zbl
[CSTU02] Linear differential operators for polynomial equations, J. Symb. Comput., Volume 34 (2002) no. 5, pp. 355-398 | DOI | MR | Zbl
[DDD85] About a New Method for Computing in Algebraic Number Fields, EUROCAL 85. European Conference on Computer Algebra Linz, Austria, April 1–3 1985 Proceedings Vol. 2: Research Contributions (Caviness, Bob F., ed.) (Lecture Notes in Computer Science), Volume 204, Springer (1985) | DOI
[DP16] Death of Marc Rybowicz, Aged 52, ACM Commun. Comput. Algebra, Volume 50 (2016) no. 4, p. 191-191 | DOI | MR | Zbl
[DSMM + 05] On the complexity of the D5 principle, SIGSAM Bull., Volume 39 (2005) no. 3, pp. 97-98 | DOI
[Duv89] Rational Puiseux Expansions, Compos. Math., Volume 70 (1989) no. 2, pp. 119-154 | Numdam | MR | Zbl
[Eic66] Introduction to the Theory of Algebraic Numbers and Functions, Academic Press Inc., 1966 | Zbl
[G13] Modern Computer Algebra, Cambridge University Press, 2013 | DOI | Zbl
[GBGPPP17] Variations on inversion theorems for Newton–Puiseux series, Math. Ann., Volume 368 (2017) no. 3, pp. 1359-1397 | DOI | MR | Zbl
[HP98] Fast Rectangular Matrix Multiplication and Applications, J. Complexity, Volume 14 (1998) no. 2, pp. 257-299 | DOI | MR | Zbl
[Kal88] Greatest Common Divisors of Polynomials Given by Straight-line Programs, J. Assoc. Comput. Mach., Volume 35 (1988) no. 1, pp. 231-264 | DOI | MR | Zbl
[KS99] Solving Multivariate Algebraic Equations by Hensel Construction, Japan J. Ind. Appl. Math., Volume 16 (1999), pp. 257-285 | MR | Zbl
[KT78] All algebraic functions can be computed fast, J. Assoc. Comput. Mach., Volume 25 (1978) no. 2, pp. 245-260 | DOI | MR | Zbl
[L19] Accelerated tower arithmetic, J. Complexity, Volume 55 (2019), 101402 | DOI | MR | Zbl
[L20] Directed evaluation, J. Complexity, Volume 60 (2020), 101498 | DOI | MR | Zbl
[LG14] Powers of Tensors and Fast Matrix Multiplication, Proceedings of the 39th international symposium on symbolic and algebraic computation, ISSAC 2014, Kobe, Japan, July 23–25, 2014, Association for Computing Machinery (2014), pp. 296-303 | DOI | Zbl
[MS16] A Fast Algorithm for Computing the Truncated Resultant, Proceedings of the 41st international symposium on symbolic and algebraic computation, ISSAC 2016, Waterloo, Canada, July 20–22, 2016 (2016), pp. 341-348 | DOI | Zbl
[Mus75] Multivariate Polynomial Factorization, J. ACM, Volume 22 (1975) no. 2, pp. 291-308 | DOI | MR | Zbl
[Per99] Polígonos de Newton de orden superior y aplicaciones aritméticas, Ph. D. Thesis, Universitat de Barcelona, Spain (1999)
[PR08] Good reduction of Puiseux series and complexity of the Newton–Puiseux algorithm over finite fields, ISSAC ’08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation (2008), pp. 239-246 | DOI
[PR11] Complexity bounds for the rational Newton–Puiseux algorithm over finite fields, Appl. Algebra Eng. Commun. Comput., Volume 22 (2011) no. 3, pp. 187-217 | DOI | MR | Zbl
[PR12] Good reduction of Puiseux series and applications, J. Symb. Comput., Volume 47 (2012) no. 1, pp. 32-63 | DOI | MR | Zbl
[PR15] Improving complexity bounds for the computation of Puiseux series over finite fields, Proceedings of the 40th international symposium on symbolic and algebraic computation, ISSAC 2015, Bath, UK, July 6–9, 2015, Association for Computing Machinery (2015), pp. 299-306 | DOI | Zbl
[PS06] Change of order for bivariate triangular sets, Proceedings of the 2006 international symposium on symbolic and algebraic computation, ISSAC 06, Genova, Italy, July 9–12, 2006, Association for Computing Machinery (2006), pp. 277-284 | Zbl
[PS13a] Modular Composition Modulo Triangular Sets and Applications, Comput. Complexity, Volume 22 (2013) no. 3, pp. 463-516 | DOI | MR | Zbl
[PS13b] On the complexity of computing with zero-dimensional triangular sets, J. Symb. Comput., Volume 50 (2013), pp. 110-138 | DOI | MR | Zbl
[Sho94] Fast Construction of Irreducible Polynomials over Finite Fields, J. Symb. Comput., Volume 17 (1994) no. 5, pp. 371-391 | DOI | MR | Zbl
[SS71] Fast multiplication of large numbers. (Schnelle Multiplikation großer Zahlen), Computing, Volume 7 (1971), pp. 281-292 | DOI | Zbl
[Tei74] Cycles évanescents, sections planes et conditions de Whitney, Singularités à Cargèse (Astérisque), Volume 1973, Société Mathématique de France, 1974 no. 7-8, pp. 285-362 | Numdam | MR | Zbl
[Wal50] Algebraic Curves, Princeton Mathematical Series, 13, Princeton University Press, 1950 | MR | Zbl
[Wei16] Bivariate Factorization Using a Critical Fiber, Found. Comput. Math., Volume 17 (2016) no. 5, pp. 1219-1263 | DOI | MR | Zbl
Cited by Sources: