Computing monodromy groups defined by plane algebraic curves

ABSTRACT

We present a symbolic-numeric method to compute the monodromy group of a plane algebraic curve viewed as a ramified covering space of the complex plane. Following the definition, our algorithm is based on analytic continuation of algebraic functions above paths in the complex plane. Our contribution is three-fold : first of all, we show how to use a minimum spanning tree to minimize the length of paths ; then, we propose a strategy that gives a good compromise between the number of steps and the truncation orders of Puiseux expansions, obtaining for the first time a complexity result about the number of steps; finally, we present an efficient numerical-modular algorithm to compute Puiseux expansions above critical points,which is a non trivial task.

REFERENCES

• 1: E. L. Allgower and K. Georg. Numerical Path Following. In Handbook of Numerical Analysis, Vol. V, Handb. Numer. Anal., V, pages 3--207. North-Holland, Amsterdam, 1997.
• 2: F. Baldassarri and B. Dwork. On Second Order Linear Differential Equations with Algebraic Solutions. Amer. J. Math., 101(1):42--76, 1979.
• 3: L. Bertrand. Computing a Hyperelliptic Integral Using Arithmetic in the Jacobian of the Curve. Applicable Algebra in Engineering, Communication and Computing, 6:275--298, 1995.
• 4: Manuel Bronstein, Integration of elementary functions, Journal of Symbolic Computation, v.9 n.2, p.117-173, Feb. 1990 [doi>10.1016/S0747-7171(08)80027-2]
• 5: A. Campillo. Algebroid Curve in Positive Characteristic, volume 813 of Lecture Notes in Mathematics. Springer-Verlag, New York-Berlin, 1980.
• 6: D V Chudnovsky , G V Chudnovsky, On expansion of algebraic functions in power and puiseux series, I, Journal of Complexity, v.2 n.4, p.271-294, Dec. 1986 [doi>10.1016/0885-064X(86)90006-3]
• 7: E. Compoint and M. Singer. Relations linéaires entre solutions d'uneéquation différentielle (Linear Relations Between the Solutions of a Differential Equation). Ann. Fac. Sci. Toulouse, Série 6, Vol. 7, no. 4:659--670, 1998.
• 8: L. Comtet. Calcul pratique des coe. cients de Taylor d'une fonction algébrique. L 'Enseignement Mathématique, 2(10):267--270, 1964.
• 9: Olivier Cormier , Michael F. Singer , Barry M. Trager , Felix Ulmer, Linear differential operators for polynomial equations, Journal of Symbolic Computation, v.34 n.5, p.355-398, November 2002 [doi>10.1006/jsco.2002.0564]
• 10: B. Deconinck and M. S. Patterson. Computing the Abel Map. preprint, 2007.
• 11: Bernard Deconinck , Harvey Segur, The KP equation with quasiperiodic initial data, Physica D, v.123 n.1-4, p.123-152, Nov. 15, 1998 [doi>10.1016/S0167-2789(98)00117-1]
• 12: B. Deconinck and M. van Hoeij. Computing Riemann Matrices of Algebraic Curves. Phys. D, 152/153:28--46, 2001. Advances in Nonlinear Mathematics and Science.
• 13: D. Duval. Rational Puiseux Expansions. Compositio Math., 70(2):119--154, 1989.
• 14: M. Eichler. Introduction to the Theory of Algebraic Numbers and Functions. Pure and Applied Mathematics. Academic Press, 1966.
• 15: O. Forster. Lectures on Riemann Surfaces. Graduate Text in Mathematics. Springer Verlag, New-York, Berlin, 1981.
• 16: A. I. Markushevich. Theory of Functions of a Complex Variable. Vol. III. Revised English edition, translated and edited by Richard A. Silverman. Prentice-Hall Inc., Englewood Cliffs, N. J., 1967.
• 17: Maurice Mignotte, Mathematics for computer algebra, Springer-Verlag New York, Inc., New York, NY, 1992
• 18: M. Mignotte and D. Stefanescu. Polynomials, an Algorithmic Approach. Discrete Mathematics and Theoretical Computer Science. Springer, 1999.
• 19: R. Miranda. Algebraic Curves and Riemann Surfaces. Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 1995.
• 20: Victor Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, v.39 n.2, p.187-220, June 1997 [doi>10.1137/S0036144595288554]
• 21: R. H. Risch. The Problem of Integration in Finite Terms. Transactions of the American Mathematical Society, 139:167--189, 1969.
• 22: Brian T. Smith, Error Bounds for Zeros of a Polynomial Based Upon Gerschgorin's Theorems, Journal of the ACM (JACM), v.17 n.4, p.661-674, Oct. 1970 [doi>10.1145/321607.321615]
• 23: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical factorization of multivariate complex polynomials, Theoretical Computer Science, v.315 n.2-3, p.651-669, 6 May 2004 [doi>10.1016/j.tcs.2004.01.011]
• 24: C. Tretko. and M. Tretko.. Combinatorial Group Theory, Riemann Surfaces and Differential Equations. Contemp. Math., 33:467--517, 1984.
• 25: Joris van der Hoeven, Fast evaluation of holonomic functions, Theoretical Computer Science, v.210 n.1, p.199-215, Jan. 6, 1999 [doi>10.1016/S0304-3975(98)00102-9]
• 26: Joris van der Hoeven, Fast evaluation of holonomic functions near and in regular singularities, Journal of Symbolic Computation, v.31 n.6, p.717-743, June 2001 [doi>10.1006/jsco.2000.0474]
• 27: H. Volklein. Groups as Galois Groups. Cambrige Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1997.
• 28: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 29: R. J. Walker. Algebraic Curves. Springer Verlag, Berlin-New York, 1978.
• 30: P. G. Walsh. On the Complexity of Rational Puiseux Expansions. Pacific Journal of Mathematics, 188:369--387, 1999.
• 31: P. G. Walsh, A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function, Mathematics of Computation, v.69 n.231, p.1167-1182, July 2000 [doi>10.1090/S0025-5718-00-01246-1]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations

General Terms:
Experimentation, Performance, Reliability

Keywords:
Riemann surfaces, algebraic curves, monodromy, symbolic-numeric computation