Fast algorithms for multiple evaluations of the Riemann zeta function
HTML articles powered by AMS MathViewer
- by A. M. Odlyzko and A. Schönhage PDF
- Trans. Amer. Math. Soc. 309 (1988), 797-809 Request permission
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
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
- P. T. Bateman and E. Grosswald, On Epstein’s zeta function, Acta Arith. 9 (1964), 365–373. MR 179141, DOI 10.4064/aa-9-4-365-373 E. Bombieri and D. A. Hejhal, Sur les zéros des fonctions zeta d’Epstein, C.R. Acad. Sci. Paris 304 (1987), 213-217.
- Richard P. Brent, On the zeros of the Riemann zeta function in the critical strip, Math. Comp. 33 (1979), no. 148, 1361–1372. MR 537983, DOI 10.1090/S0025-5718-1979-0537983-2
- D. Davies, An approximate functional equation for Dirichlet $L$-functions, Proc. Roy. Soc. London Ser. A 284 (1965), 224–236. MR 173352, DOI 10.1098/rspa.1965.0060
- Max Deuring, Asymptotische Entwicklungen der Dirichletschen $L$-Reihen, Math. Ann. 168 (1967), 1–30 (German). MR 213309, DOI 10.1007/BF01361542 H. M. Edwards, Riemann’s zeta function, Academic Press, 1974. W. Gabcke, Neue Herleitung und explicite Restabschätzung der Riemann-Siegel-Formel, Ph.D. Dissertation, Göttingen, 1979.
- N. Gastinel, Inversion d’une matrice généralisant la matrice de Hilbert, Chiffres 3 (1960), 149–152 (French, with English, German and Russian summaries). MR 123585 A. Gerasoulis, M. G. Grigoriadis, and Liping Sun, A fast algorithm for Trummer’s problem, SIAM J. Sci. Statist. Comput. 8 (1987), s135-s138. G. Golub, Trummer’s problem, SIGACT News 17 (1985), p. 17.2.12. Handbook of mathematical functions (M. Abramowitz and I. A. Stegun, eds.), National Bureau of Standards, Washington, D.C., 9th printing, 1970. A. Ivic, The Riemann zeta-function, Wiley, 1985.
- J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing $\pi (x)$: the Meissel-Lehmer method, Math. Comp. 44 (1985), no. 170, 537–560. MR 777285, DOI 10.1090/S0025-5718-1985-0777285-5
- J. C. Lagarias and A. M. Odlyzko, On computing Artin $L$-functions in the critical strip, Math. Comp. 33 (1979), no. 147, 1081–1095. MR 528062, DOI 10.1090/S0025-5718-1979-0528062-9
- J. C. Lagarias and A. M. Odlyzko, Computing $\pi (x)$: an analytic method, J. Algorithms 8 (1987), no. 2, 173–191. MR 890871, DOI 10.1016/0196-6774(87)90037-X
- 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), no. 174, 667–681. MR 829637, DOI 10.1090/S0025-5718-1986-0829637-3
- A. M. Odlyzko, On the distribution of spacings between zeros of the zeta function, Math. Comp. 48 (1987), no. 177, 273–308. MR 866115, DOI 10.1090/S0025-5718-1987-0866115-0 —, Distribution of zeros of the Riemann zeta function: Conjectures and computations (in preparation).
- Atle Selberg and S. Chowla, On Epstein’s zeta-function, J. Reine Angew. Math. 227 (1967), 86–110. MR 215797, DOI 10.1515/crll.1967.227.86 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.
- E. C. Titchmarsh, The Theory of the Riemann Zeta-Function, Oxford, at the Clarendon Press, 1951. MR 0046485
- Manfred R. Trummer, An efficient implementation of a conformal mapping method based on the Szegő kernel, SIAM J. Numer. Anal. 23 (1986), no. 4, 853–872. MR 849287, DOI 10.1137/0723055
- A. M. Turing, A method for the calculation of the zeta-function, Proc. London Math. Soc. (2) 48 (1943), 180–197. MR 9612, DOI 10.1112/plms/s2-48.1.180
Additional Information
- © Copyright 1988 American Mathematical Society
- 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