Algoritmo de Odlyzko-Schönhage

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 | editar código-fonte]

  1. 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
  2. Gourdon, X., Numerical evaluation of the Riemann Zeta-function (em inglês)
  3. Gourdon (2004), The 1013 first zeros of the Riemann Zeta function, and zeros computation at very large height (em inglês)