Application of polynomial transforms for fast 2D convolutions

Authors

  • I.A. Kalinovskii Tomsk Polytechnic University
  • V.G. Spitsyn Tomsk Polytechnic University

DOI:

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

Keywords:

2D convolution, polynomial transform, fast algorithms

Abstract

A fast algorithm for computing 2D convolutions based on the Nussbaumer polynomial transforms is considered. Its efficient implementation is proposed with the use of Intel AVX SIMD instructions. It is shown that, for a limited range of convolution kernels, the performance increases by 50% in comparison with the direct algorithm and with the method of fast convolution based on the fast Fourier transform implemented in the Intel IPP library.

Author Biographies

I.A. Kalinovskii

Tomsk Polytechnic University,
School of Computer Science & Robotics
• PhD Student

V.G. Spitsyn

Tomsk Polytechnic University,
School of Computer Science & Robotics
• Professor

References

  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).
New computational technologies

Downloads

Published

13-05-2016

How to Cite

Калиновский И., Спицын В. Application of Polynomial Transforms for Fast 2D Convolutions // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2016. 17. 197-203. doi 10.26089/NumMet.v17r318

Issue

Vol. 17 (2016): Issue 3.

Section

Section 1. Numerical methods and applications