scientific article; zbMATH DE number 4037047

From MaRDI portal
Publication:3776501





[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).




Cited in
(23)








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)