The truncated fourier transform and applications | Zendy

Joris van der Hoeven | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The truncated fourier transform and applications

Author(s) -

Joris van der Hoeven

Publication year - 2004

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

ISBN - 1-58113-827-X

DOI - 10.1145/1005285.1005327

Subject(s) - multiplication (music) , fourier transform , logarithm , fast fourier transform , sine and cosine transforms , fourier series , mathematics , polynomial , algorithm , discrete fourier transform (general) , computer science , short time fourier transform , fourier analysis , combinatorics , mathematical analysis

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research