Parallel algorithms for fast negacyclic convolutions

Author: Beka Barbakadze
Keywords: GPGPU convolution, cache efficient, parallel convolution
Annotation:

In this thesis we investigate the improvement methods of parallel algorithms for polynomial multiplication in terms of GPU parallelization that is very important in many different areas of theory and practice such as image processing, signal processing, cryptography etc. In the last decades, the idea of vertical scaling has reached its limits and the idea of horizontal scaling and distributive algorithms gain more attention. In this work, we aim to improve the implementation of existing methods and accelerate the computation of polynomial multiplication in specific rings. Several algorithms (starting with the school method an several parallel algorithms such as Karatsuba's or Schonhage- ̈ Strassen's) multiplication method, and their parallel modifications are analysed but the main topic is to improve the computation of the discrete Fourier transform. The main theoretical result is the synchronisation of two seemingly non-compatible algorithms due to which we can reduce the number of real multiplications and achieve better cache efficiency that accelerates the computational time by the factor 1.5 to 2.0 compared to other known systems. In the future we intend to create a library of efficient GPU implementations for DFT and fast polynomial multiplication.