Edit on GitHub

Nonequispaced Fast Cosine Transform (NFMT)

NDMT and NFMT

We consider for $\pmb{d}\in\{\exp,\cos,\mathrm{alg}\}^d$ the trigonometric polynomial

\[f^{\pmb{d}}(\pmb{x}) \coloneqq \sum_{\pmb{k} \in I_{\pmb{N},\pmb{d}}^d} \hat{f}_{\pmb{k}}^{\pmb{d}} \, \phi_{\pmb{k}}^{\pmb{d}}(\pmb{x}), \quad \pmb{x} \in \mathbb{R}^d,\]

with

\[\phi_{\pmb{k}}^{\pmb{d}}(\pmb{x})=\prod_{j=1}^d\begin{cases}1,&k_j=0\\\exp(2\pi\mathrm{i}k_jx_j),&d_j=\exp,\;k_j\neq0\\ \sqrt{2}\cos(\pi k_jx_j),&d_j=\cos,\;k_j\neq0\\ \sqrt{2}\cos(k_j\arccos(2x_j-1)),&d_j=\mathrm{alg},\;k_j\neq0\end{cases} $$ and multibandlimit $\pmb{N} \in (2\mathbb{N})^d$ and index set $$I_{\pmb{N},\pmb{d}}^d \coloneqq \overset{d}{\underset{j=1}{\vphantom{\mathop{\raisebox{-.5ex}{\hbox{\huge{$\times$}}}}}⨉}}\begin{cases}\Big\{-\frac{N_j}{2},-\frac{N_j}{2}+1,\ldots,\frac{N_j}{2}\Big\},&d_j=\exp\\\Big\{0,1,\ldots,\frac{N_j}{2}\Big\},&d_j\neq\exp\end{cases}.\]

The NDMT is the evaluation of

\[f^{\pmb{d}}(\pmb{x}_j) \coloneqq \sum_{\pmb{k} \in I_{\pmb{N},\pmb{d}}^d} \hat{f}_{\pmb{k}}^{\pmb{d}} \, \phi_{\pmb{k}}^{\pmb{d}}(\pmb{x}_j)\]

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

\[\hat{h}^{\pmb{d}}_{\pmb{k}} = \sum_{j=1}^M f^{\pmb{d}}_j \, \phi_{\pmb{k}}^{\pmb{d}}(\pmb{x}_j)\]

for the frequencies $\pmb{k} \in I_{\pmb{N},\pmb{d}}^d$ with given coefficients $f^{\pmb{d}}_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 NDMT and transposed NDMT, obtaining the NFMT and its transposed counterpart. For details we refer to [Potts, Schröter, 2024].

Plan structure

NFFT3.NFMT — Type
NFMT{D}

A NFMT (nonequispaced fast mixed transform) plan, where D is the dimension.

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

\[f^{\pmb{d}}(\pmb{x}_j) \coloneqq \sum_{\pmb{k} \in I_{\pmb{N},\pmb{d}}^d} \hat{f}_{\pmb{k}}^{\pmb{d}} \, \phi_{\pmb{k}}^{\pmb{d}}(\pmb{x}_j)\]

with

\[\phi_{\pmb{k}}^{\pmb{d}}(\pmb{x})=\prod_{j=1}^d\begin{cases}1,&k_j=0\\\exp(2\pi\mathrm{i}k_jx_j),&d_j=\exp,\;k_j\neq0\\ \sqrt{2}\cos(\pi k_jx_j),&d_j=\cos,\;k_j\neq0\\ \sqrt{2}\cos(k_j\arccos(2x_j-1)),&d_j=\mathrm{alg},\;k_j\neq0\end{cases}\]

for $\pmb{d}\in\{\exp,\cos,\mathrm{alg}\}^d$ at given arbitrary knots $\pmb{x}_j \in [0,1]^D, j = 1, \cdots, M$, for coefficients $\hat{f}^{c}_{\pmb{k}} \in \mathbb{R}$,

\[\pmb{k}\inI_{\pmb{N},\pmb{d}}^d \coloneqq \overset{d}{\underset{j=1}{\vphantom{\mathop{\raisebox{-.5ex}{\hbox{\huge{$\times$}}}}}⨉}}\begin{cases}\Big\{-\frac{N_j}{2},-\frac{N_j}{2}+1,\ldots,\frac{N_j}{2}\Big\},&d_j=\exp\\\Big\{0,1,\ldots,\frac{N_j}{2}\Big\},&d_j\neq\exp\end{cases},\]

and a multibandlimit vector $\pmb{N} \in (2\mathbb{N})^{D}$. The transposed problem reads as

\[\hat{h}^{\pmb{d}}_{\pmb{k}} = \sum_{j=1}^M f^{\pmb{d}}_j \, \phi_{\pmb{k}}^{\pmb{d}}(\pmb{x}_j)\]

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

Fields

  • basis_vect - tuple with the bases (exp, cos, alg) for each dimension
  • NFFT_struct - underlying NFFT plan.

Constructor

NFMT{D}( basis_vect::NTuple{D,String}, P::NFFT{D}N::NTuple{D,Int32}) where {D}

WARNING: Not for direct usage!

Additional Constructor

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

with

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

See also

NFMT`

source

Functions

NFFT3.nfmt_trafo — Function
nfmt_trafo(P)

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

Input

  • P - a NFMT plan structure.

See also

NFMT{D}, nfmt_trafo_direct

source
NFFT3.nfmt_trafo_direct — Function
nfmt_trafo_direct(P)

computes the NDMT 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}} \in \mathbb{C}, \pmb{k} \in I_{\pmb{N}}^D,$ in P.fhat.

Input

  • P - a NFMT plan structure.

See also

NFMT{D}, nfmt_trafo

source
Missing docstring.

Missing docstring for nfmt_transposed. Check Documenter's build log for details.

Missing docstring.

Missing docstring for nfmt_transposed_direct. Check Documenter's build log for details.

Missing docstring.

Missing docstring for nfmt_init. Check Documenter's build log for details.

Literature