Complexity and Performance Results for Non FFT-Based Univariate Polynomial Multiplication
Muhammad F. I. Chowdhury, Marc Moreno Maza, Wei Pan, Éric Schost, Ilias Kotsireas, Roderick Melnik, Brian West · AIP conference proceedings · 2011
Today's parallel hardware architectures and computer memory hierarchies enforce revisiting fundamental algorithms which were often designed with algebraic complexity as the main complexity measure and with sequential running time as the main performance counter. This study is devoted to two algorithms of univariate polynomial multiplication; that are independent of the coefficient ring: the plain and the Toom‐Cook univariate multiplications. We analyze their cache complexity and report on their parallel implementations in Cilk++ [1].