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
0
votes
1answer
26 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
25 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
66 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
40 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
19 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
26 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
45 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
45 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
161 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
35 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
116 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
99 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
188 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
126 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 ...