Computational Complexity - Research Seminar
Alexey Pospelov: Fast Polynomial Multiplication
July 14, 2010, 10:15 a.m.
E 1 3, Room 415
We give an overview of the currently fastest algorithms for multiplication of polynomials over arbitrary fields. We are concerned with total arithmetical complexity of the problem, that is we count all arithmetical operations used by an algorithm and each operation has unit cost. We also work in the algebraic model, that is, field elements are given as algebraic entities and we don't have access, e.g. to their bit representations. The goal of this talk is to prepare necessary background for the forthcoming talk on our recent generalization, improvement and limitation results of these algorithms.
We start with defining the Discrete Fourier Transformation (DFT) and an effective way of computing DFT by means of the Fast Fourier Transform algorithm (FFT). DFT can be used in a quite natural way for computing product of two degree N polynomials over a field where DFT is defined in O(N\log N) elementary arithmetical operations over the field. If DFT is not defined, there are numerous tricks to overcome this by using appropriate field extensions. We will outline only the ideas of the most important algorithms giving the best general upper bound of O(N\log N\log\log N) elementary arithmetical operations over the field to multiply two degree N polynomials: Schönhage-Strassen (1971), Schönhage (1976), Cantor-Kaltofen (1991).