Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Fast evaluation of modular functions using Newton iterations and the AGM


Author: Régis Dupont
Journal: Math. Comp. 80 (2011), 1823-1847
MSC (2000): Primary 65D20; Secondary 33E05, 11Y16
Published electronically: March 4, 2011
MathSciNet review: 2785482
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present an asymptotically fast algorithm for the numerical evaluation of modular functions such as the elliptic modular function $ j$. Our algorithm makes use of the natural connection between the arithmetic-geometric mean (AGM) of complex numbers and modular functions. Through a detailed complexity analysis, we prove that for a given $ \tau $, evaluating $ N$ significative bits of $ j(\tau )$ can be done in time $ O(\mathcal{M}(N)\log N)$, where $ \mathcal{M}(N)$ is the time complexity for the multiplication of two $ N$-bit integers. However, this is only true for a fixed $ \tau $ and the time complexity of this first algorithm greatly increases as $ \mathrm{Im}(\tau )$ does. We then describe a second algorithm that achieves the same time complexity independently of the value of $ \tau $ in the classical fundamental domain  $ \mathcal{F}$. We also show how our method can be used to evaluate other modular forms, such as the Dedekind $ \eta $ function, with the same time complexity.


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

  • 1. Harald Baier and Günter Köhler, How to compute the coefficients of the elliptic modular function 𝑗(𝑧), Experiment. Math. 12 (2003), no. 1, 115–121. MR 2002678 (2004h:11039)
  • 2. Jonathan M. Borwein and Peter B. Borwein, Pi and the AGM, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons Inc., New York, 1987. A study in analytic number theory and computational complexity; A Wiley-Interscience Publication. MR 877728 (89a:11134)
  • 3. Richard P. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic computational complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1975), Academic Press, New York, 1976, pp. 151–176. MR 0423869 (54 #11843)
  • 4. David A. Cox, The arithmetic-geometric mean of Gauss, Enseign. Math. (2) 30 (1984), no. 3-4, 275–330. MR 767905 (86a:01027)
  • 5. M. Deuring, Die Klassenkörper der komplexen Multiplikation, Enzyklopädie der mathematischen Wissenschaften: Mit Einschluss ihrer Anwendungen, Band I 2, Heft 10, Teil II (Article I 2, vol. 23, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1958 (German). MR 0167481 (29 #4754)
  • 6. R. Dupont.
    Borchardt's mean, theta constants in genus $ 2$ and applications, 2005.
    In preparation.
  • 7. Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089–1107. MR 2476572 (2010h:11097), http://dx.doi.org/10.1090/S0025-5718-08-02200-X
  • 8. A. Enge.
    The complexity of modular polynomial computation via floating point evaluation and interpolation, 2005.
    In preparation.
  • 9. Andreas Enge and François Morain, Comparing invariants for class fields of imaginary quadratric fields, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 252–266. MR 2041089 (2005a:11179), http://dx.doi.org/10.1007/3-540-45455-1_21
  • 10. A. Enge and P. Zimmermann.
    MPC - Multiprecision Complex arithmetic library version 0.4, 2004.
    Available at http://www.loria.fr/~zimmerma/free/.
  • 11. C. F. Gauss.
    Werke.
    Dieterich, Göttingen, 1866-1933.
  • 12. T. Granlund et al.
    GMP - GNU Multiprecision library version 4.1, 2002.
    Available at http://www.swox.com/gmp/.
  • 13. G. Hanrot, V. Lefèvre, P. Pélissier, and P. Zimmermann.
    MPFR - Multiple Precision Floating point computations with exact Rounding library version 2.1.0, 2004.
    Available at http://www.mpfr.org.
  • 14. David Mumford, Tata lectures on theta. I, Progress in Mathematics, vol. 28, Birkhäuser Boston Inc., Boston, MA, 1983. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. MR 688651 (85h:14026)
  • 15. Bruno Schoeneberg, Elliptic modular functions: an introduction, Springer-Verlag, New York, 1974. Translated from the German by J. R. Smart and E. A. Schwandt; Die Grundlehren der mathematischen Wissenschaften, Band 203. MR 0412107 (54 #236)
  • 16. H. Weber.
    Lehrbuch der Algebra, volume III.
    Chelsea Publishing Company, New York, 1902.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65D20, 33E05, 11Y16

Retrieve articles in all journals with MSC (2000): 65D20, 33E05, 11Y16


Additional Information

Régis Dupont
Affiliation: INRIA Futurs, Projet TANC, Laboratoire LIX, École polytechnique, 91128 Palaiseau, France
Email: regis.dupont@m4x.org

DOI: http://dx.doi.org/10.1090/S0025-5718-2011-01880-6
PII: S 0025-5718(2011)01880-6
Keywords: Modular functions, numerical evaluation, AGM, Newton iterations
Received by editor(s): May 27, 2005
Published electronically: March 4, 2011
Article copyright: © Copyright 2011 Régis Dupont