NFSFT - Nonequispaced fast spherical Fourier transform

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

## Data Structures

struct | nfsft_wisdom
| Wisdom structure. More...
struct | nfsft_plan
| data structure for an NFSFT (nonequispaced fast spherical Fourier transform) plan with double precision More...

## Macros

#define | NFSFT_NORMALIZED (1U << 0)
#define | NFSFT_USE_NDFT (1U << 1)
#define | NFSFT_USE_DPT (1U << 2)
#define | NFSFT_MALLOC_X (1U << 3)
#define | NFSFT_MALLOC_F_HAT (1U << 5)
#define | NFSFT_MALLOC_F (1U << 6)
#define | NFSFT_PRESERVE_F_HAT (1U << 7)
#define | NFSFT_PRESERVE_X (1U << 8)
#define | NFSFT_PRESERVE_F (1U << 9)
#define | NFSFT_DESTROY_F_HAT (1U << 10)
#define | NFSFT_DESTROY_X (1U << 11)
#define | NFSFT_DESTROY_F (1U << 12)
#define | NFSFT_NO_DIRECT_ALGORITHM (1U << 13)
#define | NFSFT_NO_FAST_ALGORITHM (1U << 14)
#define | NFSFT_ZERO_F_HAT (1U << 16)
#define | NFSFT_EQUISPACED (1U << 17)
#define | NFSFT_INDEX(k, n, plan)
#define | NFSFT_F_HAT_SIZE(N)
#define | BWEXP_MAX 10
#define | BW_MAX 1024
#define | ROW(k)
#define | ROWK(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 .

## Enumerations

enum | bool { false = 0 , true = 1 }

## Functions

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 of associated Legendre functions for .
void | beta_al_all (R *beta, const int N)
| Compute three-term-recurrence coefficients of associated Legendre functions for .
void | gamma_al_all (R *gamma, const int N)
| Compute three-term-recurrence coefficients of associated Legendre functions for .
void | eval_al (R *x, R *y, const int size, const int k, R *alpha, R *beta, R *gamma)
| Evaluates an associated Legendre polynomials 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 using the Clenshaw-algorithm if it no exceeds a given threshold.
static void | c2e (nfsft_plan *plan)
| Converts coefficients with , from a linear combination of Chebyshev polynomials.
static void | c2e_transposed (nfsft_plan *plan)
| Transposed version of the function c2e.
void | nfsft_init (nfsft_plan *plan, int N, int M)
void | nfsft_init_advanced (nfsft_plan *plan, int N, int M, unsigned int flags)
void | nfsft_init_guru (nfsft_plan *plan, int N, int M, unsigned int flags, unsigned int nfft_flags, int nfft_cutoff)
void | nfsft_precompute (int N, double kappa, unsigned int nfsft_flags, unsigned int fpt_flags)
void | nfsft_forget (void)
void | nfsft_finalize (nfsft_plan *plan)
static void | nfsft_set_f_nan (nfsft_plan *plan)
void | nfsft_trafo_direct (nfsft_plan *plan)
static void | nfsft_set_f_hat_nan (nfsft_plan *plan)
void | nfsft_adjoint_direct (nfsft_plan *plan)
void | nfsft_trafo (nfsft_plan *plan)
void | nfsft_adjoint (nfsft_plan *plan)
void | nfsft_precompute_x (nfsft_plan *plan)

## Variables

bool | nfsft_wisdom::initialized
| Indicates wether the structure has been initialized.
unsigned int | nfsft_wisdom::flags
int | nfsft_wisdom::N_MAX
| Stores precomputation flags.
int | nfsft_wisdom::T_MAX
| The logarithm /f$t = \log_2 N_{\text{max}}/f$ of the maximum bandwidth.
double * | nfsft_wisdom::alpha
| Precomputed recursion coefficients /f$\alpha_k^n/f$ for /f$k = 0,/ldots, N_{\text{max}}; n=-k,/ldots,k/f$ of associated Legendre-functions /f$P_k^n/f$.
double * | nfsft_wisdom::beta
| Precomputed recursion coefficients /f$\beta_k^n/f$ for /f$k = 0,/ldots, N_{\text{max}}; n=-k,/ldots,k/f$ of associated Legendre-functions /f$P_k^n/f$.
double * | nfsft_wisdom::gamma
| Precomputed recursion coefficients /f$\gamma_k^n/f$ for /f$k = 0,/ldots, N_{\text{max}}; n=-k,/ldots,k/f$ of associated Legendre-functions /f$P_k^n/f$.
double | nfsft_wisdom::threshold
| The threshold /f$\kappa/f$.
fpt_set | nfsft_wisdom::set
| Structure for discrete polynomial transform (DPT).
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 can be described in spherical coordinates by a vector with the radius and two angles , . We denote by the two-dimensional unit sphere embedded into , i.e.

and identify a point from with the corresponding vector . 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 , and identify a point from with the vector .

## Legendre Polynomials

The Legendre polynomials as classical orthogonal polynomials are given by their corresponding Rodrigues formula

The corresponding three-term recurrence relation is

With

being the usual inner product, the Legendre polynomials obey the orthogonality condition

Remarks
  The normalisation constant renders the scaled Legendre polynomials orthonormal with respect to the induced norm

## Associated Legendre Functions

The associated Legendre functions , , are defined by

For , they coincide with the Legendre polynomials, i.e. . The associated Legendre functions obey the three-term recurrence relation

with , , and

For fixed , the set forms a complete set of orthogonal functions in with

Remarks
  The normalisation constant renders the scaled associated Legendre functions orthonormal with respect to the induced norm

## Spherical Harmonics

The standard orthogonal basis of spherical harmonics for with yet unnormalised basis functions is given by

with the usual inner product

The normalisation constant renders the scaled basis functions

orthonormal with respect to the induced norm

A function has the orthogonal expansion

where the coefficients are the spherical Fourier coefficients and the equivalence is understood in the -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:

## Adjoint Nonuniform Discrete Spherical Fourier Transform

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

## 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 , 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 for array access `f_hat` ``[ ``] are . However, only read and write access to indices corresponding to spherical Fourier coefficients is defined. The index corresponding to the spherical Fourier coefficient with , 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 . The data layout is due to implementation details.
- `f` (`read-write`) the array of coefficients for such that `f`[ ``] =
- `N` (`read`) the bandwidth
- `x` the array of nodes for such that `x`[ ``] = and `x`[ ``] =

## Good to know...

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

- The bandwidth 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 nfsft_direct_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 nfsft_direct_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.

## Macro Definition Documentation

## NFSFT_NORMALIZED

#define NFSFT_NORMALIZED (1U << 0)

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

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

See also
  nfsft_init
  nfsft_init_advanced
  nfsft_init_guru

Author
  Jens Keiner

Definition at line 579 of file nfft3.h.

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

## NFSFT_USE_NDFT

#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 580 of file nfft3.h.

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

## NFSFT_USE_DPT

#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

Definition at line 581 of file nfft3.h.

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

## NFSFT_MALLOC_X

#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 582 of file nfft3.h.

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

## NFSFT_MALLOC_F_HAT

#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 583 of file nfft3.h.

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

## NFSFT_MALLOC_F

#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 584 of file nfft3.h.

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

## NFSFT_PRESERVE_F_HAT

#define NFSFT_PRESERVE_F_HAT (1U << 7)

If this flag is set, it is guaranteed that during an execution of nfsft_direct_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 585 of file nfft3.h.

Referenced by nfsft_finalize(), and nfsft_trafo().

## NFSFT_PRESERVE_X

#define NFSFT_PRESERVE_X (1U << 8)

If this flag is set, it is guaranteed that during an execution of nfsft_direct_trafo, nfsft_trafo or nfsft_direct_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 586 of file nfft3.h.

## NFSFT_PRESERVE_F

#define NFSFT_PRESERVE_F (1U << 9)

If this flag is set, it is guaranteed that during an execution of nfsft_direct_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 587 of file nfft3.h.

## NFSFT_DESTROY_F_HAT

#define NFSFT_DESTROY_F_HAT (1U << 10)

If this flag is set, it is explicitely allowed that during an execution of nfsft_direct_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 588 of file nfft3.h.

## NFSFT_DESTROY_X

#define NFSFT_DESTROY_X (1U << 11)

If this flag is set, it is explicitely allowed that during an execution of nfsft_direct_trafo, nfsft_trafo or nfsft_direct_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 589 of file nfft3.h.

## NFSFT_DESTROY_F

#define NFSFT_DESTROY_F (1U << 12)

If this flag is set, it is explicitely allowed that during an execution of nfsft_direct_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 590 of file nfft3.h.

## NFSFT_NO_DIRECT_ALGORITHM

#define NFSFT_NO_DIRECT_ALGORITHM (1U << 13)

If this flag is set, the transforms nfsft_direct_trafo and nfsft_direct_adjoint do not work. Setting this flag saves some memory for precomputed data.

See also
  nfsft_precompute
  nfsft_direct_trafo
  nfsft_direct_adjoint

Author
  Jens Keiner

Definition at line 594 of file nfft3.h.

Referenced by nfsft_forget(), and nfsft_precompute().

## NFSFT_NO_FAST_ALGORITHM

#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 595 of file nfft3.h.

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

## NFSFT_ZERO_F_HAT

#define NFSFT_ZERO_F_HAT (1U << 16)

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

Author
  Jens Keiner

Definition at line 596 of file nfft3.h.

Referenced by main(), and nfsft_adjoint().

## NFSFT_EQUISPACED

#define NFSFT_EQUISPACED (1U << 17)

If this flag is set, we use the equispaced FFT instead of the NFFT. This implies that the nodes are fixed to

Author
  Michael Quellmalz

Definition at line 591 of file nfft3.h.

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

## NFSFT_INDEX

#define NFSFT_INDEX | ( |  | k,
|  |  | n,
|  |  | plan )

Value:
((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 , with

Definition at line 599 of file nfft3.h.

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

## NFSFT_F_HAT_SIZE

#define NFSFT_F_HAT_SIZE | ( |  | N | ) |

Value:
((2*N+2)*(2*N+2))

This helper macro expands to the logical size of a spherical Fourier coefficients array for a bandwidth N.

Definition at line 600 of file nfft3.h.

Referenced by main().

## BWEXP_MAX

#define BWEXP_MAX 10

Definition at line 35 of file kernel/nfsft/api.h.

## BW_MAX

#define BW_MAX 1024

Definition at line 38 of file kernel/nfsft/api.h.

## ROW

#define ROW | ( |  | k | ) |

Value:
(k*(wisdom.N_MAX+2))
wisdom
static struct nfsft_wisdom wisdom
The global wisdom structure for precomputed data.
Definition nfsft.c:90

Definition at line 40 of file kernel/nfsft/api.h.

## ROWK

#define ROWK | ( |  | k | ) |

Value:
(k*(wisdom.N_MAX+2)+k)

Definition at line 41 of file kernel/nfsft/api.h.

## NFSFT_DEFAULT_NFFT_CUTOFF

#define NFSFT_DEFAULT_NFFT_CUTOFF 6

The default NFFT cutoff parameter.

Author
  Jens Keiner

Definition at line 65 of file nfsft.c.

Referenced by nfsft_init_advanced().

## NFSFT_DEFAULT_THRESHOLD

#define NFSFT_DEFAULT_THRESHOLD 1000

The default threshold for the FPT.

Author
  Jens Keiner

Definition at line 72 of file nfsft.c.

## NFSFT_BREAK_EVEN

#define NFSFT_BREAK_EVEN 5

The break-even bandwidth .

Author
  Jens Keiner

Definition at line 79 of file nfsft.c.

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

## Enumeration Type Documentation

## bool

enum bool

Definition at line 46 of file kernel/nfsft/api.h.

## Function Documentation

## alpha_al_row()

void alpha_al_row | ( | R * | alpha,
|  | const int | N,
|  | const int | n )

Definition at line 65 of file legendre.c.

## beta_al_row()

void beta_al_row | ( | R * | beta,
|  | const int | N,
|  | const int | n )

Definition at line 73 of file legendre.c.

## gamma_al_row()

void gamma_al_row | ( | R * | gamma,
|  | const int | N,
|  | const int | n )

Definition at line 81 of file legendre.c.

## alpha_al_all()

void alpha_al_all | ( | R * | alpha,
|  | const int | N )

inline

Compute three-term-recurrence coefficients of associated Legendre functions for .

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

Definition at line 89 of file legendre.c.

Referenced by nfsft_precompute().

## beta_al_all()

void beta_al_all | ( | R * | beta,
|  | const int | N )

inline

Compute three-term-recurrence coefficients of associated Legendre functions for .

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

Definition at line 98 of file legendre.c.

Referenced by nfsft_precompute().

## gamma_al_all()

void gamma_al_all | ( | R * | gamma,
|  | const int | N )

inline

Compute three-term-recurrence coefficients of associated Legendre functions for .

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

Definition at line 107 of file legendre.c.

Referenced by nfsft_precompute().

## eval_al()

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

Evaluates an associated Legendre polynomials 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
- alpha A pointer to an array containing the recurrence coefficients
- beta A pointer to an array containing the recurrence coefficients
- gamma A pointer to an array containing the recurrence coefficients

Definition at line 116 of file legendre.c.

## eval_al_thresh()

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 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
- alpha A pointer to an array containing the recurrence coefficients
- beta A pointer to an array containing the recurrence coefficients
- gamma A pointer to an array containing the recurrence coefficients
- threshold The threshold

Definition at line 161 of file legendre.c.

## c2e()

void c2e | ( | nfsft_plan * | plan | ) |

inline static

Converts coefficients with , from a linear combination of Chebyshev polynomials.

to coefficients matching the representation by complex exponentials

for each order .

- plan The `nfsft_plan` containing the coefficients

Remarks
  The transformation is computed in place.

Author
  Jens Keiner

Definition at line 115 of file nfsft.c.

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

Referenced by nfsft_trafo(), and nfsoft_trafo().

## c2e_transposed()

void c2e_transposed | ( | nfsft_plan * | plan | ) |

inline static

Transposed version of the function c2e.

- plan The `nfsft_plan` containing the coefficients

Remarks
  The transformation is computed in place.

Author
  Jens Keiner

Definition at line 193 of file nfsft.c.

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

Referenced by nfsft_adjoint().

## nfsft_init()

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
- M the number of nodes

Author
  Jens Keiner

Definition at line 260 of file nfsft.c.

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

## nfsft_init_advanced()

void nfsft_init_advanced | ( | nfsft_plan * | plan,
|  | int | N,
|  | int | M,
|  | unsigned int | flags )

Creates a transform plan.

- plan a pointer to a

      nfsft_plan

  structure
- N the bandwidth
- M the number of nodes
- nfsft_flags the NFSFT flags

Author
  Jens Keiner

Definition at line 267 of file nfsft.c.

References FFTW_INIT, NFSFT_DEFAULT_NFFT_CUTOFF, PRE_PHI_HUT, and PRE_PSI.

Referenced by nfsft_init().

## nfsft_init_guru()

void nfsft_init_guru | ( | nfsft_plan * | plan,
|  | int | N,
|  | int | M,
|  | unsigned int | flags,
|  | unsigned int | nfft_flags,
|  | int | nfft_cutoff )

Definition at line 275 of file nfsft.c.

## nfsft_precompute()

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 . The threshold parameter determines the number of stabilization steps computed in the discrete polynomial transform and thereby its accuracy.

- N the bandwidth
- threshold the threshold
- nfsft_precomputation_flags the NFSFT precomputation flags
- fpt_precomputation_flags the FPT precomputation flags

Author
  Jens Keiner

Definition at line 376 of file nfsft.c.

References nfsft_wisdom::alpha, alpha_al_all(), nfsft_wisdom::beta, beta_al_all(), FPT_AL_SYMMETRY, fpt_init(), FPT_PERSISTENT_DATA, fpt_precompute(), nfsft_wisdom::gamma, gamma_al_all(), nfft_free(), nfft_malloc(), NFSFT_BREAK_EVEN, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NO_FAST_ALGORITHM, wisdom, and X.

Referenced by main().

## nfsft_forget()

void nfsft_forget | ( | void |  | ) |

Forgets all precomputed data.

Author
  Jens Keiner

Definition at line 579 of file nfsft.c.

References nfft_free(), NFSFT_BREAK_EVEN, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NO_FAST_ALGORITHM, and wisdom.

Referenced by main().

## nfsft_finalize()

void nfsft_finalize | ( | nfsft_plan * | plan | ) |

Destroys a plan.

- plan the plan to be destroyed

Author
  Jens Keiner

Definition at line 625 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_EQUISPACED, NFSFT_MALLOC_F, NFSFT_MALLOC_F_HAT, NFSFT_MALLOC_X, NFSFT_NO_FAST_ALGORITHM, NFSFT_PRESERVE_F_HAT, nfsft_plan::plan_nfft, and nfsft_plan::x.

Referenced by main().

## nfsft_set_f_nan()

void nfsft_set_f_nan | ( | nfsft_plan * | plan | ) |

static

Definition at line 665 of file nfsft.c.

## nfsft_trafo_direct()

void nfsft_trafo_direct | ( | nfsft_plan * | plan | ) |

Definition at line 673 of file nfsft.c.

## nfsft_set_f_hat_nan()

void nfsft_set_f_hat_nan | ( | nfsft_plan * | plan | ) |

static

Definition at line 845 of file nfsft.c.

## nfsft_adjoint_direct()

void nfsft_adjoint_direct | ( | nfsft_plan * | plan | ) |

Definition at line 854 of file nfsft.c.

## nfsft_trafo()

void nfsft_trafo | ( | nfsft_plan * | plan | ) |

Executes a NFSFT, i.e. computes for

- plan the plan

Author
  Jens Keiner

Definition at line 1068 of file nfsft.c.

References c2e(), nfsft_plan::f, nfsft_plan::f_hat, nfsft_plan::f_hat_intern, nfsft_plan::flags, nfsft_plan::MEASURE_TIME_t, nfsft_plan::N, nfsft_plan::N_total, nfft_elapsed_seconds(), NFSFT_BREAK_EVEN, NFSFT_EQUISPACED, NFSFT_INDEX, NFSFT_NO_FAST_ALGORITHM, NFSFT_NORMALIZED, NFSFT_PRESERVE_F_HAT, NFSFT_USE_DPT, NFSFT_USE_NDFT, nfsft_plan::plan_nfft, wisdom, and nfsft_plan::x.

Referenced by main().

## nfsft_adjoint()

void nfsft_adjoint | ( | nfsft_plan * | plan | ) |

Executes an adjoint NFSFT, i.e. computes for

- plan the plan

Author
  Jens Keiner

Definition at line 1316 of file nfsft.c.

References c2e_transposed(), nfsft_plan::f, nfsft_plan::f_hat, nfsft_plan::flags, nfsft_plan::MEASURE_TIME_t, nfsft_plan::N, nfft_elapsed_seconds(), NFSFT_BREAK_EVEN, NFSFT_EQUISPACED, NFSFT_INDEX, NFSFT_NO_FAST_ALGORITHM, NFSFT_NORMALIZED, NFSFT_USE_DPT, NFSFT_USE_NDFT, NFSFT_ZERO_F_HAT, nfsft_plan::plan_nfft, wisdom, and nfsft_plan::x.

Referenced by main().

## nfsft_precompute_x()

void nfsft_precompute_x | ( | nfsft_plan * | plan | ) |

Definition at line 1551 of file nfsft.c.

## Variable Documentation

## initialized

bool nfsft_wisdom::initialized

Indicates wether the structure has been initialized.

Definition at line 59 of file kernel/nfsft/api.h.

## flags

unsigned int nfsft_wisdom::flags

Definition at line 60 of file kernel/nfsft/api.h.

## N_MAX

int nfsft_wisdom::N_MAX

Stores precomputation flags.

The maximum bandwidth /f$N_{\text{max}} \in \mathbb{N}_0/f$

Definition at line 63 of file kernel/nfsft/api.h.

## T_MAX

int nfsft_wisdom::T_MAX

The logarithm /f$t = \log_2 N_{\text{max}}/f$ of the maximum bandwidth.

Definition at line 65 of file kernel/nfsft/api.h.

## alpha

double* nfsft_wisdom::alpha

Precomputed recursion coefficients /f$\alpha_k^n/f$ for /f$k = 0,/ldots, N_{\text{max}}; n=-k,/ldots,k/f$ of associated Legendre-functions /f$P_k^n/f$.

Definition at line 74 of file kernel/nfsft/api.h.

Referenced by nfsft_precompute().

## beta

double* nfsft_wisdom::beta

Precomputed recursion coefficients /f$\beta_k^n/f$ for /f$k = 0,/ldots, N_{\text{max}}; n=-k,/ldots,k/f$ of associated Legendre-functions /f$P_k^n/f$.

Definition at line 80 of file kernel/nfsft/api.h.

Referenced by nfsft_precompute().

## gamma

double* nfsft_wisdom::gamma

Precomputed recursion coefficients /f$\gamma_k^n/f$ for /f$k = 0,/ldots, N_{\text{max}}; n=-k,/ldots,k/f$ of associated Legendre-functions /f$P_k^n/f$.

Definition at line 86 of file kernel/nfsft/api.h.

Referenced by nfsft_precompute().

## threshold

double nfsft_wisdom::threshold

The threshold /f$\kappa/f$.

Definition at line 91 of file kernel/nfsft/api.h.

## set

fpt_set nfsft_wisdom::set

Structure for discrete polynomial transform (DPT).

Definition at line 97 of file kernel/nfsft/api.h.

## wisdom

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 90 of file nfsft.c.

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