Complexity bounds for the rational Newton-Puiseux algorithm over finite fields

DOI10.1007/s00200-011-0144-6zbMath1276.68177OpenAlexW2050415272MaRDI QIDQ429752

Marc Rybowicz, Adrien Poteaux

Publication date: 20 June 2012

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00200-011-0144-6

zbMATH Keywords

complexityPuiseux seriesalgebraic functions

Mathematics Subject Classification ID

Related Items (10)

Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations ⋮ A quasi-linear irreducibility test in \(\mathbb{K}x[y\)] ⋮ Bivariate factorization using a critical fiber ⋮ Computing monodromy via continuation methods on random Riemann surfaces ⋮ Factoring bivariate polynomials using adjoints ⋮ Polynomial root finding over local rings and application to error correcting codes ⋮ Good reduction of Puiseux series and applications ⋮ A Symbolic Computation Approach Towards the Asymptotic Stability Analysis of Differential Systems with Commensurate Delays ⋮ Computing the equisingularity type of a pseudo-irreducible polynomial ⋮ Computing Puiseux series: a fast divide and conquer algorithm

Uses Software

• Magma
• Maple

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modular composition modulo triangular sets and applications
• Good reduction of Puiseux series and applications
• Puiseux's théorem revisited
• Matrix multiplication via arithmetic progressions
• On expansion of algebraic functions in power and Puiseux series. I
• On expansion of algebraic functions in power and Puiseux series. II
• On fast multiplication of polynomials over arbitrary algebras
• Fast evaluation of holonomic functions
• On the complexity of rational Puiseux expansions
• The Magma algebra system. I: The user language
• Linear differential operators for polynomial equations
• An algorithm for computing an integral basis in an algebraic function field
• Fast separable factorization and applications
• Effective analytic functions
• Calcul pratique des coefficients de Taylor d'une fonction algébrique
• Fast multiplication of large numbers
• The Computational Complexity of the Resolution of Plane Curve Singularities
• All Algebraic Functions Can Be Computed Fast
• Fast Algorithms for Manipulating Formal Power Series
• Hensel construction of F(x, u ₁ , ..., x _l ) l ≥ 2 at a singular point and its applications
• A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function
• Complexity of computation of embedded resolution of algebraic curves
• Fast construction of irreducible polynomials over finite fields
• Factoring polynomials over finite fields: A survey

This page was built for publication: Complexity bounds for the rational Newton-Puiseux algorithm over finite fields