Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function

Author: P. G. Walsh
Journal: Math. Comp. 69 (2000), 1167-1182
MSC (1991): Primary 14H05, 11Y15
Published electronically: February 16, 2000
MathSciNet review: 1710624
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


In this paper we present a refined version of the Newton polygon process to compute the Puiseux expansions of an algebraic function defined over the rational function field. We determine an upper bound for the bit-complexity of computing the singular part of a Puiseux expansion by this algorithm, and use a recent quantitative version of Eisenstein's theorem on power series expansions of algebraic functions to show that this computational complexity is polynomial in the degrees and the logarithm of the height of the polynomial defining the algebraic function.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 14H05, 11Y15

Retrieve articles in all journals with MSC (1991): 14H05, 11Y15

Additional Information

P. G. Walsh
Affiliation: Department of Mathematics, University of Ottawa, 585 King Edward, Ottawa, Ontario, Canada KIN 6N5

Keywords: Algebraic function, Puiseux expansion, Newton polygon, complexity.
Received by editor(s): May 28, 1994
Received by editor(s) in revised form: March 21, 1995, and June 5, 1996
Published electronically: February 16, 2000
Additional Notes: This work constitutes part of the author’s doctoral dissertation from the University of Waterloo.
Dedicated: Dedicated to Wolfgang Schmidt on the occasion of his sixtieth birthday.
Article copyright: © Copyright 2000 American Mathematical Society