Odlyzko–Schönhage algorithm
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 key point is the use of the fast Fourier transform to speed up the evaluation of finite Dirichlet series at a large collection of equally spaced values. This speeds up the Riemann-Siegel formula when used for many values with imaginary part T by a factor of about T1/2, and 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.
The algorithm was used by Gourdon (2004) to verify the Riemann hypothesis for the first 1013 zeros of the zeta function.
References
- 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 (PDF)
- 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, MR0961614