Algoritmus Odlyzko – Schönhage - Odlyzko–Schönhage algorithm
V matematice je algoritmus Odlyzko – Schönhage rychlý algoritmus pro vyhodnocení Riemannovy zeta funkce v mnoha bodech, který zavedli ( Odlyzko & Schönhage 1988 ). Hlavním bodem je použití rychlé Fourierovy transformace k urychlení vyhodnocení konečné Dirichletovy řady délky N v O ( N ) rovnoměrně rozmístěných hodnotách od O ( N 2 ) do O ( N 1 + ε ) kroků (v náklady na skladování O ( N 1 + ε ) mezilehlých hodnot). Riemann-Siegel vzorec pro výpočet zeta Riemann s imaginární částí T používá konečný řadu Dirichlet se o N = T 1/2 pojmy, takže při hledání o N hodnot funkce Riemann zeta se zrychlil faktorem asi T 1/2 . To snižuje čas na nalezení nul funkce zeta s imaginární částí nanejvýš T z přibližně T 3/2 + ε kroků do přibližně T 1 + ε kroků.
Algoritmus lze použít nejen pro funkci Riemann zeta, ale také pro mnoho dalších funkcí daných Dirichletovou řadou.
Algoritmus použil Gourdon (2004) k ověření Riemannovy hypotézy pro prvních 10 13 nul funkce zeta.
Reference
- Gourdon, X., Numerické vyhodnocení funkce Riemann Zeta
- Gourdon (2004), 10 13 prvních nul funkce Riemann Zeta a výpočet nul ve velmi velké výšce
- Odlyzko, A. (1992), 10 20. nula funkce Riemann zeta a 175 milionů jejích sousedů Tato nepublikovaná kniha popisuje implementaci algoritmu a podrobně popisuje výsledky.
- Odlyzko, AM ; Schönhage, A. (1988), „Rychlé algoritmy pro vícenásobné vyhodnocení funkce Riemann zeta“, Trans. Amer. Matematika. Soc. , 309 (2): 797–809, doi : 10,2307 / 2000939 , JSTOR 2000939 , MR 0961614
Tento článek týkající se algoritmů nebo datových struktur je útržek . Wikipedii můžete pomoci rozšířením . |