×

zbMATH — the first resource for mathematics

Fast algorithms for multiple evaluations of the Riemann zeta function. (English) Zbl 0706.11047
Summary: 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\leq t\leq T+T^{1/2}\) to within \(3\pm t^{-c}\) in \(O(t^{\epsilon})\) operations on numbers of O(log t) bits for any \(\epsilon >0\), for example, provided a precomputation involving \(O(T^{+\epsilon})\) operations and \(O(T^{+\epsilon})\) 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+\epsilon})\) 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.

MSC:
11M06 \(\zeta (s)\) and \(L(s, \chi)\)
11Y35 Analytic computations
11M26 Nonreal zeros of \(\zeta (s)\) and \(L(s, \chi)\); Riemann and other hypotheses
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)
68Q25 Analysis of algorithms and problem complexity
11Y70 Values of arithmetic functions; tables
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0326.68005
[2] P. T. Bateman and E. Grosswald, On Epstein’s zeta function, Acta Arith. 9 (1964), 365 – 373. · Zbl 0128.27004
[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. · Zbl 0638.10043
[4] Richard P. Brent, On the zeros of the Riemann zeta function in the critical strip, Math. Comp. 33 (1979), no. 148, 1361 – 1372. · Zbl 0422.10031
[5] D. Davies, An approximate functional equation for Dirichlet \?-functions, Proc. Roy. Soc. Ser. A 284 (1965), 224 – 236. · Zbl 0131.04601
[6] Max Deuring, Asymptotische Entwicklungen der Dirichletschen \?-Reihen, Math. Ann. 168 (1967), 1 – 30 (German). · Zbl 0147.30502
[7] H. M. Edwards, Riemann’s zeta function, Academic Press, 1974. · Zbl 0315.10035
[8] W. Gabcke, Neue Herleitung und explicite Restabschätzung der Riemann-Siegel-Formel, Ph.D. Dissertation, Göttingen, 1979. · Zbl 0499.10040
[9] 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). · Zbl 0213.16303
[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. · Zbl 0618.65030
[11] G. Golub, Trummer’s problem, SIGACT News 17 (1985), p. 17.2.12.
[12] Handbook of mathematical functions , National Bureau of Standards, Washington, D.C., 9th printing, 1970.
[13] A. Ivic, The Riemann zeta-function, Wiley, 1985. · Zbl 0455.10025
[14] J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing \?(\?): the Meissel-Lehmer method, Math. Comp. 44 (1985), no. 170, 537 – 560. · Zbl 0564.10006
[15] J. C. Lagarias and A. M. Odlyzko, On computing Artin \?-functions in the critical strip, Math. Comp. 33 (1979), no. 147, 1081 – 1095. · Zbl 0409.12017
[16] J. C. Lagarias and A. M. Odlyzko, Computing \?(\?): an analytic method, J. Algorithms 8 (1987), no. 2, 173 – 191. · Zbl 0622.10027
[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), no. 174, 667 – 681. · Zbl 0585.10023
[18] A. M. Odlyzko, On the distribution of spacings between zeros of the zeta function, Math. Comp. 48 (1987), no. 177, 273 – 308. · Zbl 0615.10049
[19] -, Distribution of zeros of the Riemann zeta function: Conjectures and computations (in preparation).
[20] Atle Selberg and S. Chowla, On Epstein’s zeta-function, J. Reine Angew. Math. 227 (1967), 86 – 110. · Zbl 0166.05204
[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. C. Titchmarsh, The Theory of the Riemann Zeta-Function, Oxford, at the Clarendon Press, 1951. · Zbl 0042.07901
[23] 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. · Zbl 0596.30013
[24] A. M. Turing, A method for the calculation of the zeta-function, Proc. London Math. Soc. (2) 48 (1943), 180 – 197. · Zbl 0061.08304
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.