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
1 answer
22 views

How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?

I have implemented an N-dimensional Non-Uniform Discrete Fourier Transform (in this case it's specifically an inverse NUDFT) using PyTorch. My goal with this implementation is to have a function which ...
kairocks2002's user avatar
2 votes
0 answers
79 views

Implementation of the divide-and-conquer principle for a specific summation formula

I have found two formulas in the work on pages 5 and 6, of which I am trying to develop a recursive implementation. The similarity to the DFT or FFT might be useful here. I divide this question into ...
TreeBook1's user avatar
5 votes
1 answer
2k views

Is there a faster algorithm than FFT if interested only on the maximum amplitude frequency?

Given an $n$ input array, is there an algorithm that is faster than Fast Fourier Transform if we are only interested in obtaining the maximum amplitude frequency? Looking at the Cooley–Tukey algorithm ...
Andrea Nardi's user avatar
1 vote
0 answers
59 views

Can FFT for prime $n$ be implemented as a product of $O(n\log(n))$ $2\times 2$ unitaries?

Consider normalized DFT (discrete Fourier transform) — a transform with input $x = (x_0,\dots,x_{n-1})$ and output $y=(y_0,\dots,y_{n-1})$ s.t. $$y_j = \frac1{\sqrt{n}} \sum_{l=0}^{n-1} x_l \omega^{jl}...
fiktor's user avatar
  • 111
1 vote
1 answer
60 views

product of every difference

Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $ 10^9 + 7 $ $$ \prod_{i < j} (arr[j] - arr[i]) \% (10^9 + 7) $$ Best approach I can ...
bihariforces's user avatar
1 vote
4 answers
178 views

XOR pair frequency queries

We are given an array of length $N$ and $Q$ queries (offline) where each query is a value $K$, for each query we need to count number of pairs in array with XOR $K$. If $N$ and $Q$ can both be upto $...
bihariforces's user avatar
0 votes
0 answers
36 views

Matrix Multiplication with a matrix consisting of a single shifted row

I have the following question (prefacing this with the fact that this is a question from an exam, I am currently studying but am stumped so reaching out for help). The answer to the following ...
Alon .G.'s user avatar
0 votes
0 answers
47 views

How to calculate FFT([a1, a2, . . . , an]) in time O(n), when you know FFT([a0, a1, . . . , an−1])?

I came across this problem while studying the FFT, but I have no idea how to solve it. Can anyone help?
Lothriq23's user avatar
2 votes
0 answers
55 views

Algorithm to compute sum of quotient polynomials

Let $f(X)$ be a polynomial in $\mathbb{F}_p[X]$ for some prime $p$ (of size 256 bits) that is not necessarily FFT-friendly. Let $a_1,\cdots,a_n$, $b_1,\cdots, b_n$ be $\mathbb{F}_p$ elements. What is ...
Mathdropout's user avatar
1 vote
0 answers
47 views

What algorithms apart from FFT get a computational boost by leveraging complex numbers?

If we think of the algorithmic problem of doing a convolution of two arrays, it turns out that converting them to the frequency domain first and then doing an element-wise product is equivalent. And ...
Rohit Pandey's user avatar
5 votes
3 answers
887 views

Multiplying 2 positive integers using FFT and convolutions

I was trying to figure out how I can perform multiplication of 2 big integers using FFT and convolutions, I ran into the following article: http://numbers.computation.free.fr/Constants/Algorithms/fft....
Yarin's user avatar
  • 275
1 vote
1 answer
76 views

FFT of logarithmic input data

Is there a reasonably accurate method of computing an FFT of logarithmically-represented input data (with a sign bit, that is $±2^{\text{double-precision value}}$)? The naive method (convert to linear ...
TLW's user avatar
  • 1,414
0 votes
1 answer
167 views

Why does merge sort work for any $n$, but the basic FFT algorithm only for powers of $2$?

Merge sort and FFT are both divide and conquer algorithms that split the input in two repeatedly. While merge sort can be applied to any $n$, the FFT algorithm given in CLRS (section 30.2, third ...
Rohit Pandey's user avatar
2 votes
3 answers
256 views

FFT algorithm for arbitrary $n$

In section 30.2 of CLRS (third edition), they given an algorithm for computing the fast Fourier transform of a vector represented as an $n$ dimensional array when $n$ is a power of $2$. They say that ...
Rohit Pandey's user avatar
2 votes
0 answers
79 views

Fastest algorithm for polynomial multiplication in 256-bit finite fields

I am looking for the fastest algorithm (in practice) to multiply two polynomials $f(X)\cdot h(X)$ in $\mathbb{F}_p[X]$. The prime $p$ is roughly $256$ bits but the integer $p-1$ might not have any ...
Mathdropout's user avatar
4 votes
0 answers
59 views

Polynomial multiplication in finite field without smooth-order roots of unity

I am working in a finite prime field $\mathbb{F}_p$ that does not have primitive $n$-th roots of unity for any large smooth integer $n$, which makes FFTs a bit difficult. If I need to compute a ...
Mathdropout's user avatar
1 vote
1 answer
91 views

Product of sparse polynomials with FFT

I need to compute the product of two polynomials $f(X)$ and $g(X)$ over a finite field. The degrees of these polynomials are $n^2$ for some integer $n$. However, we also know that the polynomials are ...
Mathdropout's user avatar
3 votes
1 answer
483 views

How do I take the average of multiple Fast Fourier Transforms?

How do I take the average of multiple fast Fourier transforms (ffts)? I have multiple audios that I want to take the fft of and then average these results to smooth out the random noise that appears ...
MicroscopicPie's user avatar
2 votes
0 answers
32 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 ...
openspace's user avatar
  • 151
0 votes
0 answers
237 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, ...
user2909's user avatar
0 votes
1 answer
131 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)$ $ ...
calico jack's user avatar
2 votes
1 answer
750 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 ...
joelsh's user avatar
  • 21
3 votes
1 answer
195 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 ...
RedYoel's user avatar
  • 217
0 votes
1 answer
83 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 ...
Diya Zaman's user avatar
0 votes
1 answer
278 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 ...
heretoinfinity's user avatar
1 vote
1 answer
83 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. ...
user777's user avatar
  • 729
1 vote
0 answers
113 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 ...
errorcodemonkey's user avatar
3 votes
0 answers
84 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 ...
Abhijeet Narang's user avatar
1 vote
1 answer
194 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)$.$(...
Viplaw Srivastava's user avatar
1 vote
0 answers
115 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 ...
WDUK's user avatar
  • 147
1 vote
0 answers
64 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(...
Nick Ger's user avatar
1 vote
0 answers
302 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, ...
user avatar
1 vote
0 answers
54 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], ...
vvm32812's user avatar
1 vote
0 answers
261 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 (...
vvm32812's user avatar
0 votes
0 answers
287 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. $$ ...
lan's user avatar
  • 1
2 votes
1 answer
240 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 ...
Narek Bojikian's user avatar