Parallel algorithms for polynomial multiplications

Thesis is about parallel algorithms for polynomial multiplications. Popularity of object is increasing every day, Owing to increasing demand on image processing applications and signal processing systems. Because of vertical scaling is getting harder and harder, horizontal scaling and making algorithms distributive, is the key in solving lot of actual problems. Thesis aims to create new methods and optimize existing algorithms to accelerate multiplication in some specific rings. We will discuss several algorithms and their distributive modifications: School book multiplication it's scalable algorithm and applications. Karatsuba's method and the way to make it parallel, but main subject of research will be cyclic discrete Fourier transforms in specific. Main theoretical result was to make two unfriendly optimizations work together. In practice we managed to make several optimizations during implementation about reducing number of real multiplications achieved better cache efficiency and finally as a result we got 1.5x-2.0x running time improvement against existing library solutions. Main goal is to create a framework to support people who uses convolutions, big integer multiplications, or time-domain to frequency domain transforms