- eXtended Fast Fourier Transforms
This toolbox collects several function transforms, a discrete Laplace transform, see [1,5], the butterfly sparse Fourier transform [2,3] (BSFFT) and a fast Fourier transform for complex evaluation nodes [1]. A detailed Tutorial using this toolbox is included in the software package. We give a short overview about the individual transforms.
LT - Laplace transform
Let $M_1,M_2\in\mathbb{N}$, evaluation nodes $y_1>\dots>y_{M_1}>0$, frequency nodes $\xi_1>\dots>\xi_{M_2}>0$, and coefficients $\hat f_k\in\mathbb{C}$ for $k=1,\dots,M_2$ be given. The Laplace transform computes approximatively the sums $$ \mathbf{f}_j:=f(y_j)=\sum_{k=1}^{M_2} \hat f_k \mathrm{e}^{-y_j\xi_k},\quad j=1,\dots,M_1. $$ in $ \mathcal{O}((M_1+M_2) \log \frac{1}{\varepsilon}+\log^3 \frac{1}{\varepsilon}\log\frac{y_1\xi_1}{\varepsilon})$ floating point operations where $ \varepsilon >0$ denotes the target accuracy.
BSFFT - Butterfly Sparse Fast Fourier Transform
For a given space dimension $d \in \mathbb{N} $, a nonharmonic bandwith $N=2^L, \ L \in \mathbb{N}, $ a set of frequencies $ \tilde T = \{ \boldsymbol{\xi}_k \in [0,N]^d: k=1,\dots,M_2\} $, a set of Fourier coefficients $\hat f_k \in \mathbb{C}, k=1,\dots,M_2,$ and a set of evaluation nodes $\tilde X= \{ \mathbf{x}_j\in [0,N]^d: k=1,\dots,M_1\},$ the butterfly sparse Fourier transform computes the sums $$\mathbf{f}_j:=f(\mathbf{x}_j)=\sum_{k=1}^{M_2}\hat f_k \mathrm{e}^{2\pi \mathrm{i} \boldsymbol{\xi}_k \mathbf{x}_j/N}, \quad j=1,\dots,M_1.$$ This sum with $d\geq 2$ and $ M_1=M_2=\mathcal{O}(N^{d-1}), $ and sets $\tilde T$, $\tilde X$ on smooth $(d-1)$-dimensional manifolds can be computed in $\mathcal{O}(N^{d-1}\log N(|\log \varepsilon|+\log N)^{d+1}$ floating point operations, where $\varepsilon >0$ denotes the target accuracy. About the butterfly algorithm, see [2,4].
XFLT - Fast Fourier transform for complex evaluation nodes
We compute fast Fourier transforms for complex evaluation nodes by a combination of the previous Laplace transform and a Fourier transform. To be more precisely, we compute the sums $$\mathbf{f}_j:=f(\mathbf{x}_j)=\sum_{k=1}^{M_2}\hat f_k \mathrm{e}^{-\xi_k y_j}\mathrm{e}^{2\pi \mathrm{i} \xi_k x_j/N}, \quad j=1,\dots,M_1,$$ where the evaluation nodes $y_1>\dots>y_{M_1}>0$, and $x_j \in \tilde X$ are given. Moreover, the frequency nodes $N \geq \xi_1>\dots>\xi_{M_2}>0$ are given. The sums can be computed in $$ \mathcal{O}\left(N\log N \log^2\frac{N}{\varepsilon} \log\frac{N y_1}{\varepsilon} \log \frac{1}{\varepsilon}\right)$$ floating point operations in the butterfly case for $ M_1,M_2 \in \mathcal{O}(N)$. Note, that for the part of the Fourier transform, one can use the FFT for equispaced evaluation and frequency nodes, a NFFT for equispaced frequencies and nonequispaced evaluation nodes, a NNFFT or BSFFT for nonequispaced evaluation and frequency nodes. All cases are implemented. See the tutorial for detailed description. For using the NFFT or NNFFT variant, the software library NFFT, see [3], should be installed
Download the BSFFT1D in C++
I have implemented the BSFFT for dimension $d=1$ in C++ to get experience in coding C++. My library uses the armadillo library which is published here. My library is not well documented at the moment. But nevertheless, if you have a look at the main.cpp it should be clear how you can use or apply my algorithms. Note, that my source code is published under the GNU General Public License version 3.
- BSFFT1D version 0.9.tar.gz is available, 20 May 2016.
Download the full XFFT-toolbox in MATLAB
The toolbox is published under the GNU General Public License version 3.
- Current release: XFFT version 1.0.tar.gz is available, 01 June 2015.
New: A tutorial (readme.pdf) is now included and the start scripts are corrected, 21 October 2015.
Archive
- BSFFT version 0.9.tar.gz is available, 03 September 2012
References
Stefan Kunis and Ines Melzer.
A stable and accurate butterfly sparse Fourier transform. SIAM J. Numer. Anal. 50(3):1777–1800, 2012.
URL BibTeX@article{KuMe12, author = "Kunis, Stefan and Melzer, Ines", title = "A stable and accurate butterfly sparse {F}ourier transform", journal = "{SIAM J. Numer. Anal.}", volume = 50, year = 2012, number = 3, pages = "1777--1800", issn = "0036-1429", coden = "SJNAAM", mrclass = "65T50 (42A15)", mrnumber = 2970765, mrreviewer = "Manfred Tasche", url = "/data/publications/paper/KuMe12.pdf" }Stefan Kunis and Ines Melzer.
Fast evaluation of real and complex exponential sums. Electron. Trans. Numer. Anal. 46:23-35, 2017.
URL BibTeX@article{KuMe17, author = "Stefan Kunis and Ines Melzer", title = "Fast evaluation of real and complex exponential sums", journal = "{Electron. Trans. Numer. Anal.}", volume = 46, year = 2017, url = "/data/publications/paper/KuMe16.pdf", pages = "23-35" }Lexing Ying.
Sparse Fourier transform via butterfly algorithm. SIAM J. Sci. Comput. 31(3):1678–1694, 2009.
URL, DOI BibTeX@article{Yi09, author = "Ying, Lexing", title = "Sparse {F}ourier transform via butterfly algorithm", journal = "{SIAM J. Sci. Comput.}", volume = 31, year = 2009, number = 3, pages = "1678--1694", issn = "1064-8275", mrclass = "65T50 (65R10 65Y20)", mrnumber = "2491541 (2009m:65273)", mrreviewer = "Daniel Potts", doi = "10.1137/08071291X", url = "http://dx.doi.org/10.1137/08071291X" }V Rokhlin.
A fast algorithm for the discrete Laplace transformation. J. Complexity 4(1):12–32, 1988.
URL, DOI BibTeX@article{Ro88, author = "Rokhlin, V.", title = "A fast algorithm for the discrete {L}aplace transformation", journal = "{J. Complexity}", volume = 4, year = 1988, number = 1, pages = "12--32", issn = "0885-064X", mrclass = "65R10", mrnumber = "939693 (89b:65309)", doi = "10.1016/0885-064X(88)90007-6", url = "http://dx.doi.org/10.1016/0885-064X(88)90007-6" }Jens Keiner, Stefan Kunis and Daniel Potts.
Using NFFT 3–-a software library for various nonequispaced fast Fourier transforms. ACM Trans. Math. Software 36(4):Art. 19, 30, 2009.
URL, DOI BibTeX@article{KeKuPo09, author = "Keiner, Jens and Kunis, Stefan and Potts, Daniel", title = "Using {NFFT} 3---a software library for various nonequispaced fast {F}ourier transforms", journal = "{ACM Trans. Math. Software}", volume = 36, year = 2009, number = 4, pages = "Art. 19, 30", issn = "0098-3500", coden = "ACMSCU", mrclass = "65T50 (65Y15)", mrnumber = 2738200, doi = "10.1145/1555386.1555388", url = "http://dx.doi.org/10.1145/1555386.1555388" }