Campus Event Calendar
Event Entry
What and Who
Fast Polynomial Multiplication
Alexey Pospelov
Fachrichtung Informatik - Saarbrücken / MMCI
Talk
AG 1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 14 July 2010
10:15
45 Minutes
E1 3
415
Saarbrücken
Abstract
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).
Contact
Christian Hoffmann
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Polynomial Multiplication, Fast Fourier Transform
gk-sek, 06/30/2010 14:56 -- Created document.