Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Fast evaluation of modular functions using Newton iterations and the AGM
HTML articles powered by AMS MathViewer

by Régis Dupont PDF
Math. Comp. 80 (2011), 1823-1847

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
  • Harald Baier and Günter Köhler, How to compute the coefficients of the elliptic modular function $j(z)$, Experiment. Math. 12 (2003), no. 1, 115–121. MR 2002678
  • 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
  • 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
  • David A. Cox, The arithmetic-geometric mean of Gauss, Enseign. Math. (2) 30 (1984), no. 3-4, 275–330. MR 767905
  • 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
  • R. Dupont. Borchardt’s mean, theta constants in genus $2$ and applications, 2005. In preparation.
  • Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089–1107. MR 2476572, DOI 10.1090/S0025-5718-08-02200-X
  • A. Enge. The complexity of modular polynomial computation via floating point evaluation and interpolation, 2005. In preparation.
  • 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, DOI 10.1007/3-540-45455-1_{2}1
  • A. Enge and P. Zimmermann. mpc – Multiprecision Complex arithmetic library version 0.4, 2004. Available at http://www.loria.fr/~zimmerma/free/.
  • C. F. Gauss. Werke. Dieterich, Göttingen, 1866–1933.
  • T. Granlund et al. gmp – GNU Multiprecision library version 4.1, 2002. Available at http://www.swox.com/gmp/.
  • 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.
  • 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, DOI 10.1007/978-1-4899-2843-6
  • Bruno Schoeneberg, Elliptic modular functions: an introduction, Die Grundlehren der mathematischen Wissenschaften, Band 203, Springer-Verlag, New York-Heidelberg, 1974. Translated from the German by J. R. Smart and E. A. Schwandt. MR 0412107
  • 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
  • Received by editor(s): May 27, 2005
  • Published electronically: March 4, 2011
  • © Copyright 2011 Régis Dupont
  • Journal: Math. Comp. 80 (2011), 1823-1847
  • MSC (2000): Primary 65D20; Secondary 33E05, 11Y16
  • DOI: https://doi.org/10.1090/S0025-5718-2011-01880-6
  • MathSciNet review: 2785482