Direct and fast computation of the nonequispaced discrete Fourier transform. More...

Data Structures
struct	nfft_plan

Macros
#define	PRE_PHI_HUT (1U<<0)
#define	FG_PSI (1U<<1)
#define	PRE_LIN_PSI (1U<<2)
#define	PRE_FG_PSI (1U<<3)
#define	PRE_PSI (1U<<4)
#define	PRE_FULL_PSI (1U<<5)
#define	MALLOC_X (1U<<6)
#define	MALLOC_F_HAT (1U<<7)
#define	MALLOC_F (1U<<8)
#define	FFT_OUT_OF_PLACE (1U<<9)
#define	FFTW_INIT (1U<<10)
#define	PRE_ONE_PSI (PRE_LIN_PSI\| PRE_FG_PSI\| PRE_PSI\| PRE_FULL_PSI)

Functions
void	nfft_trafo (nfft_plan *ths)
void	nfft_adjoint (nfft_plan *ths)
void	nfft_init_1d (nfft_plan *ths, int N1, int M)
void	nfft_init_2d (nfft_plan *ths, int N1, int N2, int M)
void	nfft_init_3d (nfft_plan *ths, int N1, int N2, int N3, int M)
void	nfft_init (nfft_plan ths, int d, int N, int M)
void	nfft_precompute_one_psi (nfft_plan *ths)
void	nfft_precompute_full_psi (nfft_plan *ths)
void	nfft_precompute_psi (nfft_plan *ths)
void	nfft_precompute_lin_psi (nfft_plan *ths)
const char *	nfft_check (nfft_plan *ths)
void	nfft_finalize (nfft_plan *ths)

Detailed Description

Direct and fast computation of the nonequispaced discrete Fourier transform.

This module implements the nonequispaced fast Fourier transforms. In the following, we abbreviate the term "nonequispaced fast Fourier transform" by NFFT.

We introduce our notation and nomenclature for discrete Fourier transforms. Let the torus

$\‍[ \mathbb{T}^d := \left\{ \mathbf{x}=\left(x_t\right)_{t=0,\dots,d-1}\in\mathbb{R}^{d}: \; - \frac{1}{2} \le x_t < \frac{1}{2},\; t=0,\dots,d-1 \right\} \‍]$

of dimension $d$ be given. It will serve as domain from which the nonequispaced nodes $\mathbf{x}$ are taken. The sampling set is given by ${\cal X}:=\{\mathbf{x}_j \in {\mathbb T}^d: \,j=0,\dots,M-1\}$ . Possible frequencies $\mathbf{k}$ are collected in the multi index set

$\‍[ I_{\mathbf{N}} := \left\{ \mathbf{k}=\left(k_t\right)_{t=0,\dots,d-1}\in \mathbb{Z}^d: - \frac{N_t}{2} \le k_t < \frac{N_t}{2} ,\;t=0,\dots,d-1 \right\}. \‍]$

Our concern is the computation of the nonequispaced discrete Fourier transform (NDFT)

$\‍[f_j = \sum_{\mathbf{k}\in I_{\mathbf{N}}} \hat{f}_{\mathbf{k}} {\rm e}^{-2\pi{\rm i} \mathbf{k}\mathbf{x}_j}, \qquad j=0,\dots,M-1. \‍]$

The corresponding adjoint NDFT is the computation of

$\‍[ \hat f_{\mathbf{k}}=\sum_{j=0}^{M-1} f_j {\rm e}^{+2\pi{\rm i} \mathbf{k}\mathbf{x}_j}, \qquad \mathbf{k}\in I_{\mathbf{N}}. \‍]$

Direct implementations are given by nfft_direct_trafo and nfft_direct_adjoint taking ${\cal O}(|I_{\mathbf{N}}|M)$ floating point operations. Approximative realisations take only ${\cal O}(|I_{\mathbf{N}}|\log|I_{\mathbf{N}}|+M)$ floating point operations. These are provided by nfft_trafo and nfft_adjoint, respectively.

Macro Definition Documentation

◆ PRE_PHI_HUT

#define PRE_PHI_HUT (1U<<0)

If this flag is set, the deconvolution step (the multiplication with the diagonal matrix $\mathbf{D}$ ) uses precomputed values of the Fourier transformed window function.

See also: nfft_init; nfft_init_advanced; nfft_init_guru

Author: Stefan Kunis

Definition at line 181 of file nfft3.h.

Referenced by construct(), construct(), fastsum_init_guru_source_nodes(), fastsum_init_guru_target_nodes(), main(), nfsft_init_advanced(), nfsoft_init_advanced(), nnfft_finalize(), nnfft_init(), nnfft_init_guru(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and taylor_time_accuracy().

◆ FG_PSI

#define FG_PSI (1U<<1)

If this flag is set, the convolution step (the multiplication with the sparse matrix $\mathbf{B}$ ) uses particular properties of the Gaussian window function to trade multiplications for direct calls to exponential function.

See also: nfft_init; nfft_init_advanced; nfft_init_guru

Author: Stefan Kunis

Definition at line 182 of file nfft3.h.

Referenced by nfsoft_precompute().

◆ PRE_LIN_PSI

#define PRE_LIN_PSI (1U<<2)

If this flag is set, the convolution step (the multiplication with the sparse matrix $\mathbf{B}$ ) uses linear interpolation from a lookup table of equispaced samples of the window function instead of exact values of the window function. At the moment a table of size $(K+1)d$ is used, where $K=2^{10}(m+1)$ . An estimate for the size of the lookup table with respect to the target accuracy should be implemented.

See also: nfft_init; nfft_init_advanced; nfft_init_guru

Author: Stefan Kunis

Definition at line 183 of file nfft3.h.

Referenced by fastsum_precompute_source_nodes(), fastsum_precompute_target_nodes(), nfsoft_init_guru_advanced(), nnfft_finalize(), nnfft_init_guru(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and reconstruct().

◆ PRE_FG_PSI

#define PRE_FG_PSI (1U<<3)

If this flag is set, the convolution step (the multiplication with the sparse matrix $\mathbf{B}$ ) uses particular properties of the Gaussian window function to trade multiplications for direct calls to exponential function (the remaining $2dM$ direct calls are precomputed).

See also: nfft_init; nfft_init_advanced; nfft_init_guru

Author: Stefan Kunis

Definition at line 184 of file nfft3.h.

Referenced by taylor_time_accuracy().

◆ PRE_PSI

#define PRE_PSI (1U<<4)

If this flag is set, the convolution step (the multiplication with the sparse matrix $\mathbf{B}$ ) uses $(2m+2)dM$ precomputed values of the window function.

See also: nfft_init; nfft_init_advanced; nfft_init_guru

Author: Stefan Kunis

Definition at line 185 of file nfft3.h.

Referenced by construct(), construct(), construct(), construct(), fastsum_init_guru_source_nodes(), fastsum_init_guru_target_nodes(), fastsum_precompute_source_nodes(), fastsum_precompute_target_nodes(), main(), nfsft_init_advanced(), nfsoft_init_advanced(), nfsoft_precompute(), nnfft_finalize(), nnfft_init(), nnfft_init_guru(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and reconstruct().

◆ PRE_FULL_PSI

#define PRE_FULL_PSI (1U<<5)

If this flag is set, the convolution step (the multiplication with the sparse matrix $\mathbf{B}$ ) uses $(2m+2)^dM$ precomputed values of the window function, in addition indices of source and target vectors are stored.

See also: nfft_init; nfft_init_advanced; nfft_init_guru

Author: Stefan Kunis

Definition at line 186 of file nfft3.h.

Referenced by fastsum_precompute_source_nodes(), fastsum_precompute_target_nodes(), nnfft_finalize(), nnfft_init_guru(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and reconstruct().

◆ MALLOC_X

#define MALLOC_X (1U<<6)

If this flag is set, (de)allocation of the node vector is done.

See also: nfft_init; nfft_init_advanced; nfft_init_guru; nfft_finalize

Author: Stefan Kunis

Definition at line 187 of file nfft3.h.

Referenced by construct(), construct(), nfsoft_init_advanced(), nnfft_finalize(), nnfft_init(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and taylor_init().

◆ MALLOC_F_HAT

#define MALLOC_F_HAT (1U<<7)

If this flag is set, (de)allocation of the vector of Fourier coefficients is done.

See also: nfft_init; nfft_init_advanced; nfft_init_guru; nfft_finalize

Author: Stefan Kunis

Definition at line 188 of file nfft3.h.

Referenced by construct(), construct(), nfsoft_init_advanced(), nnfft_finalize(), nnfft_init(), nnfft_init_guru(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and taylor_init().

◆ MALLOC_F

#define MALLOC_F (1U<<8)

If this flag is set, (de)allocation of the vector of samples is done.

See also: nfft_init; nfft_init_advanced; nfft_init_guru; nfft_finalize

Author: Stefan Kunis

Definition at line 189 of file nfft3.h.

Referenced by construct(), construct(), nfsoft_init_advanced(), nnfft_finalize(), nnfft_init(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and taylor_init().

◆ FFT_OUT_OF_PLACE

#define FFT_OUT_OF_PLACE (1U<<9)

If this flag is set, FFTW uses disjoint input/output vectors.

See also: nfft_init; nfft_init_advanced; nfft_init_guru; nfft_finalize

Author: Stefan Kunis

Definition at line 190 of file nfft3.h.

Referenced by fastsum_init_guru_source_nodes(), fastsum_init_guru_target_nodes(), main(), nnfft_init(), nnfft_init_guru(), taylor_init(), and taylor_time_accuracy().

◆ FFTW_INIT

#define FFTW_INIT (1U<<10)

If this flag is set, fftw_init/fftw_finalize is called.

See also: nfft_init; nfft_init_advanced; nfft_init_guru; nfft_finalize

Author: Stefan Kunis

Definition at line 191 of file nfft3.h.

Referenced by construct(), construct(), fastsum_init_guru_source_nodes(), fastsum_init_guru_target_nodes(), main(), nfsft_init_advanced(), nfsoft_init_advanced(), nnfft_init(), nnfft_init_guru(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), taylor_init(), and taylor_time_accuracy().

◆ PRE_ONE_PSI

#define PRE_ONE_PSI (PRE_LIN_PSI| PRE_FG_PSI| PRE_PSI| PRE_FULL_PSI)

Summarises if precomputation is used within the convolution step (the multiplication with the sparse matrix $\mathbf{B}$ ). If testing against this flag is positive, nfft_precompute_one_psi has to be called.

See also: nfft_init; nfft_init_advanced; nfft_init_guru; nfft_precompute_one_psi; nfft_finalize

Author: Stefan Kunis

Definition at line 194 of file nfft3.h.

Referenced by taylor_time_accuracy().

Function Documentation

◆ nfft_trafo()

void nfft_trafo ( nfft_plan * ths )

extern

Computes a NFFT, see the definition.

ths The pointer to a nfft plan

Author: Stefan Kunis, Daniel Potts

Referenced by construct(), construct(), mri_inh_2d1d_trafo(), mri_inh_3d_trafo(), nfsoft_trafo(), and nnfft_trafo().

◆ nfft_adjoint()

void nfft_adjoint ( nfft_plan * ths )

extern

Computes an adjoint NFFT, see the definition.

ths The pointer to a nfft plan

Author: Stefan Kunis, Daniel Potts

Referenced by mri_inh_3d_adjoint(), nfsoft_adjoint(), nnfft_adjoint(), reconstruct(), and reconstruct().

◆ nfft_init_1d()

void nfft_init_1d	(	nfft_plan *	ths,
		int	N1,
		int	M )

extern

Initialisation of a transform plan, wrapper d=1.

ths The pointer to a nfft plan
N1 bandwidth
M The number of nodes

Author: Stefan Kunis, Daniel Potts

◆ nfft_init_2d()

void nfft_init_2d	(	nfft_plan *	ths,
		int	N1,
		int	N2,
		int	M )

extern

Initialisation of a transform plan, wrapper d=2.

ths The pointer to a nfft plan
N1 bandwidth
N2 bandwidth
M The number of nodes

Author: Stefan Kunis, Daniel Potts

Referenced by construct(), and construct().

◆ nfft_init_3d()

void nfft_init_3d	(	nfft_plan *	ths,
		int	N1,
		int	N2,
		int	N3,
		int	M )

extern

Initialisation of a transform plan, wrapper d=3.

ths The pointer to a nfft plan
N1 bandwidth
N2 bandwidth
N3 bandwidth
M The number of nodes

Author: Stefan Kunis, Daniel Potts

◆ nfft_init()

void nfft_init	(	nfft_plan *	ths,
		int	d,
		int *	N,
		int	M )

extern

Initialisation of a transform plan, simple.

ths The pointer to a nfft plan
d The dimension
N The multi bandwidth
M The number of nodes

Author: Stefan Kunis, Daniel Potts

◆ nfft_precompute_one_psi()

void nfft_precompute_one_psi ( nfft_plan * ths )

extern

Precomputation for a transform plan.

ths The pointer to a nfft plan

Author: Stefan Kunis

wrapper for precompute*_psi

if PRE_*_PSI is set the application program has to call this routine (after) setting the nodes x

Referenced by nfsoft_precompute().

◆ nfft_precompute_full_psi()

void nfft_precompute_full_psi ( nfft_plan * ths )

extern

Superceded by nfft_precompute_one_psi.

Author: Stefan Kunis

Referenced by nnfft_precompute_full_psi(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and reconstruct().

◆ nfft_precompute_psi()

void nfft_precompute_psi ( nfft_plan * ths )

extern

Superceded by nfft_precompute_one_psi.

Author: Stefan Kunis

Referenced by construct(), construct(), construct(), construct(), nnfft_precompute_psi(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and reconstruct().

◆ nfft_precompute_lin_psi()

void nfft_precompute_lin_psi ( nfft_plan * ths )

extern

Superceded by nfft_precompute_one_psi.

Author: Stefan Kunis

Referenced by nfsoft_init_guru_advanced(), nnfft_precompute_lin_psi(), reconstruct(), reconstruct(), reconstruct(), and reconstruct().

◆ nfft_check()

const char * nfft_check ( nfft_plan * ths )

extern

Checks a transform plan for frequently used bad parameter.

ths The pointer to a nfft plan

Author: Stefan Kunis, Daniel Potts

◆ nfft_finalize()

void nfft_finalize ( nfft_plan * ths )

extern

Destroys a transform plan.

ths The pointer to a nfft plan

Author: Stefan Kunis, Daniel Potts

Referenced by construct(), construct(), mri_inh_2d1d_finalize(), mri_inh_3d_finalize(), nfsft_finalize(), nfsoft_finalize(), nnfft_finalize(), reconstruct(), reconstruct(), reconstruct(), reconstruct(), and reconstruct().

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ PRE_PHI_HUT

◆ FG_PSI

◆ PRE_LIN_PSI

◆ PRE_FG_PSI

◆ PRE_PSI

◆ PRE_FULL_PSI

◆ MALLOC_X

◆ MALLOC_F_HAT

◆ MALLOC_F

◆ FFT_OUT_OF_PLACE

◆ FFTW_INIT

◆ PRE_ONE_PSI

Function Documentation

◆ nfft_trafo()

◆ nfft_adjoint()

◆ nfft_init_1d()

◆ nfft_init_2d()

◆ nfft_init_3d()

◆ nfft_init()

◆ nfft_precompute_one_psi()

◆ nfft_precompute_full_psi()

◆ nfft_precompute_psi()

◆ nfft_precompute_lin_psi()

◆ nfft_check()

◆ nfft_finalize()