Algoritmo de Odlyzko-Schönhage

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
  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)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.