next up previous contents
Next: Accuracy vs. window function Up: Examples Previous: Computing your first transform   Contents

Computation time vs. problem size

The program nfft_times in the same directory compares the computation time of the FFT ([28], FFTW_MEASURE), the straightforward evaluation of (2.2), denoted by NDFT, and the NFFT for increasing total problem sizes $ \vert I_{\ensuremath{\boldsymbol{N}}}\vert$ and space dimensions $ d=1,2,3$ , where $ \ensuremath{\boldsymbol{N}}=(N,\hdots,N)^{\top},\;N\in\ensuremath{\mathbb{N}}$ . While the nodes for the FFT are restricted to the lattice $ \ensuremath{\boldsymbol{N}}^{-1}\odot
I_{\ensuremath{\boldsymbol{N}}}$ , we choose $ M=N^d$ random nodes for the NDFT and the NFFT. Within the latter, we use the oversampling factor $ \sigma=2$ , the cut-off $ m=4$ , and the Kaiser-Bessel window function (PRE_PSI, PRE_PHI_HUT). This results in a fixed accuracy of $ E_{\infty}:=\Vert\ensuremath{\boldsymbol{f}}-\ensuremath{\boldsymbol{s}}\Vert _{\infty}/\Vert\ensuremath{\boldsymbol{\hat f}}\Vert _1\approx 10^{-8}$ for $ d=1,2,3$ .


Table: Computation time in seconds with respect to $ l_N=\log_2\vert I_{\ensuremath{\boldsymbol{N}}}\vert$ . Note that we used accumulated measurements in case of small times and the times (*) are not displayed due to the large response time in comparison to the FFT time.
$ l_N$ FFT NDFT NFFT $ l_N$ FFT NDFT NFFT
$ d=1$ $ d=2$
$ 3$ $ 1.3e-07$ $ 8.7e-06$ $ 4.6e-06$ $ 6$ $ 9.9e-07$ $ 5.7e-04$ $ 3.2e-04$
$ 4$ $ 2.0e-07$ $ 3.5e-05$ $ 8.7e-06$ $ 8$ $ 4.4e-06$ $ 9.2e-03$ $ 1.3e-03$
$ 5$ $ 4.0e-07$ $ 1.4e-04$ $ 1.7e-05$ $ 10$ $ 2.1e-05$ $ 1.5e-01$ $ 5.2e-03$
$ 6$ $ 8.9e-07$ $ 5.6e-04$ $ 3.6e-05$ $ 12$ $ 1.2e-04$ $ 2.4e+00$ $ 2.3e-02$
$ 7$ $ 2.2e-06$ $ 2.2e-03$ $ 7.2e-05$ $ 14$ $ 1.7e-03$ $ 3.8e+01$ $ 1.5e-01$
$ 8$ $ 4.8e-06$ $ 9.0e-03$ $ 1.4e-04$ $ 16$ $ 2.1e-02$ * $ 6.8e-01$
$ 9$ $ 1.1e-05$ $ 3.6e-02$ $ 2.9e-04$ $ 18$ $ 8.4e-02$ * $ 2.8e+00$
$ 10$ $ 2.4e-05$ $ 1.4e-01$ $ 6.0e-04$ $ 20$ $ 3.2e-01$ * $ 1.2e+01$
$ 11$ $ 5.7e-05$ $ 5.8e-01$ $ 1.4e-03$ $ 22$ $ 1.4e+00$ * $ 5.3e+01$
$ 12$ $ 1.5e-04$ $ 2.3e+00$ $ 3.2e-03$ $ d=3$
$ 13$ $ 5.5e-04$ $ 9.4e+00$ $ 8.2e-03$ $ 9$ $ 1.0e-05$ $ 3.7e-02$ $ 2.5e-02$
$ 14$ $ 1.7e-03$ $ 3.8e+01$ $ 2.0e-02$ $ 12$ $ 1.1e-04$ $ 2.4e+00$ $ 2.5e-01$
$ 15$ $ 3.8e-03$ $ 1.5e+02$ $ 4.9e-02$ $ 15$ $ 3.4e-03$ $ 1.5e+02$ $ 2.4e+00$
$ 16$ $ 8.2e-03$ * $ 1.2e-01$ $ 18$ $ 5.2e-02$ * $ 2.1e+01$
$ 17$ $ 1.9e-02$ * $ 2.4e-01$ $ 21$ $ 9.0e-01$ * $ 1.8e+02$
$ 18$ $ 4.5e-02$ * $ 3.6e-01$        
$ 19$ $ 9.2e-02$ * $ 9.8e-01$        
$ 20$ $ 1.9e-01$ * $ 2.1e+00$        
$ 21$ $ 4.2e-01$ * $ 4.2e+00$        
$ 22$ $ 1.0e-00$ * $ 9.5e+00$        
             


We conclude the following: The FFT and the NFFT show the expected $ {\cal O}(\vert I_{\ensuremath{\boldsymbol{N}}}\vert \log \vert I_{\ensuremath{\boldsymbol{N}}}\vert)$ time complexity, i.e., doubling the total size $ \vert I_{\ensuremath{\boldsymbol{N}}}\vert$ results in only slightly more than twice the computation time, whereas the NDFT behaves as $ {\cal O}(\vert I_{\ensuremath{\boldsymbol{N}}}\vert^2)$ . Note furthermore, that the constant in the $ {\cal O}$ -notation is independent of the space dimension $ d$ for the FFT and the NDFT, whereas the computation time of the NFFT increases considerably for larger $ d$ .


next up previous contents
Next: Accuracy vs. window function Up: Examples Previous: Computing your first transform   Contents
Jens Keiner 2006-11-20