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

Авторы

  • И.А. Калиновский Томский политехнический университет
  • В.Г. Спицын Томский политехнический университет

DOI:

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

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

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

Аннотация

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

Авторы

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

Томский политехнический университет,
Институт кибернетики
Советская ул., 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).

Загрузки

Опубликован

13-05-2016

Как цитировать

Калиновский И., Спицын В. Применение полиномиальных преобразований для быстрого вычисления двумерных сверток // Вычислительные методы и программирование. 2016. 17. 197-203. doi 10.26089/NumMet.v17r318

Выпуск

Раздел

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