Adrien Poteaux
ABSTRACT
In [12], we sketched a numeric-symbolic method to compute Puiseux series with floating point coefficients. In this paper, we address the symbolic part of our algorithm. We study the reduction of Puiseux series coefficients modulo a prime ideal and prove a good reduction criterion sufficient to preserve the required information, namely Newton polygon trees. We introduce a convenient modification of Newton polygons that greatly simplifies proofs and statements of our results. Finally, we improve complexity bounds for Puiseux series calculations over finite fields, and estimate the bit-complexity of polygon tree computation.
- E. Brieskorn and H. Knörrer. Plane Algbebraic Curves. Birkhaüser, 1986.Google Scholar
Cross Ref
- C. Chevalley. Introduction to the Theory of Algebraic Functions of One Variable, volume 6 of Mathematical Surveys. AMS, 1951.Google Scholar
- H. Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1993. Google ScholarDigital Library
- B. Deconinck and M. S. Patterson. Computing the Abel Map. preprint, 2007.Google Scholar
- B. Deconinck and M. van Hoeij. Computing Riemann matrices of algebraic curves. Phys. D, 152/153:28--46, 2001.Google ScholarCross Ref
- D. Duval. Diverses questions relatives au calcul formel avec des nombres algébriques. PhD thesis, Université de Grenoble, 1987. Thèse d'Etat.Google Scholar
- D. Duval. Rational Puiseux Expansions. Compositio Mathematica, 70:119--154, 1989.Google Scholar
- B. Dwork and P. Robba. On natural radii of p-adic convergence. Trans. Amer. Math. Soc., 256:199--213, 1979.Google Scholar
- M. Eichler. Introduction to the Theory of Algebraic Numbers and Functions. Academic Press, 1966.Google Scholar
- W. Fulton. Hurwitz Schemes and Irreducibility of Moduli of Algebraic Curves. Annals of Mathematics, 90:542--575, 1969.Google ScholarCross Ref
- H. T. Kung and J. F. Traub. All algebraic functions can be computed fast. J. ACM, 25(2):245--260, 1978. Google ScholarDigital Library
- A. Poteaux. Computing monodromy groups defined by plane algebraic curves. In Proceedings of the 2007 International Workshop on Symbolic-numeric Computation, pages 36--45, New-York, 2007. ACM. Google ScholarDigital Library
- A. Poteaux and M. Rybowicz. Towards a Symbolic-Numeric Method to Compute Puiseux Series: The Modular Part, 2008. http://arxiv.org/abs/0803.3027.Google Scholar
- V. Shoup. A Computational Introduction to Number Theory. Cambridge University Press, 2005. Google ScholarDigital Library
- B. M. Trager. Integration of Algebraic Functions. PhD thesis, Department of EECS MIT, 1984.Google Scholar
- M. van Hoeij. An Algorithm for Computing an Integral Basis in an Algebraic Function Field. Journal of Symbolic Computation, 18:353--363, 1994. Google ScholarDigital Library
- J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge, 1999. Google ScholarDigital Library
- P. G. Walsh. A Polynomial-time Complexity Bound for the Computation of the Singular Part of an Algebraic Function. Mathematics of Computation, 69:1167--1182, 2000. Google ScholarDigital Library
- O. Zariski. Le problème des modules pour les branches planes. Hermann, Paris, 1981.Google Scholar
Index Terms
- Good reduction of puiseux series and complexity of the Newton-Puiseux algorithm over finite fields
Recommendations
Improving Complexity Bounds for the Computation of Puiseux Series over Finite Fields
ISSAC '15: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic ComputationLet K be a field of characteristic p with q elements and FΕ in L[X,Y] be a polynomial with p> deg_Y(F) and total degree d. In [40], we showed that rational Puiseux series of F above X=0 could be computed with an expected number of O~(d5+d3log q) ...
Good reduction of Puiseux series and applications
We have designed a new symbolic-numeric strategy for computing efficiently and accurately floating point Puiseux series defined by a bivariate polynomial over an algebraic number field. In essence, computations modulo a well-chosen prime number p are ...
The practical Gauss type rules for Hadamard finite-part integrals using Puiseux expansions
A general framework is constructed for efficiently and stably evaluating the Hadamard finite-part integrals by composite quadrature rules. Firstly, the integrands are assumed to have the Puiseux expansions at the endpoints with arbitrary algebraic and ...
Comments