In mathematics, the Odlyzko–Schönhage algorithm is a fast
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for evaluating the
Riemann zeta function at many points, introduced by . The main point is the use of the
fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in t ...
to speed up the evaluation of a finite
Dirichlet series
In mathematics, a Dirichlet series is any series of the form
\sum_^\infty \frac,
where ''s'' is complex, and a_n is a complex sequence. It is a special case of general Dirichlet series.
Dirichlet series play a variety of important roles in analyti ...
of length ''N'' at O(''N'') equally spaced values from O(''N''
2) to O(''N''
1+ε) steps (at the cost of storing O(''N''
1+ε) 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'' = ''T''
1/2 terms, so when finding about ''N'' values of the Riemann zeta function it is sped up by a factor of about ''T''
1/2. This reduces the time to find the zeros of the zeta function with imaginary part at most ''T'' from
about ''T''
3/2+ε steps to about ''T''
1+ε 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 to verify the
Riemann hypothesis
In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in pu ...
for the first 10
13 zeros of the zeta function.
References
*
*
* This unpublished book describes the implementation of the algorithm and discusses the results in detail.
*
Analytic number theory
Computational number theory
Zeta and L-functions
{{algorithm-stub