Algoritmo de Odlyzko-Schönhage - Odlyzko–Schönhage algorithm

Em matemática, o Algoritmo de Odlyzko-Schönhage é um rápido algoritmo para avaliar a função zeta de Riemann em muitos pontos, introduzidas pela ( Odlyzko & Schönhage  1988 ). O ponto principal é a utilização da transformada rápida de Fourier para acelerar a avaliação de um finito série Dirichlet de comprimento N , em O ( N ) igualmente espaçados valores de O ( N 2 ) a O ( N 1 + ε ) etapas (na custo de armazenar O ( N 1 + ε ) valores intermédios). A fórmula de Riemann-Siegel usadas para calcular a função Riemann zeta com a parte imaginária T utiliza uma série de Dirichlet finito com cerca N = T 1/2 termos, por isso, quando encontrar sobre N valores da função Riemann zeta-lo é acelerado por um factor de sobre T 1/2 . Isto reduz o tempo para encontrar os zeros da função zeta com a parte imaginária no máximo T a partir de cerca de T 3/2 + £ passos a cerca de T 1 + £ passos.

O algoritmo pode ser usado não apenas para a função zeta de Riemann, mas também para muitas outras funções dadas por série de Dirichlet.

O algoritmo foi utilizado por Gourdon (2004) para verificar a hipótese de Riemann para os 10 primeiros 13 zeros da função zeta.

Referências

  • Gourdon, X., avaliação numérica da Zeta-função de Riemann
  • Gourdon (2004), The 10 13 primeiros zeros da função Riemann Zeta, e os zeros na computação muito grande altura
  • Odlyzko, A. (1992), O 10 20 -ésimo zero da função Riemann zeta e 175 milhões de seus vizinhos Este livro inédito descreve a implementação do algoritmo e discute os resultados em detalhe.
  • Odlyzko, AM ; Schönhage, A. (1988), "algoritmos rápidos para várias avaliações da função zeta de Riemann", Trans. Amer. Matemática. Soc. , 309 (2): 797-809, DOI : 10,2307 / 2000939 , JSTOR  2.000.939 , MR  0.961.614