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
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?)

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

Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society