<p>While this is not a direct answer, the <a href="https://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures">following discussion on MO</a> (Mathoverflow) relates to finding convolution operations that admit fast FFT-like operations on other algebraic structures. </p>

CC BY-SA 2.5
2010-08-16T20:47:42.030Z
2010-08-16T20:47:42.030Z
2017-04-13T12:57:54.777Z
Suresh Venkat
<p>Can the divide and conquer nature of the FFT be generalized to other transforms (z Transform, chirp, etc) automatically?</p>

<p>Is there an algorithm that takes in a description of transform (I don't know what information would be needed) and can produce a fast FFT like function?</p>

<ds.algorithms>
Generalizing the FFT
Jonathan Fischoff
# Generalizing the FFT

(Asked by: username_0 on 2010-08-16)

Can the divide and conquer nature of the FFT be generalized to other transforms (z Transform, chirp, etc) automatically?

Is there an algorithm that takes in a description of transform (I don't know what information would be needed) and can produce a fast FFT like function?

**Tags:** ds.algorithms

---

## 1 answers

### Answer by username_1 on 2010-08-16. Score: 6 | Accepted answer

While this is not a direct answer, the [following discussion on MO](https://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures) (Mathoverflow) relates to finding convolution operations that admit fast FFT-like operations on other algebraic structures.


---

