In mathematics, the Odlyzko–Schönhage algorithm is a fast algorithm for evaluating the Riemann zeta function at many points, introduced by (Odlyzko & Schönhage 1988). The main point is the use of the fast Fourier transform to speed up the evaluation of a finite Dirichlet series of length N at O(N) equally spaced values from O(N2) to O(N1+ε) steps (at the cost of storing O(N1+ε) intermediate values). The Riemann–Siegel formula used for calculating the Riemann zeta function with imaginary part T uses a finite Dirichlet series with about N = T1/2 terms, so when finding about N values of the Riemann zeta function it is sped up by a factor of about T1/2. This reduces the time to find the zeros of the zeta function with imaginary part at most T from about T3/2+ε steps to about T1+ε steps.
The algorithm can be used not just for the Riemann zeta function, but also for many other functions given by Dirichlet series.
- Gourdon, X., Numerical evaluation of the Riemann Zeta-function
- Gourdon (2004), The 1013 first zeros of the Riemann Zeta function, and zeros computation at very large height
- Odlyzko, A. (1992), The 1020-th zero of the Riemann zeta function and 175 million of its neighbors This unpublished book describes the implementation of the algorithm and discusses the results in detail.
- Odlyzko, A. M.; Schönhage, A. (1988), "Fast algorithms for multiple evaluations of the Riemann zeta function", Trans. Amer. Math. Soc., 309 (2): 797–809, doi:10.2307/2000939, JSTOR 2000939, MR 0961614