<p>Take a look at <a href="http://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication" rel="nofollow">Toom-Cook multiplication</a> and see if that is helpful for what you need. The complexity is $O(n^{1+\epsilon})$ for any fixed $\epsilon&gt;0$.</p>

CC BY-SA 3.0
2013-07-05T01:00:46.323Z
2013-07-05T01:00:46.323Z
Simd
<p>What is the best upper and lower bound known for <a href="https://en.wikipedia.org/wiki/Convolution" rel="nofollow">convolution</a> without <a href="https://en.wikipedia.org/wiki/Fast_Fourier_transform" rel="nofollow">FFT</a>? </p>

<p>Is FFT proven to be essential for time complexity reduction? 
Is cancellation essential as well?</p>

CC BY-SA 3.0
2013-07-04T21:19:54.843Z
It might be a good idea to clarify what you mean by FFT being essential for convolution.
Kaveh
<cc.complexity-theory><algebraic-complexity><fft><convolution>
Convolution without FFT
Turbo
# Convolution without FFT

(Asked by: username_0 on 2013-07-04)

What is the best upper and lower bound known for [convolution](https://en.wikipedia.org/wiki/Convolution) without [FFT](https://en.wikipedia.org/wiki/Fast_Fourier_transform)?

Is FFT proven to be essential for time complexity reduction?
Is cancellation essential as well?

**Tags:** cc.complexity-theory, algebraic-complexity, fft, convolution

> **Comments:**
> **username_1**: It might be a good idea to clarify what you mean by FFT being essential for convolution.  

---

## 1 answers

### Answer by username_2 on 2013-07-05. Score: 2 | Accepted answer

Take a look at [Toom-Cook multiplication](http://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication) and see if that is helpful for what you need. The complexity is $O(n^{1+\epsilon})$ for any fixed $\epsilon>0$.


---

