Questions tagged [fast-fourier-transform]

Fast Fourier transformation computes discrete Fourier transformation efficiently. It is used in many areas including fast polynomial multiplication, signal processing and computing sequence convolutions efficiently.

Filter by
Sorted by
Tagged with
1
vote
0answers
43 views

Understanding the recursive fast Fourier Transform Algorithm from CLRS

Consider the following recursive fast Fourier transform algorithm from CLRS: I believe that I understand this algorithm correctly: you split the input coefficients into the odd and even terms, ...
1
vote
0answers
38 views

Optimization of modular exponentiation using fft [duplicate]

My math/cs professor said it is trivial to optimize a modular exponentiation ($a^b \bmod c$) problem using fft, yet I am not able to understand how to do this. I found 3 papers on this ([1], [2], ...
1
vote
0answers
49 views

Optimization of modular exponentiation using fft

My math prof said it is trivial to optimize a modular exponentiation (a^b mod c) problem for large values using fft, but I can't figure out how to do this. I looked it up and found a few papers on it (...
0
votes
0answers
99 views

Multiplying bivariate polynomials using FFT

Consider two bivariate polynomials of degree at most $n-1$ in each variable: $$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^i y^j \quad \text{and} \quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^i y^j. $$ ...
2
votes
1answer
51 views

Polynomial multiplications and counting

I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically ...