Fast Algorithms for Multiple Evaluations of the Riemann Zeta Function
Authors:
- A. M. OdlyzkoAOA. M. Odlyzko
- A. SchonhageASA. Schonhage
Open Access
- 1 October 1988
- journal article
- Published by JSTOR in Transactions of the American Mathematical Society
- Vol. 309 (2) , 797-809
Abstract
The best previously known algorithm for evaluating the Riemann zeta function, <!-- MATH $\zeta (\sigma + it)$ --> , with bounded and large to moderate accuracy (within <!-- MATH $\pm {t^{ - c}}$ --> for some 0$">, say) was based on the Riemann-Siegel formula and required on the order of operations for each value that was computed. New algorithms are presented in this paper which enable one to compute any single value of <!-- MATH $\zeta (\sigma + it)$ --> with fixed and <!-- MATH $T \leqslant t \leqslant T + {T^{1/2}}$ --> to within <!-- MATH $\pm {t^{ - c}}$ --> in <!-- MATH $O({t^\varepsilon })$ --> operations on numbers of bits for any <!-- MATH $\varepsilon > 0$ --> 0$">, for example, provided a precomputation involving <!-- MATH $O({T^{1/2 + \varepsilon }})$ --> operations and <!-- MATH $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 zeros in what is expected to be <!-- MATH $O({n^{1 + \varepsilon }})$ --> operations (as opposed to about operations for the previous method), as well as improved algorithms for the computation of various arithmetic functions, such as . 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 -functions, Epstein zeta functions, and other Dirichlet series.
Keywords
This publication has 13 references indexed in Scilit:
- Computing π(x): An analytic methodJournal of Algorithms, 1987
- On the Distribution of Spacings Between Zeros of the Zeta FunctionMathematics of Computation, 1987
- An Efficient Implementation of a Conformal Mapping Method Based on the Szegö KernelSIAM Journal on Numerical Analysis, 1986
- On the Zeros of the Riemann Zeta Function in the Critical Strip. IVMathematics of Computation, 1986
- Computing π(x): The Meissel-Lehmer MethodMathematics of Computation, 1985
- On the Zeros of the Riemann Zeta Function in the Critical StripMathematics of Computation, 1979
- On Computing Artin L-Functions in the Critical StripMathematics of Computation, 1979
- Asymptotische Entwicklungen der DirichletschenL-ReihenMathematische Annalen, 1967
- The Theory of the Riemann Zeta-functions. By E. C. Titchmarsh Pp. 346. 40s. 1951. (Oxford University Press)The Mathematical Gazette, 1952
- A Method for the Calculation of the Zeta-FunctionProceedings of the London Mathematical Society, 1945