3.0 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 - 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 corresponding to the spherical Fourier coefficient 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) ((2N+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, 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 ()
	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)
double	alpha_al (int k, int n)
	Computes three-term recurrence coefficients $\alpha_k^n$ of associated Legendre functions.
double	beta_al (int k, int n)
	Computes three-term recurrence coefficients $\beta_k^n$ of associated Legendre functions.
double	gamma_al (int k, int n)
	Computes three-term recurrence coefficients $\gamma_k^n$ of associated Legendre functions.
void	alpha_al_row (double *alpha, int N, int n)
void	beta_al_row (double *beta, int N, int n)
void	gamma_al_row (double *gamma, int N, int n)
void	alpha_al_all (double *alpha, 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 (double *beta, 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 (double *gamma, 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 (double x, double y, int size, int k, double alpha, double beta, double *gamma)
	Evaluates an associated Legendre polynomials using the Clenshaw-algorithm.
int	eval_al_thresh (double x, double y, int size, int k, double alpha, double beta, double *gamma, double threshold)
	Evaluates an associated Legendre polynomials using the Clenshaw-algorithm if it no exceeds a given threshold.
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$ .
void	c2e_transposed (nfsft_plan *plan)
	Transposed version of the function c2e.
Variables
static struct nfsft_wisdom	wisdom = {false,0U}
	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.

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:

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:

N_total (read) The total number of components in f_hat. If the bandwidth is $N \in \mathbb{N}_0$ , the total number of components in f_hat is N_total .
M_total (read) the total number of samples
f_hat (read-write) The flattened array of spherical Fourier coefficents. The array has length such that valid indices $i \in \mathbb{N}_0$ for array access f_hat [ ] are $i=0,1,\ldots,(2N+2)^2-1$ . However, only read and write access to indices corresponding to spherical Fourier coefficients $\hat{f}(k,n)$ is defined. The index corresponding to the spherical Fourier coefficient $\hat{f}(k,n)$ with $0 \le k \le M$ , $-k \le n \le k$ is . For convenience, the helper macro NFSFT_INDEX(k,n) provides the necessary index calculations such that one can write f_hat[ NFSFT_INDEX( )] = ... to access the component corresponding to $\hat{f}(k,n)$ . The data layout is due to implementation details.
f (read-write) the array of coefficients for $m=0,\ldots,M-1$ such that f[ ] =
N (read) the bandwidth $N \in \mathbb{N}_0$
x the array of nodes $\mathbf{x}(m) \in [-\frac{1}{2},\frac{1}{2}] \times [0,\frac{1}{2}]$ for $m = 0, \ldots,M-1$ such that f[ ] = and f[ ] =

Good to know...

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

The bandwidth $N_{\text{max}}$ up to which precomputation is performed is always chosen as the next power of two with respect to the specified maximum bandwidth.
By default, the NDSFT transforms (see ndsft_trafo, nfsft_trafo) are allowed to destroy the input f_hat while the input x is preserved. On the contrary, the adjoint NDSFT transforms (see ndsft_adjoint, nfsft_adjoint) do not destroy the input f and x by default. The desired behaviour can be assured by using the NFSFT_PRESERVE_F_HAT, NFSFT_PRESERVE_X, NFSFT_PRESERVE_F and NFSFT_DESTROY_F_HAT, NFSFT_DESTROY_X, NFSFT_DESTROY_F flags.

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 1718 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 1730 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 1743 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 1758 of file nfft3.h.
Referenced by 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 1773 of file nfft3.h.
Referenced by 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 1788 of file nfft3.h.
Referenced by 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 1800 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 1813 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 1825 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 1836 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 1848 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 1859 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 1872 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 1883 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 1892 of file nfft3.h.
Referenced by ndsft_adjoint(), and nfsft_adjoint().

#define NFSFT_DEFAULT_NFFT_CUTOFF 6

The default NFFT cutoff parameter.

Author:
Jens Keiner

Definition at line 34 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 41 of file nfsft.c.

#define NFSFT_BREAK_EVEN 5

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

Author:
Jens Keiner

Definition at line 48 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 225 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 232 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 flags,

int nfft_flags,

int nfft_cutoff

)

Creates a transform plan.

Definition at line 240 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::N, nfsft_plan::N_total, nfft_init_guru(), NFSFT_MALLOC_F, NFSFT_MALLOC_F_HAT, NFSFT_MALLOC_X, NFSFT_NO_FAST_ALGORITHM, NFSFT_PRESERVE_F_HAT, 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$ .

Definition at line 326 of file nfsft.c.
References nfsft_wisdom::alpha, alpha_al_all(), alpha_al_row(), nfsft_wisdom::beta, beta_al_all(), beta_al_row(), nfsft_wisdom::flags, FPT_AL_SYMMETRY, fpt_init(), FPT_PERSISTENT_DATA, fpt_precompute(), nfsft_wisdom::gamma, gamma_al_all(), gamma_al_row(), nfsft_wisdom::initialized, nfsft_wisdom::N_MAX, nfft_next_power_of_2_exp(), NFSFT_BREAK_EVEN, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NO_FAST_ALGORITHM, ROW, nfsft_wisdom::set, and nfsft_wisdom::T_MAX.
Referenced by main().

void nfsft_forget ( )

Forgets all precomputed data.

Author:
Jens Keiner

Definition at line 428 of file nfsft.c.
References nfsft_wisdom::alpha, nfsft_wisdom::beta, nfsft_wisdom::flags, fpt_finalize(), nfsft_wisdom::gamma, nfsft_wisdom::initialized, nfsft_wisdom::N_MAX, NFSFT_BREAK_EVEN, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NO_FAST_ALGORITHM, and nfsft_wisdom::set.
Referenced by main().

void ndsft_trafo ( nfsft_plan * plan )

Executes a direct NDSFT, i.e.
computes for $m = 0,\ldots,M-1$
$f(m) = \sum_{k=0}^N \sum_{n=-k}^k \hat{f}(k,n) Y_k^n\left(2\pi x_1(m), 2\pi x_2(m)\right).$

plan the plan

Author:
Jens Keiner

Definition at line 501 of file nfsft.c.
References nfsft_wisdom::alpha, nfsft_plan::f, nfsft_plan::f_hat, nfsft_plan::f_hat_intern, nfsft_plan::flags, nfsft_wisdom::flags, nfsft_wisdom::gamma, nfsft_plan::N, nfsft_plan::N_total, NFSFT_INDEX, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NORMALIZED, NFSFT_PRESERVE_F_HAT, PI, ROW, ROWK, and nfsft_plan::x.
Referenced by main(), and nfsft_trafo().

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 633 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::N, nfsft_plan::N_total, NFSFT_INDEX, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NORMALIZED, NFSFT_ZERO_F_HAT, PI, ROW, ROWK, and nfsft_plan::x.
Referenced by main(), and nfsft_adjoint().

void nfsft_trafo ( nfsft_plan * plan )

Executes a NFSFT, i.e.
computes for $m = 0,\ldots,M-1$
$f(m) = \sum_{k=0}^N \sum_{n=-k}^k \hat{f}(k,n) Y_k^n\left(2\pi x_1(m), 2\pi x_2(m)\right).$

plan the plan

Author:
Jens Keiner

Definition at line 745 of file nfsft.c.
References c2e(), dpt_trafo(), nfsft_plan::f, nfft_plan::f, nfft_plan::f_hat, nfsft_plan::f_hat, nfsft_plan::f_hat_intern, nfsft_plan::flags, nfsft_wisdom::flags, fpt_trafo(), nfsft_wisdom::initialized, nfsft_plan::N, nfsft_wisdom::N_MAX, nfsft_plan::N_total, ndft_trafo(), ndsft_trafo(), nfft_trafo(), NFSFT_BREAK_EVEN, NFSFT_INDEX, NFSFT_NO_FAST_ALGORITHM, NFSFT_NORMALIZED, NFSFT_PRESERVE_F_HAT, NFSFT_USE_DPT, NFSFT_USE_NDFT, PI, nfsft_plan::plan_nfft, nfsft_wisdom::set, nfsft_plan::x, and nfft_plan::x.
Referenced by main().

void nfsft_adjoint ( nfsft_plan * plan )

Executes an adjoint NFSFT, 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 864 of file nfsft.c.
References c2e_transposed(), dpt_transposed(), nfsft_plan::f, nfft_plan::f, nfsft_plan::f_hat, nfft_plan::f_hat, nfsft_plan::flags, nfsft_wisdom::flags, fpt_transposed(), nfsft_wisdom::initialized, nfsft_plan::N, nfsft_wisdom::N_MAX, ndft_adjoint(), ndsft_adjoint(), nfft_adjoint(), NFSFT_BREAK_EVEN, NFSFT_INDEX, NFSFT_NO_FAST_ALGORITHM, NFSFT_NORMALIZED, NFSFT_USE_DPT, NFSFT_USE_NDFT, NFSFT_ZERO_F_HAT, PI, nfsft_plan::plan_nfft, nfsft_wisdom::set, nfsft_plan::x, and nfft_plan::x.
Referenced by main().

void nfsft_finalize ( nfsft_plan * plan )

Destroys a plan.

plan the plan to be destroyed

Author:
Jens Keiner

Definition at line 467 of file nfsft.c.
References nfsft_plan::f, nfsft_plan::f_hat, nfsft_plan::f_hat_intern, nfsft_plan::flags, nfft_finalize(), 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().

double alpha_al ( int k,

int n

) [inline]

Computes three-term recurrence coefficients $\alpha_k^n$ of associated Legendre functions.

k The index $k$

n The index $n$

Definition at line 9 of file legendre.c.
Referenced by alpha_al_all(), and alpha_al_row().

double beta_al ( int k,

int n

) [inline]

Computes three-term recurrence coefficients $\beta_k^n$ of associated Legendre functions.

k The index $k$

n The index $n$

Definition at line 36 of file legendre.c.
Referenced by beta_al_all(), and beta_al_row().

double gamma_al ( int k,

int n

) [inline]

Computes three-term recurrence coefficients $\gamma_k^n$ of associated Legendre functions.

k The index $k$

n The index $n$

Definition at line 48 of file legendre.c.
Referenced by gamma_al_all(), and gamma_al_row().

void alpha_al_all ( double * alpha,

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 106 of file legendre.c.
References alpha_al().
Referenced by nfsft_precompute().

void beta_al_all ( double * beta,

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 120 of file legendre.c.
References beta_al().
Referenced by nfsft_precompute().

void gamma_al_all ( double * gamma,

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 134 of file legendre.c.
References gamma_al().
Referenced by nfsft_precompute().

void eval_al ( double * x,

double * y,

int size,

int k,

double * alpha,

double * beta,

double * gamma

) [inline]

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 148 of file legendre.c.

int eval_al_thresh ( double * x,

double * y,

int size,

int k,

double * alpha,

double * beta,

double * gamma,

double threshold

) [inline]

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 193 of file legendre.c.

void c2e ( nfsft_plan * plan ) [inline]

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

plan The nfsft_plan containing the coefficients $\left(b_k^n\right)_{k=0,\ldots,M;n=-M,\ldots,M}$

Remarks:
The transformation is computed in place.

Author:
Jens Keiner
< The degree k
< The order k
< Stores temporary values
< Stores temporary values
< Auxilliary pointer
< Auxilliary pointer
< Lower loop bound
< Upper loop bound
< Lower loop bound for even terms
< Upper loop bound for even terms
Definition at line 80 of file nfsft.c.
References nfsft_plan::f_hat_intern, nfsft_plan::N, and NFSFT_INDEX.
Referenced by nfsft_trafo().

void c2e_transposed ( nfsft_plan * plan ) [inline]

Transposed version of the function c2e.

plan The nfsft_plan containing the coefficients $\left(c_k^n\right)_{k=-M,\ldots,M;n=-M,\ldots,M}$

Remarks:
The transformation is computed in place.

Author:
Jens Keiner
< The degree k
< The order k
< Stores temporary values
< Stores temporary values
< Auxilliary pointer
< Auxilliary pointer
< Lower loop bound
< Upper loop bound
< Lower loop bound for even terms
< Upper loop bound for even terms
Definition at line 158 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} [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 56 of file nfsft.c.

Generated on 1 Nov 2006 by Doxygen 1.4.4

NFSFT - Nonequispaced fast spherical Fourier transform

Data Structures

Defines

Enumerations

Functions

Variables

Detailed Description

Define Documentation

Function Documentation

Variable Documentation