Odlyzko–Schönhage algorithm

In mathematics, the Odlyzko-Schönhage algorithm is a fast algorithm for evaluating the Riemann zeta function at many equally spaced points, introduced by (Odlyzko & Schönhage 1988). The key point is the use of the fast Fourier transform to speed up the evaluation of Dirichlet series at a large collection of equally spaced values. This reduces the time to find the zeros of the zeta function with imaginary part at most T from about T^3/2+ε steps needed by the Riemann-Siegel formula to about T^1+ε steps.

The algorithm was used by Gourdon (2004) to verify the Riemann hypothesis for the first 10¹³ zeros of the zeta function.

References

• Gourdon, X., Numerical evaluation of the Riemann Zeta-function
• Gourdon (2004), The 10¹³ first zeros of the Riemann Zeta function, and zeros computation at very large height (PDF)
• Odlyzko, A. (1992), The 10²⁰-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