TY - JOUR

T1 - Fast algorithms for multiple evaluations of the riemann zeta function

AU - Odlyzko, A. M.

AU - Schônhage, A.

PY - 1988/10

Y1 - 1988/10

N2 - The best previously known algorithm for evaluating the Riemann zeta function, ç(σ+ it), with o bounded and t large to moderate accuracy (within ±t˜c for some c > 0, say) was based on the Riemann-Siegel formula and required on the order of t1/2 operations for each value that was computed. New algorithms are presented in this paper which enable one to compute any single value of ç(a + it) with a fixed and T < t < T + T1/2 to within ±t˜c in 0(t£) operations on numbers of O(logi) bits for any e > 0, for example, provided a precomputation involving 0(Tl/2+e) operations and 0(Tlf2Jt£) 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 0(n1+£) operations (as opposed to about n3/2 operations for the previous method), as well as improved algorithms for the computation of various arithmetic functions, such as n(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.

AB - The best previously known algorithm for evaluating the Riemann zeta function, ç(σ+ it), with o bounded and t large to moderate accuracy (within ±t˜c for some c > 0, say) was based on the Riemann-Siegel formula and required on the order of t1/2 operations for each value that was computed. New algorithms are presented in this paper which enable one to compute any single value of ç(a + it) with a fixed and T < t < T + T1/2 to within ±t˜c in 0(t£) operations on numbers of O(logi) bits for any e > 0, for example, provided a precomputation involving 0(Tl/2+e) operations and 0(Tlf2Jt£) 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 0(n1+£) operations (as opposed to about n3/2 operations for the previous method), as well as improved algorithms for the computation of various arithmetic functions, such as n(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.

UR - http://www.scopus.com/inward/record.url?scp=0008476113&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0008476113&partnerID=8YFLogxK

U2 - 10.1090/S0002-9947-1988-0961614-2

DO - 10.1090/S0002-9947-1988-0961614-2

M3 - Article

AN - SCOPUS:0008476113

SN - 0002-9947

VL - 309

SP - 797

EP - 809

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

IS - 2

ER -