Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-152 | 6th October 2010 11:06

Faster Polynomial Multiplication via Discrete Fourier Transforms


Authors: Alexey Pospelov
Publication: 6th October 2010 13:51
Downloads: 3549


We study the complexity of polynomial multiplication over arbitrary fields. We present a unified approach that generalizes all known asymptotically fastest algorithms for this problem. In particular, the well-known algorithm for multiplication of polynomials over fields supporting DFTs of large smooth orders, Schönhage-Strassen's algorithm over arbitrary fields of characteristic different from 2, Schönhage's algorithm over fields of characteristic 2, and Cantor-Kaltofen's algorithm over arbitrary algebras - all appear to be instances of this approach. We also obtain faster algorithms for polynomial multiplication over certain fields which do not support DFTs of large smooth orders.

We prove that the Schönhage-Strassen's upper bound cannot be improved further over the field of rational numbers if we consider only algorithms based on consecutive applications of DFT, as all known fastest algorithms are. We also explore the ways to transfer the recent Fürer's algorithm for integer multiplication to the problem of polynomial multiplication over arbitrary fields of positive characteristic.

This work is inspired by the recent improvement for the closely related problem of complexity of integer multiplication by Fürer and its consequent modular arithmetic treatment due to De, Kurur, Saha, and Saptharishi. We explore the barriers in transferring the techniques for solutions of one problem to a solution of the other.

ISSN 1433-8092 | Imprint