NFFT Logo 3.1.3 API Reference

NFSFT - Nonequispaced fast spherical Fourier transform

This module implements nonuniform fast spherical Fourier transforms. More...

Data Structures

struct  nfsft_plan
 Structure for a NFSFT transform plan. More...
struct  nfsft_wisdom
 Wisdom structure. More...

Defines

#define NFSFT_NORMALIZED   (1U << 0)
 By default, all computations are performed with respect to the unnormalized basis functions

\[ \tilde{Y}_k^n(\vartheta,\varphi) = P_k^{|n|}(\cos\vartheta) \mathrm{e}^{\mathrm{i} n \varphi}. \]

If this flag is set, all computations are carried out using the $L_2$- normalized basis functions

\[ Y_k^n(\vartheta,\varphi) = \sqrt{\frac{2k+1}{4\pi}} P_k^{|n|}(\cos\vartheta) \mathrm{e}^{\mathrm{i} n \varphi}. \]

.

#define NFSFT_USE_NDFT   (1U << 1)
 If this flag is set, the fast NFSFT algorithms (see nfsft_trafo, nfsft_adjoint) will use internally the exact but usually slower direct NDFT algorithm in favor of fast but approximative NFFT algorithm.
#define NFSFT_USE_DPT   (1U << 2)
 If this flag is set, the fast NFSFT algorithms (see nfsft_trafo, nfsft_adjoint) will use internally the usually slower direct DPT algorithm in favor of the fast FPT algorithm.
#define NFSFT_MALLOC_X   (1U << 3)
 If this flag is set, the init methods (see nfsft_init , nfsft_init_advanced , and nfsft_init_guru) will allocate memory and the method nfsft_finalize will free the array x for you.
#define NFSFT_MALLOC_F_HAT   (1U << 5)
 If this flag is set, the init methods (see nfsft_init , nfsft_init_advanced , and nfsft_init_guru) will allocate memory and the method nfsft_finalize will free the array f_hat for you.
#define NFSFT_MALLOC_F   (1U << 6)
 If this flag is set, the init methods (see nfsft_init , nfsft_init_advanced , and nfsft_init_guru) will allocate memory and the method nfsft_finalize will free the array f for you.
#define NFSFT_PRESERVE_F_HAT   (1U << 7)
 If this flag is set, it is guaranteed that during an execution of ndsft_trafo or nfsft_trafo the content of f_hat remains unchanged.
#define NFSFT_PRESERVE_X   (1U << 8)
 If this flag is set, it is guaranteed that during an execution of ndsft_trafo, nfsft_trafo or ndsft_adjoint, nfsft_adjoint the content of x remains unchanged.
#define NFSFT_PRESERVE_F   (1U << 9)
 If this flag is set, it is guaranteed that during an execution of ndsft_adjoint or nfsft_adjoint the content of f remains unchanged.
#define NFSFT_DESTROY_F_HAT   (1U << 10)
 If this flag is set, it is explicitely allowed that during an execution of ndsft_trafo or nfsft_trafo the content of f_hat may be changed.
#define NFSFT_DESTROY_X   (1U << 11)
 If this flag is set, it is explicitely allowed that during an execution of ndsft_trafo, nfsft_trafo or ndsft_adjoint, nfsft_adjoint the content of x may be changed.
#define NFSFT_DESTROY_F   (1U << 12)
 If this flag is set, it is explicitely allowed that during an execution of ndsft_adjoint or nfsft_adjoint the content of f may be changed.
#define NFSFT_NO_DIRECT_ALGORITHM   (1U << 13)
 If this flag is set, the transforms ndsft_trafo and ndsft_adjoint do not work.
#define NFSFT_NO_FAST_ALGORITHM   (1U << 14)
 If this flag is set, the transforms nfsft_trafo and nfsft_adjoint do not work.
#define NFSFT_ZERO_F_HAT   (1U << 16)
 If this flag is set, the transforms nfsft_adjoint and ndsft_adjoint set all unused entries in f_hat not corresponding to spherical Fourier coefficients to zero.
#define NFSFT_INDEX(k, n, plan)   ((2*(plan)->N+2)*((plan)->N-n+1)+(plan)->N+k+1)
 This helper macro expands to the index $i$ corresponding to the spherical Fourier coefficient $f_hat(k,n)$ for $0 \le k \le N$, $-k \le n \le k$ with

\[ (N+2)(N-n+1)+N+k+1 \]

.

#define NFSFT_F_HAT_SIZE(N)   ((2*N+2)*(2*N+2))
 This helper macro expands to the logical size of a spherical Fourier coefficients array for a bandwidth N.
#define BWEXP_MAX   10
#define BW_MAX   1024
#define ROW(k)   (k*(wisdom.N_MAX+2))
#define ROWK(k)   (k*(wisdom.N_MAX+2)+k)
#define NFSFT_DEFAULT_NFFT_CUTOFF   6
 The default NFFT cutoff parameter.
#define NFSFT_DEFAULT_THRESHOLD   1000
 The default threshold for the FPT.
#define NFSFT_BREAK_EVEN   5
 The break-even bandwidth $N \in \mathbb{N}_0$.

Enumerations

enum  bool { false = 0, true = 1 }

Functions

void nfsft_init (nfsft_plan *plan, int N, int M)
 Creates a transform plan.
void nfsft_init_advanced (nfsft_plan *plan, int N, int M, unsigned int nfsft_flags)
 Creates a transform plan.
void nfsft_init_guru (nfsft_plan *plan, int N, int M, unsigned int nfsft_flags, unsigned int nfft_flags, int nfft_cutoff)
 Creates a transform plan.
void nfsft_precompute (int N, double kappa, unsigned int nfsft_flags, unsigned int fpt_flags)
 Performes precomputation up to the next power of two with respect to a given bandwidth $N \in \mathbb{N}_2$.
void nfsft_forget (void)
 Forgets all precomputed data.
void ndsft_trafo (nfsft_plan *plan)
 Executes a direct NDSFT, i.e.
void ndsft_adjoint (nfsft_plan *plan)
 Executes a direct adjoint NDSFT, i.e.
void nfsft_trafo (nfsft_plan *plan)
 Executes a NFSFT, i.e.
void nfsft_adjoint (nfsft_plan *plan)
 Executes an adjoint NFSFT, i.e.
void nfsft_finalize (nfsft_plan *plan)
 Destroys a plan.
void nfsft_precompute_x (nfsft_plan *plan)
void alpha_al_row (R *alpha, const int N, const int n)
void beta_al_row (R *beta, const int N, const int n)
void gamma_al_row (R *gamma, const int N, const int n)
void alpha_al_all (R *alpha, const int N)
 Compute three-term-recurrence coefficients $\alpha_{k-1}^n$ of associated Legendre functions for $k,n = 0,1,\ldots,N$.
void beta_al_all (R *beta, const int N)
 Compute three-term-recurrence coefficients $\beta_{k-1}^n$ of associated Legendre functions for $k,n = 0,1,\ldots,N$.
void gamma_al_all (R *gamma, const int N)
 Compute three-term-recurrence coefficients $\gamma_{k-1}^n$ of associated Legendre functions for $k,n = 0,1,\ldots,N$.
void eval_al (R *x, R *y, const int size, const int k, R *alpha, R *beta, R *gamma)
 Evaluates an associated Legendre polynomials $P_k^n(x,c)$ using the Clenshaw-algorithm.
int eval_al_thresh (R *x, R *y, const int size, const int k, R *alpha, R *beta, R *gamma, R threshold)
 Evaluates an associated Legendre polynomials $P_k^n(x,c)$ using the Clenshaw-algorithm if it no exceeds a given threshold.
static void c2e (nfsft_plan *plan)
 Converts coefficients $\left(b_k^n\right)_{k=0}^M$ with $M \in \mathbb{N}_0$, $-M \le n \le M$ from a linear combination of Chebyshev polynomials

\[ f(\cos\vartheta) = \sum_{k=0}^{2\lfloor\frac{M}{2}\rfloor} a_k (\sin\vartheta)^{n\;\mathrm{mod}\;2} T_k(\cos\vartheta) \]

to coefficients $\left(c_k^n\right)_{k=0}^M$ matching the representation by complex exponentials

\[ f(\cos\vartheta) = \sum_{k=-M}^{M} c_k \mathrm{e}^{\mathrm{i}k\vartheta} \]

for each order $n=-M,\ldots,M$.

static void c2e_transposed (nfsft_plan *plan)
 Transposed version of the function c2e.

Variables

static struct nfsft_wisdom wisdom = {false,0U,-1,-1,0,0,0,0,0}
 The global wisdom structure for precomputed data.

Detailed Description

This module implements nonuniform fast spherical Fourier transforms.

In the following, we abbreviate the term "nonuniform fast spherical Fourier transform" by NFSFT.

Preliminaries

This section summarises basic definitions and properties related to spherical Fourier transforms.

Spherical Coordinates

Every point in $\mathbb{R}^3$ can be described in spherical coordinates by a vector $(r,\vartheta,\varphi)^{\mathrm{T}}$ with the radius $r \in \mathbb{R}^{+}$ and two angles $\vartheta \in [0,\pi]$, $\varphi \in [-\pi,\pi)$. We denote by $\mathbb{S}^2$ the two-dimensional unit sphere embedded into $\mathbb{R}^3$, i.e.

\[ \mathbb{S}^2 := \left\{\mathbf{x} \in \mathbb{R}^{3}:\; \|\mathbf{x}\|_2=1\right\} \]

and identify a point from $\mathbb{S}^2$ with the corresponding vector $(\vartheta,\varphi)^{\mathrm{T}}$. The spherical coordinate system is illustrated in the following figure:

sphere.png
For consistency with the other modules and the conventions used there, we also use swapped scaled spherical coordinates $x_1 := \frac{\varphi}{2\pi}$, $x_2 := \frac{\vartheta}{2\pi}$ and identify a point from $\mathbb{S}^2$ with the vector $\mathbf{x} := \left(x_1,x_2\right) \in [-\frac{1}{2}, \frac{1}{2}) \times [0,\frac{1}{2}]$.

Legendre Polynomials

The Legendre polynomials $P_k : [-1,1] \rightarrow \mathbb{R}$, $k \in \mathbb{N}_{0}$ as classical orthogonal polynomials are given by their corresponding Rodrigues formula

\[ P_k(t) := \frac{1}{2^k k!} \frac{\text{d}^k}{\text{d} t^k} \left(t^2-1\right)^k. \]

The corresponding three-term recurrence relation is

\[ (k+1)P_{k+1}(t) = (2k+1) x P_{k}(t) - k P_{k-1}(t) \quad (k \in \mathbb{N}_0). \]

With

\[ \left< f,g \right>_{\text{L}^2\left([-1,1]\right)} := \int_{-1}^{1} f(t) g(t) \text{d} t \]

being the usual $\text{L}^2\left([-1,1]\right)$ inner product, the Legendre polynomials obey the orthogonality condition

\[ \left< P_k,P_l \right>_{\text{L}^2\left([-1,1]\right)} = \frac{2}{2k+1} \delta_{k,l}. \]

Remarks:
The normalisation constant $ c_k := \sqrt{\frac{2k+1}{2}}$ renders the scaled Legendre polynomials $c_k P_k$ orthonormal with respect to the induced $\text{L}^2\left([-1,1]\right)$ norm

\[ \|f\|_{\text{L}^2\left([-1,1]\right)} := \left(<f,f>_{\text{L}^2\left([-1,1]\right)}\right)^{1/2} = \left(\int_{-1}^{1} |f(t)|^2 \; \text{d} t\right)^{1/2}. \]

Associated Legendre Functions

The associated Legendre functions $P_k^n : [-1,1] \rightarrow \mathbb{R} $, $n \in \mathbb{N}_0$, $k \ge n$ are defined by

\[ P_k^n(t) := \left(\frac{(k-n)!}{(k+n)!}\right)^{1/2} \left(1-t^2\right)^{n/2} \frac{\text{d}^n}{\text{d} t^n} P_k(t). \]

For $n = 0$, they coincide with the Legendre polynomials, i.e. $P_k^0 = P_k$. The associated Legendre functions obey the three-term recurrence relation

\[ P_{k+1}^n(t) = v_{k}^n t P_k^n(t) + w_{k}^n P_{k-1}^n(t) \quad (k \ge n), \]

with $P_{n-1}^n(t) := 0$, $P_{n}^n(t) := \frac{\sqrt{(2n)!}}{2^n n!} \left(1-t^2\right)^{n/2}$, and

\[ v_{k}^n := \frac{2k+1}{((k-n+1)(k+n+1))^{1/2}}\; ,\qquad w_{k}^n := - \frac{((k-n)(k+n))^{1/2}}{((k-n+1)(k+n+1))^{1/2}}. \]

For fixed $n$, the set $\left\{P_k^n:\: k \ge n\right\}$ forms a complete set of orthogonal functions in $\text{L}^2\left([-1,1]\right)$ with

\[ \left< P_k^n,P_l^n \right>_{\text{L}^2\left([-1,1]\right)} = \frac{2}{2k+1} \delta_{k,l} \quad (0 \le n \le k,l). \]

Remarks:
The normalisation constant $ c_k = \sqrt{\frac{2k+1}{2}}$ renders the scaled associated Legendre functions $c_k P_k^n$ orthonormal with respect to the induced $\text{L}^2\left([-1,1]\right)$ norm

\[ \|f\|_{\text{L}^2\left([-1,1]\right)} := \left(<f,f>_{\text{L}^2\left([-1,1]\right)}\right)^{1/2} = \left(\int_{-1}^{1} |f(t)|^2 \; \text{d} t\right)^{1/2}. \]

Spherical Harmonics

The standard orthogonal basis of spherical harmonics for $\text{L}^2 \left(\mathbb{S}^2\right)$ with yet unnormalised basis functions $\tilde{Y}_k^n : \mathbb{S}^2 \rightarrow \mathbb{C}$ is given by

\[ \tilde{Y}_k^n(\vartheta,\varphi) := P_k^{|n|}(\cos\vartheta) \mathrm{e}^{\mathrm{i} n \varphi} \]

with the usual $\text{L}^2\left(\mathbb{S}^2\right)$ inner product

\[ \left< f,g \right>_{\mathrm{L}^2\left(\mathbb{S}^2\right)} := \int_{\mathbb{S}^2} f(\vartheta,\varphi) \overline{g(\vartheta,\varphi)} \: \mathrm{d} \mathbf{\xi} := \int_{-\pi}^{\pi} \int_{0}^{\pi} f(\vartheta,\varphi) \overline{g(\vartheta,\varphi)} \sin \vartheta \; \mathrm{d} \vartheta \; \mathrm{d} \varphi. \]

The normalisation constant $c_k^n := \sqrt{\frac{2k+1}{4\pi}}$ renders the scaled basis functions

\[ Y_k^n(\vartheta,\varphi) := c_k^n P_k^{|n|}(\cos\vartheta) \mathrm{e}^{\mathrm{i} n \varphi} \]

orthonormal with respect to the induced $\text{L}^2\left(\mathbb{S}^2 \right)$ norm

\[ \|f\|_{\text{L}^2\left(\mathbb{S}^2\right)} = \left(<f,f>_{\text{L}^2\left(\mathbb{S}^2\right)}\right)^{1/2} = \left(\int_{-\pi}^{\pi} \int_{0}^{\pi} |f(\vartheta,\varphi)|^2 \sin \vartheta \; \mathrm{d} \vartheta \; \mathrm{d} \varphi\right)^{1/2}. \]

A function $f \in \mathrm{L}^2\left(\mathbb{S}^2\right)$ has the orthogonal expansion

\[ f = \sum_{k=0}^{\infty} \sum_{n=-k}^{k} \hat{f}(k,n) Y_k^n, \]

where the coefficients $\hat{f}(k,n) := \left< f, Y_k^{n} \right>_{\mathrm{L}^2\left(\mathbb{S}^2\right)}$ are the spherical Fourier coefficients and the equivalence is understood in the $\mathrm{L}^2$-sense.

Nonuniform Fast Spherical Fourier Transforms

This section describes the input and output relation of the spherical Fourier transform algorithms and the layout of the corresponding plan structure.

Nonuniform Discrete Spherical Fourier Transform

The nonuniform discrete spherical Fourier transform (NDSFT) is defined as follows:

\[ \begin{array}{rcl} \text{\textbf{Input}} & : & \text{coefficients } \hat{f}(k,n) \in \mathbb{C} \text{ for } k=0,\ldots,N,\;n=-k, \ldots,k,\; N \in \mathbb{N}_0,\\[1ex] & & \text{arbitrary nodes } \mathbf{x}(m) \in [-\frac{1}{2},\frac{1}{2}] \times [0,\frac{1}{2}] \text{ for } m=0,\ldots,M-1, M \in \mathbb{N}. \\[1ex] \text{\textbf{Task}} & : & \text{evaluate } f(m) := f\left( \mathbf{x}(m)\right) = \sum_{k=0}^N \sum_{n=-k}^k \hat{f}_k^n Y_k^n\left(\mathbf{x}(m)\right) \text{ for } m=0,\ldots,M-1. \\[1ex] \text{\textbf{Output}} & : & \text{coefficients } f(m) \in \mathbb{C} \text{ for } m=0,\ldots,M-1.\\ \end{array} \]

Adjoint Nonuniform Discrete Spherical Fourier Transform

The adjoint nonuniform discrete spherical Fourier transform (adjoint NDSFT) is defined as follows:

\[ \begin{array}{rcl} \text{\textbf{Input}} & : & \text{coefficients } f(m) \in \mathbb{C} \text{ for } m=0,\ldots,M-1, M \in \mathbb{N},\\ & & \text{arbitrary nodes } \mathbf{x}(m) \in [-\frac{1}{2},\frac{1}{2}] \times [0,\frac{1}{2}] \text{ for } m=0,\ldots,M-1, N \in \mathbb{N}_0.\\[1ex] \text{\textbf{Task}} & : & \text{evaluate } \hat{f}(k,n) := \sum_{m=0}^{M-1} f(m) \overline{Y_k^n\left(\mathbf{x}(m)\right)}cd Do \text{ for } k=0,\ldots,N,\;n=-k,\ldots,k.\\[1ex] \text{\textbf{Output}} & : & \text{coefficients } \hat{f}(k,n) \in \mathbb{C} \text{ for } k=0,\ldots,N,\;n=-k,\ldots,k.\\[1ex] \end{array} \]

Data Layout

This section describes the public layout of the nfsft_plan structure which contains all data for the computation of the aforementioned spherical Fourier transforms. The structure contains private (no read or write allowed), public read-only (only read access permitted), and public read-write (read and write access allowed) members. In the following, we indicate read and write access by read and write. The public members are structured as follows:

Good to know...

When using the routines of this module you should bear in mind the following:

Define Documentation

#define NFSFT_NORMALIZED   (1U << 0)

By default, all computations are performed with respect to the unnormalized basis functions

\[ \tilde{Y}_k^n(\vartheta,\varphi) = P_k^{|n|}(\cos\vartheta) \mathrm{e}^{\mathrm{i} n \varphi}. \]

If this flag is set, all computations are carried out using the $L_2$- normalized basis functions

\[ Y_k^n(\vartheta,\varphi) = \sqrt{\frac{2k+1}{4\pi}} P_k^{|n|}(\cos\vartheta) \mathrm{e}^{\mathrm{i} n \varphi}. \]

.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1803 of file nfft3.h.

Referenced by main(), ndsft_adjoint(), ndsft_trafo(), nfsft_adjoint(), and nfsft_trafo().

#define NFSFT_USE_NDFT   (1U << 1)

If this flag is set, the fast NFSFT algorithms (see nfsft_trafo, nfsft_adjoint) will use internally the exact but usually slower direct NDFT algorithm in favor of fast but approximative NFFT algorithm.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1815 of file nfft3.h.

Referenced by main(), nfsft_adjoint(), and nfsft_trafo().

#define NFSFT_USE_DPT   (1U << 2)

If this flag is set, the fast NFSFT algorithms (see nfsft_trafo, nfsft_adjoint) will use internally the usually slower direct DPT algorithm in favor of the fast FPT algorithm.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner
Warning:
This feature is not implemented yet!

Definition at line 1828 of file nfft3.h.

Referenced by main(), nfsft_adjoint(), and nfsft_trafo().

#define NFSFT_MALLOC_X   (1U << 3)

If this flag is set, the init methods (see nfsft_init , nfsft_init_advanced , and nfsft_init_guru) will allocate memory and the method nfsft_finalize will free the array x for you.

Otherwise, you have to assure by yourself that x points to an array of proper size before excuting a transform and you are responsible for freeing the corresponding memory before program termination.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1843 of file nfft3.h.

Referenced by main(), nfsft_finalize(), nfsft_init(), and nfsft_init_guru().

#define NFSFT_MALLOC_F_HAT   (1U << 5)

If this flag is set, the init methods (see nfsft_init , nfsft_init_advanced , and nfsft_init_guru) will allocate memory and the method nfsft_finalize will free the array f_hat for you.

Otherwise, you have to assure by yourself that f_hat points to an array of proper size before excuting a transform and you are responsible for freeing the corresponding memory before program termination.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1858 of file nfft3.h.

Referenced by main(), nfsft_finalize(), nfsft_init(), and nfsft_init_guru().

#define NFSFT_MALLOC_F   (1U << 6)

If this flag is set, the init methods (see nfsft_init , nfsft_init_advanced , and nfsft_init_guru) will allocate memory and the method nfsft_finalize will free the array f for you.

Otherwise, you have to assure by yourself that f points to an array of proper size before excuting a transform and you are responsible for freeing the corresponding memory before program termination.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1873 of file nfft3.h.

Referenced by main(), nfsft_finalize(), nfsft_init(), and nfsft_init_guru().

#define NFSFT_PRESERVE_F_HAT   (1U << 7)

If this flag is set, it is guaranteed that during an execution of ndsft_trafo or nfsft_trafo the content of f_hat remains unchanged.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1885 of file nfft3.h.

Referenced by ndsft_trafo(), nfsft_finalize(), nfsft_init_guru(), and nfsft_trafo().

#define NFSFT_PRESERVE_X   (1U << 8)

If this flag is set, it is guaranteed that during an execution of ndsft_trafo, nfsft_trafo or ndsft_adjoint, nfsft_adjoint the content of x remains unchanged.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1898 of file nfft3.h.

#define NFSFT_PRESERVE_F   (1U << 9)

If this flag is set, it is guaranteed that during an execution of ndsft_adjoint or nfsft_adjoint the content of f remains unchanged.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1910 of file nfft3.h.

#define NFSFT_DESTROY_F_HAT   (1U << 10)

If this flag is set, it is explicitely allowed that during an execution of ndsft_trafo or nfsft_trafo the content of f_hat may be changed.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1921 of file nfft3.h.

#define NFSFT_DESTROY_X   (1U << 11)

If this flag is set, it is explicitely allowed that during an execution of ndsft_trafo, nfsft_trafo or ndsft_adjoint, nfsft_adjoint the content of x may be changed.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1933 of file nfft3.h.

#define NFSFT_DESTROY_F   (1U << 12)

If this flag is set, it is explicitely allowed that during an execution of ndsft_adjoint or nfsft_adjoint the content of f may be changed.

See also:
nfsft_init

nfsft_init_advanced

nfsft_init_guru

Author:
Jens Keiner

Definition at line 1944 of file nfft3.h.

#define NFSFT_NO_DIRECT_ALGORITHM   (1U << 13)

If this flag is set, the transforms ndsft_trafo and ndsft_adjoint do not work.

Setting this flag saves some memory for precomputed data.

See also:
nfsft_precompute

ndsft_trafo

ndsft_adjoint

Author:
Jens Keiner

Definition at line 1957 of file nfft3.h.

Referenced by ndsft_adjoint(), ndsft_trafo(), nfsft_forget(), and nfsft_precompute().

#define NFSFT_NO_FAST_ALGORITHM   (1U << 14)

If this flag is set, the transforms nfsft_trafo and nfsft_adjoint do not work.

Setting this flag saves memory for precomputed data.

See also:
nfsft_precompute

nfsft_trafo

nfsft_adjoint

Author:
Jens Keiner

Definition at line 1968 of file nfft3.h.

Referenced by main(), nfsft_adjoint(), nfsft_forget(), nfsft_init_guru(), nfsft_precompute(), and nfsft_trafo().

#define NFSFT_ZERO_F_HAT   (1U << 16)

If this flag is set, the transforms nfsft_adjoint and ndsft_adjoint set all unused entries in f_hat not corresponding to spherical Fourier coefficients to zero.

Author:
Jens Keiner

Definition at line 1977 of file nfft3.h.

Referenced by main(), ndsft_adjoint(), and nfsft_adjoint().

#define NFSFT_DEFAULT_NFFT_CUTOFF   6

The default NFFT cutoff parameter.

Author:
Jens Keiner

Definition at line 57 of file nfsft.c.

Referenced by nfsft_init_advanced().

#define NFSFT_DEFAULT_THRESHOLD   1000

The default threshold for the FPT.

Author:
Jens Keiner

Definition at line 64 of file nfsft.c.

#define NFSFT_BREAK_EVEN   5

The break-even bandwidth $N \in \mathbb{N}_0$.

Author:
Jens Keiner

Definition at line 71 of file nfsft.c.

Referenced by nfsft_adjoint(), nfsft_forget(), nfsft_precompute(), and nfsft_trafo().


Function Documentation

void nfsft_init ( nfsft_plan plan,
int  N,
int  M 
)

Creates a transform plan.

  • plan a pointer to a nfsft_plan structure
  • N the bandwidth $N \in \mathbb{N}_0$
  • M the number of nodes $M \in \mathbb{N}$
Author:
Jens Keiner

Definition at line 248 of file nfsft.c.

References nfsft_init_advanced(), NFSFT_MALLOC_F, NFSFT_MALLOC_F_HAT, and NFSFT_MALLOC_X.

void nfsft_init_advanced ( nfsft_plan plan,
int  N,
int  M,
unsigned int  nfsft_flags 
)

Creates a transform plan.

  • plan a pointer to a
    nfsft_plan 
    structure
  • N the bandwidth $N \in \mathbb{N}_0$
  • M the number of nodes $M \in \mathbb{N}$
  • nfsft_flags the NFSFT flags
Author:
Jens Keiner

Definition at line 255 of file nfsft.c.

References FFT_OUT_OF_PLACE, FFTW_INIT, NFSFT_DEFAULT_NFFT_CUTOFF, nfsft_init_guru(), PRE_PHI_HUT, and PRE_PSI.

Referenced by nfsft_init().

void nfsft_init_guru ( nfsft_plan plan,
int  N,
int  M,
unsigned int  nfsft_flags,
unsigned int  nfft_flags,
int  nfft_cutoff 
)

Creates a transform plan.

  • plan a pointer to a
    nfsft_plan 
    structure
  • N the bandwidth $N \in \mathbb{N}_0$
  • M the number of nodes $M \in \mathbb{N}$
  • nfsft_flags the NFSFT flags
  • nfft_cutoff the NFFT cutoff parameter
Author:
Jens Keiner

Definition at line 263 of file nfsft.c.

References nfft_plan::f, nfsft_plan::f, nfft_plan::f_hat, nfsft_plan::f_hat, nfsft_plan::f_hat_intern, nfsft_plan::flags, nfsft_plan::M_total, nfsft_plan::mv_adjoint, nfsft_plan::mv_trafo, nfsft_plan::N, nfsft_plan::N_total, nfft_free(), nfft_init_guru(), nfft_malloc(), nfsft_adjoint(), NFSFT_MALLOC_F, NFSFT_MALLOC_F_HAT, NFSFT_MALLOC_X, NFSFT_NO_FAST_ALGORITHM, NFSFT_PRESERVE_F_HAT, nfsft_trafo(), nfsft_plan::plan_nfft, nfft_plan::x, and nfsft_plan::x.

Referenced by main(), and nfsft_init_advanced().

void nfsft_precompute ( int  N,
double  kappa,
unsigned int  nfsft_flags,
unsigned int  fpt_flags 
)

Performes precomputation up to the next power of two with respect to a given bandwidth $N \in \mathbb{N}_2$.

The threshold parameter $\kappa \in \mathbb{R}^{+}$ determines the number of stabilization steps computed in the discrete polynomial transform and thereby its accuracy.

  • N the bandwidth $N \in \mathbb{N}_0$
  • threshold the threshold $\kappa \in \mathbb{R}^{+}$
  • nfsft_precomputation_flags the NFSFT precomputation flags
  • fpt_precomputation_flags the FPT precomputation flags
Author:
Jens Keiner

Definition at line 352 of file nfsft.c.

References nfsft_wisdom::alpha, alpha_al_all(), nfsft_wisdom::beta, beta_al_all(), nfsft_wisdom::flags, FPT_AL_SYMMETRY, fpt_init(), FPT_PERSISTENT_DATA, fpt_precompute(), nfsft_wisdom::gamma, gamma_al_all(), nfsft_wisdom::initialized, nfsft_wisdom::N_MAX, nfft_free(), nfft_malloc(), nfft_next_power_of_2_exp(), NFSFT_BREAK_EVEN, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NO_FAST_ALGORITHM, nfsft_wisdom::set, and nfsft_wisdom::T_MAX.

Referenced by main().

void nfsft_forget ( void   ) 

void ndsft_trafo ( nfsft_plan plan  ) 

void ndsft_adjoint ( nfsft_plan plan  ) 

Executes a direct adjoint NDSFT, i.e.

computes for $k=0,\ldots,N; n=-k,\ldots,k$

\[ \hat{f}(k,n) = \sum_{m = 0}^{M-1} f(m) Y_k^n\left(2\pi x_1(m), 2\pi x_2(m)\right). \]

  • plan the plan
Author:
Jens Keiner

Definition at line 662 of file nfsft.c.

References nfsft_wisdom::alpha, nfsft_plan::f, nfsft_plan::f_hat, nfsft_plan::flags, nfsft_wisdom::flags, nfsft_wisdom::gamma, nfsft_plan::M_total, nfsft_plan::N, nfsft_plan::N_total, NFSFT_INDEX, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NORMALIZED, NFSFT_ZERO_F_HAT, PI, and nfsft_plan::x.

Referenced by main(), and nfsft_adjoint().

void nfsft_trafo ( nfsft_plan plan  ) 

void nfsft_adjoint ( nfsft_plan plan  ) 

void nfsft_finalize ( nfsft_plan plan  ) 

Destroys a plan.

  • plan the plan to be destroyed
Author:
Jens Keiner

Definition at line 493 of file nfsft.c.

References nfsft_plan::f, nfsft_plan::f_hat, nfsft_plan::f_hat_intern, nfsft_plan::flags, nfft_finalize(), nfft_free(), NFSFT_MALLOC_F, NFSFT_MALLOC_F_HAT, NFSFT_MALLOC_X, NFSFT_PRESERVE_F_HAT, nfsft_plan::plan_nfft, and nfsft_plan::x.

Referenced by main().

void alpha_al_all ( R *  alpha,
const int  N 
) [inline]

Compute three-term-recurrence coefficients $\alpha_{k-1}^n$ of associated Legendre functions for $k,n = 0,1,\ldots,N$.

  • alpha A pointer to an array of doubles of size $(N+1)^2$ where the coefficients will be stored such that alpha[n+(N+1)+k] = $\alpha_{k-1}^n$.
  • N The upper bound $N$.

Definition at line 91 of file legendre.c.

Referenced by nfsft_precompute().

void beta_al_all ( R *  beta,
const int  N 
) [inline]

Compute three-term-recurrence coefficients $\beta_{k-1}^n$ of associated Legendre functions for $k,n = 0,1,\ldots,N$.

  • beta A pointer to an array of doubles of size $(N+1)^2$ where the coefficients will be stored such that beta[n+(N+1)+k] = $\beta_{k-1}^n$.
  • N The upper bound $N$.

Definition at line 100 of file legendre.c.

Referenced by nfsft_precompute().

void gamma_al_all ( R *  gamma,
const int  N 
) [inline]

Compute three-term-recurrence coefficients $\gamma_{k-1}^n$ of associated Legendre functions for $k,n = 0,1,\ldots,N$.

  • beta A pointer to an array of doubles of size $(N+1)^2$ where the coefficients will be stored such that gamma[n+(N+1)+k] = $\gamma_{k-1}^n$.
  • N The upper bound $N$.

Definition at line 109 of file legendre.c.

Referenced by nfsft_precompute().

void eval_al ( R *  x,
R *  y,
const int  size,
const int  k,
R *  alpha,
R *  beta,
R *  gamma 
)

Evaluates an associated Legendre polynomials $P_k^n(x,c)$ using the Clenshaw-algorithm.

  • x A pointer to an array of nodes where the function is to be evaluated
  • y A pointer to an array where the function values are returned
  • size The length of x and y
  • k The index $k$
  • alpha A pointer to an array containing the recurrence coefficients $\alpha_c^n,\ldots,\alpha_{c+k}^n$
  • beta A pointer to an array containing the recurrence coefficients $\beta_c^n,\ldots,\beta_{c+k}^n$
  • gamma A pointer to an array containing the recurrence coefficients $\gamma_c^n,\ldots,\gamma_{c+k}^n$

Definition at line 118 of file legendre.c.

int eval_al_thresh ( R *  x,
R *  y,
const int  size,
const int  k,
R *  alpha,
R *  beta,
R *  gamma,
threshold 
)

Evaluates an associated Legendre polynomials $P_k^n(x,c)$ using the Clenshaw-algorithm if it no exceeds a given threshold.

  • x A pointer to an array of nodes where the function is to be evaluated
  • y A pointer to an array where the function values are returned
  • size The length of x and y
  • k The index $k$
  • alpha A pointer to an array containing the recurrence coefficients $\alpha_c^n,\ldots,\alpha_{c+k}^n$
  • beta A pointer to an array containing the recurrence coefficients $\beta_c^n,\ldots,\beta_{c+k}^n$
  • gamma A pointer to an array containing the recurrence coefficients $\gamma_c^n,\ldots,\gamma_{c+k}^n$
  • threshold The threshold

Definition at line 163 of file legendre.c.

static void c2e ( nfsft_plan plan  )  [inline, static]

Converts coefficients $\left(b_k^n\right)_{k=0}^M$ with $M \in \mathbb{N}_0$, $-M \le n \le M$ from a linear combination of Chebyshev polynomials

\[ f(\cos\vartheta) = \sum_{k=0}^{2\lfloor\frac{M}{2}\rfloor} a_k (\sin\vartheta)^{n\;\mathrm{mod}\;2} T_k(\cos\vartheta) \]

to coefficients $\left(c_k^n\right)_{k=0}^M$ matching the representation by complex exponentials

\[ f(\cos\vartheta) = \sum_{k=-M}^{M} c_k \mathrm{e}^{\mathrm{i}k\vartheta} \]

for each order $n=-M,\ldots,M$.

Remarks:
The transformation is computed in place.
Author:
Jens Keiner

Definition at line 103 of file nfsft.c.

References nfsft_plan::f_hat_intern, nfsft_plan::N, and NFSFT_INDEX.

Referenced by nfsft_trafo(), and nfsoft_trafo().

static void c2e_transposed ( nfsft_plan plan  )  [inline, static]

Transposed version of the function c2e.

Remarks:
The transformation is computed in place.
Author:
Jens Keiner

Definition at line 181 of file nfsft.c.

References nfsft_plan::f_hat, nfsft_plan::N, and NFSFT_INDEX.

Referenced by nfsft_adjoint().


Variable Documentation

struct nfsft_wisdom wisdom = {false,0U,-1,-1,0,0,0,0,0} [static]

The global wisdom structure for precomputed data.

wisdom.initialized is set to false and wisdom.flags is set to 0U.

Author:
Jens Keiner

Definition at line 79 of file nfsft.c.


Generated on 23 Dec 2009 by Doxygen 1.5.6