Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Fast algorithms for multiple evaluations of the Riemann zeta function


Authors: A. M. Odlyzko and A. Schönhage
Journal: Trans. Amer. Math. Soc. 309 (1988), 797-809
MSC: Primary 11M06; Secondary 11M26, 11Y35, 65E05, 68Q25
DOI: https://doi.org/10.1090/S0002-9947-1988-0961614-2
MathSciNet review: 961614
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The best previously known algorithm for evaluating the Riemann zeta function, $ \zeta (\sigma + it)$, with $ \sigma $ bounded and $ t$ large to moderate accuracy (within $ \pm {t^{ - c}}$ for some $ c > 0$, say) was based on the Riemann-Siegel formula and required on the order of $ {t^{1/2}}$ operations for each value that was computed. New algorithms are presented in this paper which enable one to compute any single value of $ \zeta (\sigma + it)$ with $ \sigma $ fixed and $ T \leqslant t \leqslant T + {T^{1/2}}$ to within $ \pm {t^{ - c}}$ in $ O({t^\varepsilon })$ operations on numbers of $ O(\log t)$ bits for any $ \varepsilon > 0$, for example, provided a precomputation involving $ O({T^{1/2 + \varepsilon }})$ operations and $ O({T^{1/2 + \varepsilon }})$ bits of storage is carried out beforehand. These algorithms lead to methods for numerically verifying the Riemann hypothesis for the first $ n$ zeros in what is expected to be $ O({n^{1 + \varepsilon }})$ operations (as opposed to about $ {n^{3/2}}$ operations for the previous method), as well as improved algorithms for the computation of various arithmetic functions, such as $ \pi (x)$. The new zeta function algorithms use the fast Fourier transform and a new method for the evaluation of certain rational functions. They can also be applied to the evaluation of $ L$-functions, Epstein zeta functions, and other Dirichlet series.


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

  • [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1974. MR 0413592 (54:1706)
  • [2] P. T. Bateman and E. Grosswald, On Epstein's zeta function, Acta Arith. 9 (1964), 365-384. MR 0179141 (31:3392)
  • [3] E. Bombieri and D. A. Hejhal, Sur les zéros des fonctions zeta d'Epstein, C.R. Acad. Sci. Paris 304 (1987), 213-217.
  • [4] R. P. Brent, On the zeros of the Riemann zeta function in the critical strip, Math. Comp. 33 (1979), 1361-1372. MR 537983 (80g:10033)
  • [5] D. Davies, An approximate functional equation for Dirichlet $ L$-functions, Proc. Roy. Soc. Ser. A 284 (1965), 224-236. MR 0173352 (30:3565)
  • [6] M. Deuring, Asymptotische Entwicklungen der Dirichletschen $ L$-Reihen, Math. Ann. 168 (1967), 1-30. MR 0213309 (35:4173)
  • [7] H. M. Edwards, Riemann's zeta function, Academic Press, 1974.
  • [8] W. Gabcke, Neue Herleitung und explicite Restabschätzung der Riemann-Siegel-Formel, Ph.D. Dissertation, Göttingen, 1979.
  • [9] N. Gastinel, Inversion d'une matrice généralisant la matrice de Hilbert, Chiffres 3 (1960), 149-152. MR 0123585 (23:A910)
  • [10] A. Gerasoulis, M. G. Grigoriadis, and Liping Sun, A fast algorithm for Trummer's problem, SIAM J. Sci. Statist. Comput. 8 (1987), s135-s138.
  • [11] G. Golub, Trummer's problem, SIGACT News 17 (1985), p. 17.2.12.
  • [12] Handbook of mathematical functions (M. Abramowitz and I. A. Stegun, eds.), National Bureau of Standards, Washington, D.C., 9th printing, 1970.
  • [13] A. Ivic, The Riemann zeta-function, Wiley, 1985.
  • [14] J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing $ \pi (x)$: The Meissel-Lehmer method, Math. Comp. 44 (1985), 537-560. MR 777285 (86h:11111)
  • [15] J. C. Lagarias and A. M. Odlyzko, On computing Artin $ L$-functions in the critical strip, Math. Comp. 33 (1979), 1081-1095. MR 528062 (80g:12010)
  • [16] -, Computing $ \pi (x)$: An analytic method, J. Algorithms 8 (1987), 173-191. MR 890871 (88k:11095)
  • [17] J. van de Lune, H. J. J. te Riele, and D. T. Winter, On the zeros of the Riemann zeta function in the critical strip. IV, Math. Comp. 46 (1986), 667-681. MR 829637 (87e:11102)
  • [18] A. M. Odlyzko, On the distribution of spacings between zeros of the zeta function, Math. Comp. 48 (1987), 273-308. MR 866115 (88d:11082)
  • [19] -, Distribution of zeros of the Riemann zeta function: Conjectures and computations (in preparation).
  • [20] A. Selberg and S. Chowla, On Epstein's zeta function, J. Reine Angew. Math. 227 (1967), 86-110. MR 0215797 (35:6632)
  • [21] C. L. Siegel, Über Riemanns Nachlass zur analytischen Zahlentheorie, Quellen und Studien zur Geschichte der Math. Astr. Phys. 2 (1932), 45-80. Reprinted in C. L. Siegel, Gesammelte Abhandlungen, vol. 1, Springer, 1966, pp. 275-310.
  • [22] E. L. Titchmarsh, The theory of the Riemann zeta-function, Oxford Univ. Press, 1951. MR 0046485 (13:741c)
  • [23] M. R. Trummer, An efficient implementation of a conformal mapping method using the Szegö kernel, SIAM J. Numer. Anal. 23 (1986), 853-872. MR 849287 (87k:30013)
  • [24] A. M. Turing, A method for the calculation of the zeta-function, Proc. London Math. Soc. (2) 48 (1943), 180-197. MR 0009612 (5:173a)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 11M06, 11M26, 11Y35, 65E05, 68Q25

Retrieve articles in all journals with MSC: 11M06, 11M26, 11Y35, 65E05, 68Q25


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1988-0961614-2
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society