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$ .