Abstract
In this paper, we present a truncated version of the classical Fast Fourier Transform. When applied to polynomial multiplication, this algorithm has the nice property of eliminating the "jumps" in the complexity at powers of two. When applied to the multiplication of multivariate polynomials or truncated multivariate power series, we gain a logarithmic factor with respect to the best previously known algorithms.
| Original language | English |
|---|---|
| Pages | 290-296 |
| Number of pages | 7 |
| DOIs | |
| Publication status | Published - 1 Jan 2004 |
| Externally published | Yes |
| Event | ISSAC 2004 - International Symposium on Symbolic and Algebraic Computation - Santander, Spain Duration: 4 Jul 2004 → 7 Jul 2004 |
Conference
| Conference | ISSAC 2004 - International Symposium on Symbolic and Algebraic Computation |
|---|---|
| Country/Territory | Spain |
| City | Santander |
| Period | 4/07/04 → 7/07/04 |
Keywords
- FFT-multiplication
- Fast Fourier Transform
- Jump phenomenon
- Multivariate polynomials
- Multivariate power series
- Truncated multiplication