Em matemática, o algoritmo de Odlyzko-Schönhage é um algoritmo rápido para avaliar a função zeta de Riemann em muitos pontos, introduzido por Odlyzko e Schönhage (1988)[1]. O ponto chave é o uso da transformada rápida de Fourier para acelerar a avaliação de uma série de Dirichlet finita de comprimento N em O(N) igualmente espaçada em passos de valores de O(N2) a O(N1+ε) (ao custo de armazenar os valores u]intermediários O(N1+ε) ). A fórmula de Riemann–Siegel usada para o cálculo da função zeta de Riemann com parte imaginária T usa uma série de Dirichlet finita com aproximadamente N = T1/2 termos, então quando encontra aproximadamente N valores da função zeta de Riemann ela acelera-se por um fator de aproximadamente T1/2. Isto reduz o tempo para encontrar os zeros da função zeta com parte imaginária em quase T para aproximadamente T3/2+ε passos para aproximadamente T1+ε passos.[2]
O algoritmo pode se usado não só para a função zeta de Riemann, mas também para muitas outras funções dadas pela séries de Dirichlet.
O algoritmo foi usado por Gourdon (2004)[3] para verificar a hipótese de Riemann para os primeiros 1013 da função zeta.
Referências
editar- ↑ Odlyzko, A. M.; Schönhage, A. (1988), "Fast algorithms for multiple evaluations of the Riemann zeta function", Trans. Amer. Math. Soc. 309 (2): 797–809, doi:10.2307/2000939, MR0961614
- ↑ Gourdon, X., Numerical evaluation of the Riemann Zeta-function (em inglês)
- ↑ Gourdon (2004), The 1013 first zeros of the Riemann Zeta function, and zeros computation at very large height (em inglês)
- Odlyzko, A.; The 1020-th zero of the Riemann zeta function and 175 million of its neighbors; 1992 Este livro não publicado descreve a implementação do algoritmo e discute os resultados em detalhe.
