DOI: https://doi.org/10.26089/NumMet.v17r318

Применение полиномиальных преобразований для быстрого вычисления двумерных сверток

Авторы

  • И.А. Калиновский
  • В.Г. Спицын

Ключевые слова:

двумерная свертка
полиномиальные преобразования
быстрые алгоритмы

Аннотация

Рассмотрен быстрый алгоритм вычисления двумерных сверток, основанный на полиномиальных преобразованиях Нуссбаумера. Предложена его эффективная программная реализация с использованием набора SIMD-инструкций Intel AVX. Показано, что для ограниченного диапазона размеров ядер достигается 50% увеличение производительности вычислений по сравнению с прямым алгоритмом и методом быстрой свертки на основе быстрого преобразования Фурье, реализованных в библиотеке Intel IPP.

Новые вычислительные технологии

Загрузки

Опубликован

2016-05-13

Выпуск

Том 17 (2016): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

И.А. Калиновский

Томский политехнический университет,
Институт кибернетики
Советская ул., 84/3, 634034, Томск
• аспирант

В.Г. Спицын

Томский политехнический университет,
Институт кибернетики
Советская ул., 84/3, 634034, Томск
• профессор

Библиографические ссылки

  1. E. C. Ifeachor and B. W. Jervis, Digital Signal Processing: A Practical Approach (Prentice-Hall, Harlow, 2002; Vil’yams, Moscow, 2004).
  2. H. J. Nussbaumer, Fast Fourier Transform and Convolution Algorithms (Springer, Heidelberg, 1982; Radio i Svyaz’, Moscow, 1985).
  3. D. J. Bernstein, “The Tangent FFT,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2007), Vol. 4851, pp. 291-300.
  4. Yu. V. Nesterenko, Number Theory (Akademiya, Moscow, 2008) [in Russian].
  5. A. O. Makarov and V. V. Starovoitov, Fast Algorithms for Computing Features on Digital Images , Preprint No. 1 (United Institute of Informatics Problems, Minsk, 2005).