Editing Fast Fourier transform (section)

==Research areas==
; Big FFTs: With the explosion of big data in fields such as astronomy, the need for 512K&nbsp;FFTs has arisen for certain interferometry calculations. The data collected by projects such as [[WMAP]] and [[LIGO]] require FFTs of tens of billions of points. As this size does not fit into main memory, so called out-of-core FFTs are an active area of research.<ref name="Cormen_Nicol_1998"/>
; Approximate FFTs: For applications such as MRI, it is necessary to compute DFTs for nonuniformly spaced grid points and/or frequencies. Multipole based approaches can compute approximate quantities with factor of runtime increase.<ref name="Dutt_Rokhlin_1993"/>
; [[Fourier transform on finite groups|Group FFTs]]: The FFT may also be explained and interpreted using [[group representation theory]] allowing for further generalization. A function on any compact group, including non-cyclic, has an expansion in terms of a basis of irreducible matrix elements. It remains active area of research to find efficient algorithm for performing this change of basis. Applications including efficient [[spherical harmonic]] expansion, analyzing certain [[Markov process]]es, robotics etc.<ref name="Rockmore_2004"/>
; [[Quantum Fourier transform|Quantum FFTs]]: Shor's fast algorithm for [[integer factorization]] on a quantum computer has a subroutine to compute DFT of a binary vector. This is implemented as sequence of 1- or 2-bit quantum gates now known as quantum FFT, which is effectively the Cooley–Tukey FFT realized as a particular factorization of the Fourier matrix. Extension to these ideas is currently being explored.<ref>{{Cite journal |title=Quantum circuit for the fast Fourier transform |journal=Quantum Information Processing |volume=19 |issue=277 |year=2020 |first1=Asaka |last1=Ryo |first2=Sakai |last2=Kazumitsu |first3=Yahagi |last3=Ryoko |page=277 |doi=10.1007/s11128-020-02776-5 |arxiv=1911.03055 |bibcode=2020QuIP...19..277A |s2cid=207847474 |url=https://link.springer.com/article/10.1007/s11128-020-02776-5}}</ref>