Алгоритм Одлыцко – Шенхаге

В математике алгоритм Одлыжко–Шёнхаге — это быстрый алгоритм для вычисления дзета-функции Римана во многих точках, введенный ( Odlyzko & Schönhage  1988). Главным моментом является использование быстрого преобразования Фурье для ускорения вычисления конечного ряда Дирихле длины N при O( N ) равноотстоящих значениях от O( N ² ) до O( N ^1+ε ) шагов (за счет хранения O( N ^1+ε ) промежуточных значений). Формула Римана–Зигеля, используемая для вычисления дзета-функции Римана с мнимой частью T, использует конечный ряд Дирихле с примерно N = T ^1/2 членами, поэтому при нахождении примерно N значений дзета-функции Римана она ускоряется примерно в T ^1/2 раз . Это сокращает время нахождения нулей дзета-функции с мнимой частью не более T с примерно T ^3/2+ε шагов до примерно T ^1+ε шагов.

Алгоритм можно использовать не только для дзета-функции Римана, но и для многих других функций, заданных рядами Дирихле.

Алгоритм был использован Гурдоном (2004) для проверки гипотезы Римана для первых 1013 ^нулей дзета-функции.

• Гурдон, X., Численная оценка дзета-функции Римана.
• Гурдон (2004), 1013 первых нулей дзета-функции Римана и вычисление нулей на очень большой высоте
• Одлыжко, А. (1992), 1020-й ноль дзета-функции Римана и 175 миллионов его соседейВ этой неопубликованной книге описывается реализация алгоритма и подробно обсуждаются результаты.
• Одлыжко, AM ; Шёнхаге, A. (1988), "Быстрые алгоритмы для множественных оценок дзета-функции Римана", Trans. Amer. Math. Soc. , 309 (2): 797– 809, doi : 10.2307/2000939 , JSTOR  2000939, MR  0961614

Эта статья по теме алгоритмы или структуры данных является заглушкой . Вы можете помочь Википедии, расширив ее.

• в
• т
• е