scientific article; zbMATH DE number 4037047
[For the entire collection see Zbl 0596.00021.] The Newton-Puiseux algorithm computates roots \(y_ i\) of a polynomial f(Y) where the \(y_ i=\sum_{0\leq j\in {\mathbb{Z}}}y_{ij}x^{j/\xi (i)}\) belong to the field of fraction-power series. It has been known [cf. \textit{H. T. Kung} and \textit{J. F. Traub}, J. Assoc. Comput. Machin. 25, 245-260 (1978; Zbl 0371.68019)] only that the algorithm has polynomial complexity without taking into account sizes of coefficients when in one step an arithmetical operation over complex numbers can be implemented. The author proves, that in the most important model for symbolic computations when sizes of rational coefficients and extensions of the constant field are taken into account, the algorithm has also polynomial complexity (i.e. the first i terms of each of fraction-power series in the output of the algorithm are computed within polynomial time with respect to the size of the input and of i).
- scientific article; zbMATH DE number 5154
- Puiseux series solutions of ODEs
- scientific article; zbMATH DE number 953020
- Efficient estimation of roots from the field of fractional power series of a given polynomial in nonzero characteristic
- Good reduction of puiseux series and complexity of the Newton-Puiseux algorithm over finite fields
- On computation of a power series root with arbitrary degree of convergence
- On the complexity of rational Puiseux expansions
- Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic
- Computing tropical points and tropical links
- Efficient estimation of roots from the field of fractional power series of a given polynomial in nonzero characteristic
- Complexity of deciding whether a tropical linear prevariety is a tropical variety
- On the estimation of coefficients of irreducible factors of polynomials over a field of formal power series in nonzero characteristic
- Effective construction of an algebraic variety nonsingular in codimension one over a ground field of zero characteristic
- A numerical realization of the conditions of Max Nöther's residual intersection theorem
- An overview of effective normalization of a projective algebraic variety nonsingular in codimension one
- Improving complexity bounds for the computation of Puiseux series over finite fields
- Dynamic Newton-Puiseux theorem
- Generating approximate parametric roots of parametric polynomials
- Computing low-degree factors of lacunary polynomials: a Newton-Puiseux approach
- Complexity bounds for the rational Newton-Puiseux algorithm over finite fields
- scientific article; zbMATH DE number 5154 (Why is no real title available?)
- scientific article; zbMATH DE number 953020 (Why is no real title available?)
- A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function
- Irreducibility testing over local fields
- Extension of the Newton–Puiseux algorithm to the case of a nonzero characteristic ground field. I
- Good reduction of Puiseux series and applications
- Plane curve germs and contact factorization
- Complexity of factoring and calculating the GCD of linear ordinary differential operators
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3776501)