“Odlyzko–Schönhage algorithm”的意思、由来-开放百科全书

词条

Odlyzko–Schönhage algorithm

释义

References

In mathematics, the Odlyzko–Schönhage algorithm is a fast algorithm for evaluating the Riemann zeta function at many points, introduced by {{harvs|author1-link=Andrew Odlyzko|last1=Odlyzko|last2=Schönhage|author2-link=Arnold Schönhage|year=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(N²) 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 {{harvtxt|Gourdon|2004}} to verify the Riemann hypothesis for the first 10¹³ zeros of the zeta function.

References

{{citation|first=X.|last=Gourdon|url=http://numbers.computation.free.fr/Constants/Miscellaneous/zetaevaluations.html|title=Numerical evaluation of the Riemann Zeta-function}}
{{citation|url=http://numbers.computation.free.fr/Constants/Miscellaneous/zetazeroscompute.html|last=Gourdon|title=The 10¹³ first zeros of the Riemann Zeta function, and zeros computation at very large height|year=2004}}
{{citation|first=A.|last= Odlyzko|title=The 10²⁰-th zero of the Riemann zeta function and 175 million of its neighbors|year= 1992|url=http://www.dtc.umn.edu/~odlyzko/unpublished/index.html}} This unpublished book describes the implementation of the algorithm and discusses the results in detail.
{{citation|mr=0961614

|author1-link=Odlyzko|author2-link=Schönhage|last=Odlyzko|first= A. M.|last2= Schönhage|first2= A.
|title=Fast algorithms for multiple evaluations of the Riemann zeta function
|journal=Trans. Amer. Math. Soc.|volume= 309 |year=1988|issue= 2|pages= 797–809
|doi=10.2307/2000939|jstor=2000939}}{{DEFAULTSORT:Odlyzko-Schonhage algorithm}}{{algorithm-stub}}

3 : Analytic number theory|Computational number theory|Zeta and L-functions

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。