Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards MyNewsletter Firmensuche
Jetzt Einzelzugang starten
Referenzkunden
Automotive Acoustics Conference 2025

Call for Papers - Deadline: 13. Januar 2025.

Wir möchten Sie dazu einladen, Ihre Vorschläge für einen Vortrag auf der Automotive Acoustics Conference 2025 einzureichen und mit uns neue Verfahren der nachhaltigen Lärmminderung zu erforschen. Wir freuen uns auf Ihre Anregungen für innovative, umweltfreundliche und intelligente Verfahren zur Gestaltung der Zukunft der Fahrzeugakustik.
Erweiterte Suche
Anmelden
nach oben
Applicable Algebra in Engineering, Communication and Computing

30.11.2024 | Original Paper

Plane curve germs and contact factorization

verfasst von: Joris van der Hoeven, Grégoire Lecerf

Erschienen in: Applicable Algebra in Engineering, Communication and Computing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Given an algebraic germ of a plane curve at the origin, in terms of a bivariate polynomial, we analyze the complexity of computing an irreducible decomposition up to any given truncation order. With a suitable representation of the irreducible components, and whenever the characteristic of the ground field is zero or larger than the degree of the germ, we design a new algorithm that involves a nearly linear number of arithmetic operations in the ground field plus a small amount of irreducible univariate polynomial factorizations.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
  1. Abelard, S., Berardini, E., Couvreur, A., Lecerf, G.: Computing Riemann–Roch spaces via Puiseux expansions. J. Complex. 73, 101666 (2022)MathSciNetView Article
  2. Abhyankar, S.S.: Irreducibility criterion for germs of analytic functions of two complex variables. Adv. Math. 74(2), 190–257 (1989)MathSciNetView Article
  3. Abhyankar, S.S., Moh, T.: Newton-Puiseux expansion and generalized Tschirnhausen transformation. I. J. Reine Angew. Math. 260, 47–83 (1973)MathSciNet
  4. Abhyankar, S.S., Moh, T.: Newton-Puiseux expansion and generalized Tschrinhausen transformation. II. J. Reine Angew. Math. 261, 29–54 (1973)
  5. Alberich-Carramiñana, M., Guàrdia, J., Nart, E., Poteaux, A., Roé, J., Weimann, M.: Polynomial factorization over henselian fields. Found. Comput. Math. (2024). https://​doi.​org/​10.​1007/​s10208-024-09646-xView Article
  6. Alonso, M.E., Castro-Jiménez, F.J., Hauser, H.: Encoding algebraic power series. J. Found. Comput. Math. 18(3), 789–833 (2018)MathSciNetView Article
  7. Aschenbrenner, M., van den Dries, L., van der Hoeven, J.: Asymptotic Differential Algebra and Model Theory of Transseries Number 195 in Annals of Mathematics studies. Princeton University Press, New Jersey (2017)
  8. Bauch, J.-D., Nart, E., Stainsby, H.D.: Complexity of OM factorizations of polynomials over local fields. LMS J. Comput. Math. 16, 139–171 (2013)MathSciNetView Article
  9. Berthomieu, J., Lecerf, G., Quintin, G.: Polynomial root finding over local rings and application to error correcting codes. Appl. Algebra Engrg. Comm. Comput. 24(6), 413–443 (2013)MathSciNetView Article
  10. Bostan, A., Christol, G., Dumas, Ph.: Fast computation of the Nth term of an algebraic series over a finite prime field. In: Rosenkranz, M. (ed.), Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’16, pp. 119–126. ACM, New York, NY, USA, (2016)
  11. Bostan, A., Chyzak, F., Lecerf, G., Salvy, B., Schost, É.: Differential equations for algebraic functions. In: Brown, C.W. (ed.) Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, ISSAC ’07. ACM, New York, NY, USA, (2007)
  12. Bostan, A., Lecerf, G., Salvy, B., Schost, É., Wiebelt, B.: Complexity issues in bivariate polynomial factorization. In: Schicho, J. (ed.) Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, ISSAC ’04, pp. 42–49, ACM Press. New York, NY, USA, (2004)
  13. Campillo, A., Farrán, J.I.: Symbolic Hamburger–Noether expressions of plane curves and applications to AG codes. Math. Comp. 71(240), 1759–1780 (2002)MathSciNetView Article
  14. Cantor, D.G., Gordon, D.M.: Factoring polynomials over \(p\)-adic fields. In: Bosma, W. (ed.) Algorithmic Number Theory. 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000. Proceedings, volume 1838 of Lecture Notes in Comput. Sci., pp. 185–208. Springer-Verlag, (2000)
  15. Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inf. 28, 693–701 (1991)MathSciNetView Article
  16. Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36(154), 587–592 (1981)MathSciNetView Article
  17. Chistov, A.L.: Polynomial complexity of the Newton–Puiseux algorithm. In: Mathematical Foundations of Computer Science 1986. Proceedings of the 12th Symposium Bratislava, Czechoslovakia August 25–29, 1986, volume 233 of Lecture Notes in Comput. Sci., pp. 247–255. Springer-Verlag, (1986)
  18. Chistov, A.L.: Efficient factoring polynomials over local fields and its applications. In: Proceedings of the International Congress of Mathematicians, Kyoto, Japan, 1990, vol. 1, pp. 1509–1519. Springer-Verlag, (1991)
  19. Chudnovsky, D.V., Chudnovsky, G.V.: On expansion of algebraic functions in power and Puiseux series. I. J. Complex. 2(4), 271–294 (1986)MathSciNetView Article
  20. Chudnovsky, D.V., Chudnovsky, G.V.: On expansion of algebraic functions in power and Puiseux series. II. J. Complex. 3(1), 1–25 (1987)MathSciNetView Article
  21. Cohen, H.: A course in computational algebraic number theory. Graduate Texts in Mathematics. Springer, Berlin, Heidelberg (1993)View Article
  22. Cossart, V., Moreno-Socías, G.: Racines approchées, suites génératrices, suffisance des jets. Annales de la Faculté des sciences de Toulouse \(6_{e}\) série, 14(3):353–394, (2005)
  23. Duval, D.: Rational Puiseux expansions. Compos. Math. 70(2), 119–154 (1989)MathSciNet
  24. Dwivedi, A., Saxena, N.: Computing Igusa’s local zeta function of univariates in deterministic polynomial-time. In: Galbraith, S.D. (ed.) ANTS XIV. Proceedings of the Fourteenth Algorithmic Number Theory Symposium, volume 4 of The Open Book Series, pp. 197–214. MSP, Berkeley, CA, USA (2020)
  25. Fernández, J., Guàrdia, J., Montes, J., Nart, E.: Residual ideals of MacLane valuations. J. Algebra 427, 30–75 (2015)MathSciNetView Article
  26. Ford, D., Letard, P.: Implementing the Round Four maximal order algorithm. J. Théor. Nombres Bordeaux 6(1), 39–80 (1994)MathSciNetView Article
  27. Ford, D., Pauli, S., Roblot, X.-F.: A fast algorithm for polynomial factorization over \({\mathbb{Q} }_p\). J. Théor. Nombres Bordeaux 14(1), 151–169 (2002)MathSciNetView Article
  28. Ford, D., Veres, O.: On the complexity of the Montes ideal factorization algorithm. In: Hanrot, G., Morain, F., Thomé, E. (eds.), Algorithmic Number Theory. 9th International Symposium, ANTS-IX, Nancy, France, July 19-23, 2010. Proceedings, volume 6197 of Lecture Notes in Comput. Sci., pp. 174–185. Springer-Verlag, (2010)
  29. Fröhlich, A., Shepherdson, J.C.: On the factorisation of polynomials in a finite number of steps. Math. Z. 62, 331–334 (1955)MathSciNetView Article
  30. Fröhlich, A., Shepherdson, J.C.: Effective procedures in field theory. Philos. Trans. R. Soc. Lond. Ser. A. 248, 407–432 (1956)MathSciNetView Article
  31. von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. 3rd edn., Cambridge University Press, New York (2013)
  32. von Gathen, J., Shoup, V.: Computing Frobenius maps and factoring polynomials. Comput. Complex. 2(3), 187–224 (1992)MathSciNetView Article
  33. Greuel, G.-M., Pfister, G.: A Singular Introduction to Commutative Algebra. Springer-Verlag, Berlin Heidelberg (2002)View Article
  34. Guàrdia, J., Montes, J., Nart, E.: Okutsu invariants and Newton polygons. Acta Arith. 145(1), 83–108 (2010)MathSciNetView Article
  35. Guàrdia, J., Montes, J., Nart, E.: Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields. J. Théor. Nombres Bordeaux 23(3), 667–696 (2011)MathSciNetView Article
  36. Guàrdia, J., Montes, J., Nart, E.: Newton polygons of higher order in algebraic number theory. Trans. Am. Math. Soc. 364(1), 361–416 (2012)MathSciNetView Article
  37. Guàrdia, J., Montes, J., Nart, E.: A new computational approach to ideal theory in number fields. Found. Comput. Math. 13(5), 729–762 (2013)MathSciNetView Article
  38. Guàrdia, J., Montes, J., Nart, E.: Higher Newton polygons and integral bases. J. Number Theory 147, 549–589 (2015)MathSciNetView Article
  39. Guàrdia, J., Nart, E., Pauli, S.: Single-factor lifting and factorization of polynomials over local fields. J. Symb. Comput. 47(11), 1318–1346 (2012)MathSciNetView Article
  40. Harvey, D., van der Hoeven, J.: Polynomial multiplication over finite fields in time \(O (n \log n)\). J. ACM 69(2), 1–40 (2022)View Article
  41. Henry, J.P.G., Merle, M.: Complexity of computation of embedded resolution of algebraic curves. In: Davenport, J.H. (ed.), Eurocal ’87. European Conference on Computer Algebra. Leipzig, GDR, June 2–5, (1987). Proceedings, volume 378 of Lect. Notes Comput. Sci., pp. 381–390. Springer Berlin Heidelberg, 1989
  42. Hironaka, H.: Resolution of singularities of an algebraic variety over a field of characteristic zero. Ann. Math. 79, 109–326 (1964)MathSciNetView Article
  43. van der Hoeven, J.: Automatic asymptotics. PhD thesis, École polytechnique, Palaiseau, France, (1997)
  44. van der Hoeven, J.: Relax, but don’t be too lazy. J. Symbol. Comput. 34, 479–542 (2002)MathSciNetView Article
  45. van der Hoeven, J.: Newton’s method and FFT trading. J. Symbol. Comput. 45(8), 857–878 (2010)MathSciNetView Article
  46. van der Hoeven, J.: Faster Chinese remaindering. Technical Report, HAL, (2016). https://​hal.​archives-ouvertes.​fr/​hal-01403810
  47. van der Hoeven, J.: Computing with D-algebraic power series. Appl. Algebra Eng. Comm. Comput. 30(1), 17–49 (2019)MathSciNetView Article
  48. van der Hoeven, J.: Effective power series computations. Found. Comput. Math. 19(3), 623–651 (2019)MathSciNetView Article
  49. van der Hoeven, J.: The Jolly Writer. Scypress, Your Guide to GNU TeXmacs (2020)
  50. van der Hoeven, J., Lecerf, G.: Modular composition via factorization. J. Complex. 48, 36–68 (2018)MathSciNetView Article
  51. van der Hoeven, J., Lecerf, G.: Accelerated tower arithmetic. J. Complex. 55, 101402 (2019)MathSciNetView Article
  52. van der Hoeven, J., Lecerf, G.: Directed evaluation. J. Complex. 60, 101498 (2020)MathSciNetView Article
  53. van der Hoeven, J., Lecerf, G.: Univariate polynomial factorization over finite fields with large extension degree. Appl. Algebra Eng. Commun. Comput. 35, 121–149 (2024)MathSciNetView Article
  54. Kaltofen, E., Shoup, V.: Fast polynomial factorization over high algebraic extensions of finite fields. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97, pp. 184–188. New York, NY, USA, ACM (1997)
  55. Kaltofen, E., Shoup, V.: Subquadratic-time factoring of polynomials over finite fields. Math. Comput. 67(223), 1179–1197 (1998)MathSciNetView Article
  56. Kedlaya, K.S.: On the algebraicity of generalized power series. Beitr. Algebra Geom. 58, 499–527 (2017)MathSciNetView Article
  57. Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767–1802 (2011)MathSciNetView Article
  58. Kung, H.T., Traub, J.F.: All algebraic functions can be computed fast. J. ACM 25(2), 245–260 (1979)MathSciNetView Article
  59. Lang, S.: Algebra. Graduate Texts in Mathematics, vol. 211, 3rd edn. Springer-Verlag, New York (2002)
  60. Lecerf, G.: Fast separable factorization and applications. Appl. Algebra Eng. Comm. Comput. 19(2), 135–160 (2008)MathSciNetView Article
  61. Lecerf, G.: New recombination algorithms for bivariate polynomial factorization based on Hensel lifting. Appl. Algebra Eng. Comm. Comput. 21(2), 151–176 (2010)MathSciNetView Article
  62. MacLane, S.: A construction for absolute values in polynomial rings. Trans. Am. Math. Soc. 40(3), 363–395 (1936)MathSciNetView Article
  63. MacLane, S.: A construction for prime ideals as absolute values of an algebraic field. Duke Math. J. 2(3), 492–510 (1936)MathSciNet
  64. Montes, J.: Polígonos de Newton de orden superior y aplicaciones aritméticas. PhD thesis, Universitat de Barcelona, Spain, (1999)
  65. Mora, F.: An algorithm to compute the equations of tangent cones. In:  Calmet, J. (ed.), Computer Algebra. EUROCAM ’82, European Computer Algebra Conference, Marseilles, France, April 5-7, 1982, volume 144 of Lect. Notes in Computer Sc., pp. 158–165. Springer-Verlag Berlin Heidelberg, (1982)
  66. Moroz, G.: New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 1090–1099. Los Alamitos, CA, USA. IEEE (2022)
  67. Moroz, G., Schost, É.: A fast algorithm for computing the truncated resultant. In: Rosenkranz, M. (ed.), Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’16, pp. 341–348. New York, NY, USA, (2016). ACM
  68. Nart, E.: Okutsu-Montes representations of prime ideals of one-dimensional integral closures. Publicacions Matemàtiques 55(2), 261–294 (2011)MathSciNetView Article
  69. Neiger, V., Rosenkilde, J., Schost, É.: Fast computation of the roots of polynomials over the ring of power series. In: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’17, pp. 349–356. ACM Press, New York, NY, USA, (2017)
  70. Newton, I.: De methodis serierum et Fluxionum. Manuscript, (1671)
  71. Okutsu, K.: Construction of integral basis. I. Proc. Jpn. Acad. Ser. A Math. Sci. 58(1), 47–49 (1982)MathSciNetView Article
  72. Okutsu, K.: Construction of integral basis. II. Proc. Jpn. Acad. Ser. A Math. Sci. 58(2), 87–89 (1982)MathSciNetView Article
  73. Okutsu, K.: Construction of integral basis. III. Proc. Jpn. Acad. Ser. A Math. Sci. 58(3), 117–119 (1982)MathSciNetView Article
  74. Okutsu, K.: Construction of integral basis. IV. Proc. Jpn. Acad. Ser. A Math. Sci. 58(4), 167–169 (1982)MathSciNetView Article
  75. Ore, Ö.: Zur Theorie der Algebraischen Körper. Acta Math. 44, 219–314 (1923)MathSciNetView Article
  76. Ore, Ö.: Bestimmung der Diskriminanten algebraischer Körper. Acta Math. 45, 303–344 (1925)MathSciNetView Article
  77. Ore, Ö.: Newtonsche Polygone in der Theorie der algebraischen Körper. Math. Ann. 99, 84–117 (1928)MathSciNetView Article
  78. Ostrowski, A.M.: Über die Bedeutung der Theorie der konvexen Polyeder für die formale Algebra. Jahresber. Deutsch. Math.-Verein. 30(2), 98–99 (1921). (Talk given at Der Deutsche Mathematikertag vom 18–24 September 1921 in Jena)
  79. Ostrowski, A.M.: On multiplication and factorization of polynomials. I. Lexicographic orderings and extreme aggregates of terms. Aequationes Math. 13(3), 201–228 (1975)MathSciNetView Article
  80. Ostrowski, A.M.: On the significance of the theory of convex polyhedra for formal algebra. SIGSAM Bull. 33(1), 5 (1999). (Translated from [78])View Article
  81. Pan, V.Y.: Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding. J. Symbol. Comput. 33(5), 701–733 (2002)MathSciNetView Article
  82. Pauli, S.: Factoring polynomials over local fields. J. Symbol. Comput. 32(5), 533–547 (2001)MathSciNetView Article
  83. Poteaux, A.: Calcul de développements de Puiseux et application au calcul de groupe de monodromie d’une courbe algébrique plane. PhD thesis, Université de Limoges, France, (2008)
  84. Poteaux, A., Rybowicz, M.: Improving complexity bounds for the computation of Puiseux series over finite fields. In: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC’15, pp. 299–306. New York, NY, USA. ACM (2015)
  85. Poteaux, A., Schost, É.: Modular composition modulo triangular sets and applications. Comput. Complex. 22(3), 463–516 (2013)MathSciNetView Article
  86. Poteaux, A., Weimann, M.: Using approximate roots for irreducibility and equi-singularity issues in \(K [[x]] [y]\). Technical Report, arXiv:​1904.​00286, (2019)
  87. Poteaux, A., Weimann, M.: Computing Puiseux series: a fast divide and conquer algorithm. Ann. Henri Lebesgue 5, 1061–1102 (2021)MathSciNetView Article
  88. Poteaux, A., Weimann, M.: A quasi-linear irreducibility test in \({\mathbb{K} } [[x]] [y]\). Comput. Complex. 31, 6 (2022)MathSciNetView Article
  89. Poteaux, A., Weimann, M.: Local polynomial factorisation: improving the Montes algorithm. In:  Hashemi, A. (ed.), Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC ’22, pp. 149–157. ACM, New York, NY, USA, (2022)
  90. Puiseux, M.V.: Recherches sur les fonctions algébriques. J. Math. Pures et Appliquées 15, 365–480 (1850)
  91. Russell, P.: Hamburger-Noether expansions and approximate roots of polynomials. Manuscr. Math. 31, 25–95 (1980)MathSciNetView Article
  92. Schönhage, A.: Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Inf. 7, 395–398 (1977)MathSciNetView Article
  93. Schönhage, A.: The fundamental theorem of algebra in terms of computational complexity. Math. Inst. Univ. of Tübingen, Technical Report (1982)
  94. Shoup, V.: New algorithms for finding irreducible polynomials over finite fields. Math. Comp. 54(189), 435–447 (1990)MathSciNetView Article
  95. Smith, S.: On the higher singularities of plane curves. Prod. Lond. Math. Soc. 6, 153–182 (1875)MathSciNet
  96. von Tschirnhaus, E.W.: Nova methodus auferendi omnes terminos intermedios ex data æquatione. Acta Eriditorium, 1683, 204–207
  97. van der Waerden, B.L. Algebra. Springer, 7th edition: Based in part on lectures by E. Artin and E, Noether (1991)
  98. Walker, R.J.: Algebraic Curves, volume 13 of Princeton mathematical series. Princeton University Press, (1950)
  99. Walsh, P.: A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function. Math. Comp. 69(231), 1167–1182 (2000)MathSciNetView Article
  100. Walsh, P.G.: On the complexity of rational Puiseux expansions. Pacific J. Math. 188(2), 369–387 (1999)MathSciNetView Article
  101. Watt, S.M.: A fixed point method for power series computation. In: Gianni, P. (ed.), Symbolic and Algebraic Computation. International Symposium ISSAC’ 88, Rome, Italy, July 4-8, 1988. Proceedings, volume 358 of Lect. Notes in Computer Sc., pp. 206–217. Springer-Verlag, (1989)
  102. Zariski, O.: Le problème des modules pour les branches planes. Hermann, Paris (1986)
Metadaten
Titel
Plane curve germs and contact factorization
verfasst von
Joris van der Hoeven
Grégoire Lecerf
Publikationsdatum
30.11.2024
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-024-00669-z

Premium Partner

    Bildnachweise