Faster Polynomial Multiplication via Discrete Fourier Transforms

DOI10.1007/978-3-642-20712-9_8zbMath1330.68121arXiv1010.1101OpenAlexW1526245840MaRDI QIDQ3007620

Alexey Pospelov

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.1101

zbMATH Keywords

discrete Fourier transformlower boundsalgebraic complexitypolynomial multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Numerical methods for discrete and fast Fourier transforms (65T50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On fast multiplication of polynomials over arbitrary algebras
• Fast multiplication of polynomials over fields of characteristic 2
• Simple multivariate polynomial multiplication
• Fast multiplication of large numbers
• Lower bounds on the bounded coefficient complexity of bilinear maps
• An algorithm for polynomial multiplication that does not depend on the ring constants
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Algebraic complexities and algebraic curves over finite fields