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
2
votes
0answers
24 views

Fast calculations using fast-Fourier convolution

Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$. We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by ...
0
votes
0answers
64 views

Recursive-FFT Algorithm in CLRS

In this FFT algorithm (as per CLRS), in line number 4, shouldn't the angle be $-2\pi i/n$ and not $+2\pi i/n$? The same algorithm is used in cp-algorithms as well, but in python, ...
0
votes
1answer
38 views

Finding $Aeven(x)$ and $Aodd(x)$ for a Fast Fourier Transform (FFT) problem?

In this article about FFT the author used FFT on this polynomial. $A(x) = 3+2x+3x^2+4x^3$ Using $ A(x)= Aeven(x^2) + xAodd(x^2)$ the author determined the following for $Aeven(x)$ and $Aodd(x)$ $ ...
0
votes
1answer
40 views

Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T

Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
0
votes
0answers
30 views

Cost of solving linear equation using FFT algorithm

I have a linear equation $Cx=b$ where $C$ is $n \times n$ circulant matrix. By applying circular convolution process, vector $x$ can be solved using Fast Fourier Transform (FFT) to transform the ...
3
votes
1answer
73 views

Computing coefficients of $p(x)^n$ in time $O(n \log n)$

For homework I've to give an algorithm that computes the coefficients of the polynomial $p(x)^n$ in time $O(n\log n)$, where $p(x)$ is a polynomial of degree 7. As an hint I'm told to consider first ...
0
votes
1answer
43 views

Multiplying two 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^iy^j \quad\text{and}\quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^iy^j $$ Show how ...
0
votes
1answer
24 views

Multiplication of polynomials in value representation as done for Fast Fourier Transform

I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the ...
1
vote
1answer
30 views

How polynomial interpolation of polynomial multiplication algorithm works?

I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following: Algorithm [DPV, p. 60] Input: Coefficients of two polynomials. ...
1
vote
0answers
50 views

Efficient Fast Fourier Transform to calculate the expected value

Suppose two people A and B draw a list of cards with difference scores n = {0, 1, 2, ..., n - 1}. Let $i \in$n such that $i \in [0, n - 1].$ Let $a_i$ be the probability that the person A draws a card ...
2
votes
0answers
48 views

Multipoint evaluation of a given polynomial

You are given a polynomial of degree n. We have to find the value of the polynomial at n different points in O(n(log(n))^2). The answer should be modulo 998244353. I have read various blogs on it and ...
1
vote
1answer
165 views

Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$

Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$. For eg. Let the array be $1,2,3$ then my answer will be calculated as- $(2-1)$.$(...
1
vote
0answers
39 views

Butterfly diagram from Cooley-Tukey algorithm

I am trying to understand the logic of this algorithm so I can implement my own but I am not understanding this diagram I see appearing many times in a fair few articles on the topic. I am teaching ...
1
vote
0answers
53 views

How to compute the first n coefficients using number theoretic transform (NTT)?

I need to find the first $n$ coefficients of $$\prod_{i = 1}^{i = q}(1 + x^{a_i})^{b_i}$$ modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity $O(n\log n)$ or $O(...
1
vote
0answers
134 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
46 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
113 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
191 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
157 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 ...