Odlyzko–Schönhage-algoritm
Inom matematiken är Odlyzko–Schönhage-algoritmen en snabb algoritm för att utvärdera Riemanns zeta-funktion på många punkter, introducerad av ( Odlyzko & Schönhage 1988 ). Huvudpoängen är användningen av den snabba Fouriertransformen för att påskynda utvärderingen av en ändlig Dirichlet-serie med längd N vid O( N ) jämnt fördelade värden från O( N 2 ) till O( N 1+ε ) steg (vid kostnad för att lagra O( N 1+ε ) mellanvärden). Riemann -Siegel-formeln som används för att beräkna Riemann zeta-funktionen med imaginär del T använder en ändlig Dirichlet-serie med ungefär N = T 1/2 termer, så när man hittar ungefär N värden för Riemann zeta-funktionen snabbas den upp med en faktor på ca T 1/2 . Detta minskar tiden för att hitta nollorna för zetafunktionen med imaginär del som högst T från ca T 3/2+ε -steg till ca T 1+ε -steg.
Algoritmen kan användas inte bara för Riemann zeta-funktionen, utan också för många andra funktioner som ges av Dirichlet-serien.
Algoritmen användes av Gourdon (2004) för att verifiera Riemann-hypotesen för de första 10 13 nollorna i zetafunktionen.
- Gourdon, X., Numerisk utvärdering av Riemann Zeta-funktionen
- Gourdon (2004), De 10 13 första nollorna i Riemann Zeta-funktionen och nollberäkningar på mycket stor höjd
- Odlyzko, A. (1992), Den 10 20 :e nollan av Riemann zeta-funktionen och 175 miljoner av dess grannar. Denna opublicerade bok beskriver implementeringen av algoritmen och diskuterar resultaten i detalj.
- Odlyzko, AM ; Schönhage, A. (1988), "Snabba algoritmer för flera utvärderingar av Riemann zeta-funktionen", Trans. Amer. Matematik. Soc. , 309 (2): 797–809, doi : 10.2307/2000939 , JSTOR 2000939 , MR 0961614