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