Edit on GitHub

Nonequispaced Fast Sine Transform (NFST)

NDST and NFST

We consider the odd, 1-periodic trigonometric polynomial

\[ f^s(\pmb{x}) \coloneqq \sum_{\pmb{k} \in I_{\pmb{N},\mathrm{s}}^d} \hat{f}_{\pmb{k}}^s \, \sin(2\pi \, \pmb{k} \odot \pmb{x}), \quad \pmb{x} \in \mathbb{R}^d,\]

with multibandlimit $\pmb{N} \in \mathbb{N}^d$ and index set

\[ I_{\pmb{N},\mathrm{s}}^d \coloneqq \left\{ \pmb{k} \in \mathbb{Z}^d: 1 \leq k_i \leq N_i - 1, \, i = 1,2,\ldots,d \right\}.\]

Note that we define $\sin(\pmb{k} \circ \pmb{x}) \coloneqq \prod_{i=1}^d \sin(k_i \cdot x_i)$. The NDST is the evaluation of

\[ f^s(\pmb{x}_j) = \sum_{\pmb{k} \in I_{\pmb{N},\mathrm{s}}^d} \hat{f}_{\pmb{k}}^s \, \sin(2\pi \, \pmb{k} \odot \pmb{x}_j)\]

at arbitrary nodes $\pmb{x}_j \in [0,0.5]^d$ for given coefficients $\hat{f}_{\pmb{k}}^s \in \mathbb{R}, \pmb{k} \in I_{\pmb{N},\mathrm{s}}^d$. Similarly to the NDFT, the transposed NDST is the evaluation of

\[ \hat{h}^s_{\pmb{k}} = \sum_{j=1}^M f^s_j \, \sin(2\pi \, \pmb{k} \odot \pmb{x}_j)\]

for the frequencies $\pmb{k} \in I_{\pmb{N},\mathrm{s}}^d$ with given coefficients $f^s_j \in \mathbb{R}, j = 1,2,\ldots,M$.

We modify the NFFT in order to derive a fast algorithm for the computation of the NDST and transposed NDST, obtaining the NFST and its transposed counterpart. For details we refer to Chapter 6 in [Plonka, Potts, Steidl, Tasche, 2018].

Plan structure

NFFT3.NFST — Type
NFST{D}

A NFST (nonequispaced fast sine transform) plan, where D is the dimension.

The NFST realizes a direct and fast computation of the discrete nonequispaced sine transform. The aim is to compute

\[f^s(\pmb{x}_j) = \sum_{\pmb{k} \in I_{\pmb{N},\mathrm{s}}^D} \hat{f}_{\pmb{k}}^s \, \sin(2\pi \, \pmb{k} \odot \pmb{x}_j)\]

at given arbitrary knots $\pmb{x}_j \in [0,0.5]^D, j = 1, \cdots, M$, for coefficients $\hat{f}^{s}_{\pmb{k}} \in \mathbb{R}$, $\pmb{k} \in I_{\pmb{N},\mathrm{s}}^D \coloneqq \left\{ \pmb{k} \in \mathbb{Z}^D: 1 \leq k_i \leq N_i - 1, \, i = 1,2,\ldots,D \right\}$, and a multibandlimit vector $\pmb{N} \in \mathbb{N}^{D}$. Note that we define $\sin(\pmb{k} \circ \pmb{x}) \coloneqq \prod_{i=1}^D \sin(k_i \cdot x_i)$. The transposed problem reads as

\[\hat{h}^s_{\pmb{k}} = \sum_{j=1}^M f^s_j \, \sin(2\pi \, \pmb{k} \odot \pmb{x}_j)\]

for the frequencies $\pmb{k} \in I_{\pmb{N},\mathrm{s}}^D$ with given coefficients $f^s_j \in \mathbb{R}, j = 1,2,\ldots,M$.

Fields

  • N - the multibandlimit $(N_1, N_2, \ldots, N_D)$ of the trigonometric polynomial $f^s$.
  • M - the number of nodes.
  • n - the oversampling $(n_1, n_2, \ldots, n_D)$ per dimension.
  • m - the window size. A larger m results in more accuracy but also a higher computational cost.
  • f1 - the NFST flags.
  • f2 - the FFTW flags.
  • init_done - indicates if the plan is initialized.
  • finalized - indicates if the plan is finalized.
  • x - the nodes $x_j \in [0,0.5]^D, \, j = 1, \ldots, M$.
  • f - the values $f^s(\pmb{x}_j)$ for the NFST or the coefficients $f_j^s \in \mathbb{R}, j = 1, \ldots, M,$ for the transposed NFST.
  • fhat - the Fourier coefficients $\hat{f}_{\pmb{k}}^s \in \mathbb{R}$ for the NFST or the values $\hat{h}_{\pmb{k}}^s, \pmb{k} \in I_{\pmb{N},\mathrm{s}}^D,$ for the adjoint NFFT.
  • plan - plan (C pointer).

Constructor

NFST{D}( N::NTuple{D,Int32}, M::Int32, n::NTuple{D,Int32}, m::Int32, f1::UInt32, f2::UInt32 ) where {D}

Additional Constructor

NFST( N::NTuple{D,Int32}, M::Int32, n::NTuple{D,Int32}, m::Int32, f1::UInt32, f2::UInt32) where {D}
NFST( N::NTuple{D,Int32}, M::Int32) where {D}

See also

NFFT

source

Functions

NFFT3.nfst_trafo — Function
nfst_trafo(P)

computes the NDST via the fast NFST algorithm for provided nodes $\pmb{x}_j, j =1,2,\dots,M,$ in P.X and coefficients $\hat{f}_{\pmb{k}}^s \in \mathbb{R}, \pmb{k} \in I_{\pmb{N},s}^D,$ in P.fhat.

Input

  • P - a NFST plan structure.

See also

NFST{D}, nfst_trafo_direct

source
NFFT3.nfst_trafo_direct — Function
nfst_trafo_direct(P)

computes the NDST via naive matrix-vector multiplication for provided nodes $\pmb{x}_j, j =1,2,\dots,M,$ in P.X and coefficients $\hat{f}_{\pmb{k}}^s \in \mathbb{R}, \pmb{k} \in I_{\pmb{N},s}^D,$ in P.fhat.

Input

  • P - a NFST plan structure.

See also

NFST{D}, nfst_trafo

source
NFFT3.nfst_transposed — Function
nfst_transposed(P)

computes the transposed NDST via the fast transposed NFST algorithm for provided nodes $\pmb{x}_j, j =1,2,\dots,M,$ in P.X and coefficients $f_j^s \in \mathbb{R}, j =1,2,\dots,M,$ in P.f.

Input

  • P - a NFST plan structure.

See also

NFST{D}, nfst_transposed_direct

source
NFFT3.nfst_transposed_direct — Function
nfst_transposed_direct(P)

computes the transposed NDST via naive matrix-vector multiplication for provided nodes $\pmb{x}_j, j =1,2,\dots,M,$ in P.X and coefficients $f_j^s \in \mathbb{R}, j =1,2,\dots,M,$ in P.f.

Input

  • P - a NFST plan structure.

See also

NFST{D}, nfst_transposed

source

Literature