Computing Puiseux series: a fast divide and conquer algorithm
Annales Henri Lebesgue, Volume 4 (2021) , pp. 1061-1102.

Metadata

KeywordsPuiseux series, complexity, dynamic evaluation

Abstract

Let F𝕂[X,Y] be a polynomial of total degree D defined over a perfect field 𝕂 of characteristic zero or greater than D. Assuming F separable with respect to Y, we provide an algorithm that computes all singular parts of Puiseux series of F above X=0 in an expected Ø ˜(Dδ ) operations in 𝕂, where δ is the valuation of the resultant of F and its partial derivative with respect to Y. 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 F in 𝕂[[X]][Y] up to an arbitrary precision X N with Ø ˜(D(δ +N)) arithmetic operations. As a second main corollary, we compute the genus of the plane curve defined by F with Ø ˜(D 3 ) arithmetic operations and, if 𝕂=, with Ø ˜((h+1)D 3 ) bit operations using probabilistic algorithms, where h is the logarithmic height of F.


References

[AAMM17] Alvandi, Parisa; Ataei, Masoud; Moreno Maza, Marc 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 (2017), pp. 13-20 | Article | Zbl 1450.13011

[Abh89] Abhyankar, Shreeram S. Irreducibility criterion for germs of analytic functions of two complex variables, Adv. Math., Volume 74 (1989) no. 2, pp. 190-257 | Article | MR 997097 | Zbl 0683.14001

[Abh90] Abhyankar, Shreeram S. Algebraic Geometry for Scientists and Engineers, Mathematical Surveys and Monographs, 35, American Mathematical Society, 1990 | MR 1075991 | Zbl 0709.14001

[BCS + 07] Bostan, Alin; Chyzak, Frédéric; Salvy, Bruno; Lecerf, Grégoire; Schost, Éric 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 1190.68085

[BGY80] Brent, Richard P.; Gustavson, Fred G.; Yun, David Y. Y. Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, Volume 1 (1980) no. 3, pp. 259-295 | Article | Zbl 0475.65018

[BK86] Brieskorn, Egbert; Knörrer, Horst Plane Algebraic Curves, Birkhäuser, 1986 (translated from the German by John Stillwell) | Article | Zbl 0588.14019

[BNS13] Bauch, Jens-Dietrich; Nart, Enric; Stainsby, Hayden D. Complexity of the OM Factorizations of Polynomials over Local Fields, LMS J. Comput. Math., Volume 16 (2013), pp. 139-171 | Article | MR 3081769 | Zbl 1349.11099

[BP94] Bini, Dario; Pan, Victor Y. Polynomial and matrix computations. Fundamental algorithms. Vol. 1., Progress in Theoretical Computer Science, Birkhäuser, 1994 | Zbl 0809.65012

[Cas86] Cassel, John W. S. Local Fields, London Mathematical Society Student Texts, 3, Cambridge University Press, 1986 | Zbl 0595.12006

[Che51] Chevalley, Claude Introduction to the Theory of Algebraic Functions of One Variable, Mathematical Surveys, 6, American Mathematical Society, 1951 | Zbl 0045.32301

[CK91] Cantor, David; Kaltofen, Erich On fast multiplication of polynomials over arbitrary algebras, Acta Inf., Volume 28 (1991) no. 7, pp. 693-701 | Article | MR 1129288 | Zbl 076.68055

[CSTU02] Cormier, Olivier; Singer, Michael F.; Trager, Barry M.; Ulmer, Felix Linear differential operators for polynomial equations, J. Symb. Comput., Volume 34 (2002) no. 5, pp. 355-398 | Article | MR 1937466 | Zbl 1030.12002

[DDD85] Dora, Jean Della; Dicrescenzo, Claire; Duval, Dominique 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 (Lecture Notes in Computer Science), Volume 204 (1985) | Article

[DP16] Duval, Dominique; Poteaux, Adrien Death of Marc Rybowicz, Aged 52, ACM Commun. Comput. Algebra, Volume 50 (2016) no. 4, p. 191-191 | Article | MR 3622863 | Zbl 1365.01050

[DSMM + 05] Dahan, Xavier; Schost, Éric; Maza Moreno, Marc; Wu, Wenyuan; Xie, Yuzhen On the complexity of the D5 principle, SIGSAM Bull., Volume 39 (2005) no. 3, pp. 97-98 | Article

[Duv89] Duval, Dominique Rational Puiseux Expansions, Compos. Math., Volume 70 (1989) no. 2, pp. 119-154 | Numdam | MR MR996324 | Zbl 0699.14034

[Eic66] Eichler, Martin Introduction to the Theory of Algebraic Numbers and Functions, Academic Press Inc., 1966 | Zbl 0152.19502

[G13] von zur Gathen, Joachim von zur; Gerhard, Jürgen Modern Computer Algebra, Cambridge University Press, 2013 | Article | Zbl 1277.68002

[GBGPPP17] García Barroso, Evelia Rosa; González Pérez, Pedro Daniel; Popescu-Pampu, Patrick Variations on inversion theorems for Newton–Puiseux series, Math. Ann., Volume 368 (2017) no. 3, pp. 1359-1397 | Article | MR 3673657 | Zbl 1386.14018

[HP98] Huang, Xiaohan; Pan, Victor Y. Fast Rectangular Matrix Multiplication and Applications, J. Complexity, Volume 14 (1998) no. 2, pp. 257-299 | Article | MR 1629113 | Zbl 0919.65030

[Kal88] Kaltofen, Erich Greatest Common Divisors of Polynomials Given by Straight-line Programs, J. Assoc. Comput. Mach., Volume 35 (1988) no. 1, pp. 231-264 | Article | MR 926181 | Zbl 0642.68058

[KS99] Kako, Fujio; Sasaki, Tateaki Solving Multivariate Algebraic Equations by Hensel Construction, Japan J. Ind. Appl. Math., Volume 16 (1999), pp. 257-285 | MR 1696979 | Zbl 0941.12002

[KT78] Kung, H. T.; Traub, Joseph F. All algebraic functions can be computed fast, J. Assoc. Comput. Mach., Volume 25 (1978) no. 2, pp. 245-260 | Article | MR 488306 | Zbl 0371.68019

[L19] van der Hoeven, Joris; Lecerf, Grégoire Accelerated tower arithmetic, J. Complexity, Volume 55 (2019), 101402 | Article | MR 4007581 | Zbl 07134888

[L20] van der Hoeven, Joris; Lecerf, Grégoire Directed evaluation, J. Complexity, Volume 60 (2020), 101498 | Article | MR 4123745 | Zbl 07236044

[LG14] Le Gall, François 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 (2014), pp. 296-303 | Article | Zbl 1325.65061

[MS16] Moroz, Guillaume; Schost, Éric 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 | Article | Zbl 1362.13034

[Mus75] Musser, David R. Multivariate Polynomial Factorization, J. ACM, Volume 22 (1975) no. 2, pp. 291-308 | Article | MR 396470 | Zbl 0301.65029

[Per99] Peral, Jesús Montes Polígonos de Newton de orden superior y aplicaciones aritméticas (1999) (Ph. D. Thesis)

[PR08] Poteaux, Adrien; Rybowicz, Marc 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 | Article

[PR11] Poteaux, Adrien; Rybowicz, Marc Complexity bounds for the rational Newton–Puiseux algorithm over finite fields, Appl. Algebra Eng. Commun. Comput., Volume 22 (2011) no. 3, pp. 187-217 | Article | MR 2803913 | Zbl 1276.68177

[PR12] Poteaux, Adrien; Rybowicz, Marc Good reduction of Puiseux series and applications, J. Symb. Comput., Volume 47 (2012) no. 1, pp. 32-63 | Article | MR 2854846 | Zbl 1235.30002

[PR15] Poteaux, Adrien; Rybowicz, Marc 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 (2015), pp. 299-306 | Article | Zbl 1345.68293

[PS06] Pascal, Cyril; Schost, Éric 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 (2006), pp. 277-284 | Zbl 1356.12013

[PS13a] Poteaux, Adrien; Schost, Éric Modular Composition Modulo Triangular Sets and Applications, Comput. Complexity, Volume 22 (2013) no. 3, pp. 463-516 | Article | MR 3090784 | Zbl 1311.68199

[PS13b] Poteaux, Adrien; Schost, Éric On the complexity of computing with zero-dimensional triangular sets, J. Symb. Comput., Volume 50 (2013), pp. 110-138 | Article | MR 2996871 | Zbl 1332.68300

[Sho94] Shoup, Victor Fast Construction of Irreducible Polynomials over Finite Fields, J. Symb. Comput., Volume 17 (1994) no. 5, pp. 371-391 | Article | MR 1289997 | Zbl 0815.11059

[SS71] Schönage, Arnold; Strassen, Volker Fast multiplication of large numbers. (Schnelle Multiplikation großer Zahlen), Computing, Volume 7 (1971), pp. 281-292 | Article | Zbl 0223.68007

[Tei74] Teissier, Bernard 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 374482 | Zbl 0295.14003

[Wal50] Walker, Robert J. Algebraic Curves, Princeton Mathematical Series, 13, Princeton University Press, 1950 | MR 33083 | Zbl 0039.37701

[Wei16] Weimann, Martin Bivariate Factorization Using a Critical Fiber, Found. Comput. Math., Volume 17 (2016) no. 5, pp. 1219-1263 | Article | MR 3709331 | Zbl 1415.13014