Questions tagged [fft]
The fft tag has no usage guidance.
9 questions
2
votes
0
answers
89
views
Multipoint evaluation in Lagrange basis
Setup. Let $\mathbb{F}$ be a finite field with a multiplicative subgroup $E = \{e_1, \dots, e_k\}$ of order $k$. Given a list $y = y_1, \dots, y_k\in \mathbb{F}$ let $p$ be the unique polynomial of ...
1
vote
0
answers
72
views
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
7
votes
1
answer
227
views
Subquadratic 3SUM when one set is in [n^1.99]
Chan and Lewenstein (STOC 2015) said:
3SUM for three integer sets where only one set is assumed to be in $[n^{2−\delta}]$ can still be solved
in subquadratic time (by doing several FFTs, without ...
1
vote
0
answers
35
views
Are there uses for a Fourier transform of length $n^m$ with elements of maximum size $n$?
In essence, I'm trying to get a better feel for when there is a use for FFT with small coefficients, compared to the length, assuming that we get a better runtime.
I've been toying with an idea for a ...
- 2,110
2
votes
0
answers
134
views
What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?
There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
- 2,110
2
votes
0
answers
96
views
Is gaussian smoothing possible in less operations than O(N log N)
Gaussian filtering is popular in applications, for my question it can be written as (I've fixed the size of window):
$$y_i = \sum_{j = 1}^{n} x_j e^{(i - j)^2}, \qquad i = 1, 2, ..., n $$
One can ...
- 121
17
votes
3
answers
2k
views
Finding witness in minkowski sum of integers
Let $A$ and $B$ be subsets of $\{0,\ldots,n\}$. We are interested in finding the Minkowski sum $A+B=\{a+b~|~a\in A,b\in B\}$.
$\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ is a characteristic function of $X$ ...
- 4,529
12
votes
1
answer
2k
views
Complexity of convolution in the max/plus ring
We can do convolution in $O(n\log n)$ for plus/multiply polynomials with FFT. However, the approach doesn't seem very generalisable to rings in general.
Has there been any progress over the naive $O(...
- 958
3
votes
1
answer
261
views
Convolution without FFT
What is the best upper and lower bound known for convolution without FFT?
Is FFT proven to be essential for time complexity reduction?
Is cancellation essential as well?
- 13.3k