Faster Polynomial Multiplication via Discrete Fourier Transforms

Details Faster Polynomial Multiplication via Discrete Fourier Transforms Faster Polynomial Multiplication via Discrete Fourier Transforms

2010-10-06

arxiv.org/abs/1010.1101v1

Computer Science

Computational Complexity

26 pages, submitted to a conference

Scientific paper

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\"onhage-Strassen's algorithm over arbitrary fields of characteristic different from 2, Sch\"onhage'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\"onhage-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\"urer'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\"urer 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.

Affiliated with

Also associated with

No associations

Rating

Faster Polynomial Multiplication via Discrete Fourier Transforms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster Polynomial Multiplication via Discrete Fourier Transforms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Polynomial Multiplication via Discrete Fourier Transforms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427419