Об эффективности алгоритмов Рейдера-Винограда

Чернов В.М.

Аннотация:
Доказывается факт существования «исключительных» простых чисел, для которых алгоритмы Рейдера-Винограда вычисления дискретного преобразования Фурье и/или свертки соответствующей длины являются неэффективными. Приводятся достаточные условия «исключительности» в аналитической форме.

Ключевые слова:
дискретное преобразование Фурье, циклическая свертка, алгоритм Рейдера-Винограда, вычислительная сложность.

Литература:

  1. Блейхут, Р. Быстрые алгоритмы цифровой обработки сигналов / Р.Блейхут; пер.с англ. – М.: Мир, 1987. – 448 с.
  2. Макклеллан, Дж. Х. Применение теории чисел в цифровой обработке сигналов / Дж.Х. Маккеллан, Ч.М. Рейдер; пер.с англ. – М.: Радио и связь, 1983. – 263 с.
  3. Winograd, S. On Computing the Discrete Fourier Transform / S. Winograd // Proc. Nat. Acad. Sci. USA. – 1976. – Vol.73. – P.1005-1006.
  4. Winograd, S. On the Discrete Fourier Transform / S. Winograd // Math. Comp. – 1978. – Vol. 32. – P. 175-199.
  5. Власенко, В. А. Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов / В.А. Власенко, Ю.П. Лаппа, Л.П. Ярославский. – М.: Наука, 1990. – 180 с.
  6. Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток / Г. Нуссбаумер; пер.с англ. – М.: Радио и связь, 1985. – 248с.
  7. Erdös, P. On the normal number of prime factors of p-1 and some related problems concerning Euler's φ-function / P. Erdös // Quart. J. Oxford. – 1935. – Vol.6. – P.205-213.
  8. Prachar, K. Primzahlverteilung / K.Prachar. – Springer-Verlag, Berlin, 1957.
  9. Winograd, S. Arithmetic complexity of computations / S. Winograd. – SIAM, 1980. – 93p.
  10. Dubner, H. Large Sophie Germain Primes / H. Dubner. // Math. Comput. – 1996. – Vol. 65. –P. 393-396.
  11. Indlekofer, K. H. Largest Known Twin Primes and Sophie Germain Primes / K. H. Indlekofer, A. Járai // Math. Comput. – 1999. – Vol. 68. – P. 1317-1324.
  12. Ribenboim, P. Sophie Germain Primes / P. Ribenboim // The New Book of Prime Number Records. – New York, Springer-Verlag, 1996. – P. 329-332.
  13. Chernov, V.M. Data Algorithms: Galois vs. Rader and Winograd / V.M.Chernov // Pattern Recognition and Image Analysis. – 2003. – Vol. 13(1) . – P. 5–7.
  14. Чернов, В.М. Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований / В.М.Чернов. – М.: Физматлит, 2007.
  15. Chernov, V. Fast algorithm for «error-free» convolution computation using Mersenne-Lucas codes / V. Chernov // Chaos, Solitons and Fractals. – 2006. – Vol. 29. – P. 372-380.
© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20