![]() |
NFFT 3.5.3alpha
|
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) ((2*(plan)->N+2)*((plan)->N-n+1)+(plan)->N+k+1) |
#define | NFSFT_F_HAT_SIZE(N) ((2*N+2)*(2*N+2)) |
#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 ![]() | |
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 ![]() ![]() | |
void | beta_al_all (R *beta, const int N) |
Compute three-term-recurrence coefficients ![]() ![]() | |
void | gamma_al_all (R *gamma, const int N) |
Compute three-term-recurrence coefficients ![]() ![]() | |
void | eval_al (R *x, R *y, const int size, const int k, R *alpha, R *beta, R *gamma) |
Evaluates an associated Legendre polynomials ![]() | |
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 ![]() | |
static void | c2e (nfsft_plan *plan) |
Converts coefficients ![]() ![]() ![]() | |
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. | |
This module implements nonuniform fast spherical Fourier transforms.
In the following, we abbreviate the term "nonuniform fast spherical Fourier transform" by NFSFT.
This section summarises basic definitions and properties related to spherical Fourier transforms.
Every point in
and identify a point from
For consistency with the other modules and the conventions used there, we also use swapped scaled spherical coordinates\iline 53
The Legendre polynomials\iline 60
The corresponding three-term recurrence relation is
With
being the usual
The associated Legendre functions\iline 95
For
with
For fixed
The standard orthogonal basis of spherical harmonics for
with the usual
The normalisation constant
orthonormal with respect to the induced
A function
where the coefficients
This section describes the input and output relation of the spherical Fourier transform algorithms and the layout of the corresponding plan structure.
The nonuniform discrete spherical Fourier transform (NDSFT) is defined as follows:
The adjoint nonuniform discrete spherical Fourier transform (adjoint NDSFT) is defined as follows:
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 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 f_hat
[
] are f_hat
[ NFSFT_INDEX
(
)] =
... to access the component corresponding to f
(read-write
) the array of coefficients f
[
] = N
(read
) the bandwidth x
the array of nodes x
[
] = x
[
] = When using the routines of this module you should bear in mind the following:
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. #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
#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. 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.
#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.
#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.
#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.
#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.
#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.
#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.
#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.
#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.
#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.
#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.
#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.
#define NFSFT_EQUISPACED (1U << 17) |
#define NFSFT_INDEX | ( | k, | |
n, | |||
plan | |||
) | ((2*(plan)->N+2)*((plan)->N-n+1)+(plan)->N+k+1) |
#define NFSFT_F_HAT_SIZE | ( | N | ) | ((2*N+2)*(2*N+2)) |
#define BWEXP_MAX 10 |
Definition at line 35 of file kernel/nfsft/api.h.
#define BW_MAX 1024 |
Definition at line 38 of file kernel/nfsft/api.h.
#define ROW | ( | k | ) | (k*(wisdom.N_MAX+2)) |
Definition at line 40 of file kernel/nfsft/api.h.
#define ROWK | ( | k | ) | (k*(wisdom.N_MAX+2)+k) |
Definition at line 41 of file kernel/nfsft/api.h.
#define NFSFT_DEFAULT_NFFT_CUTOFF 6 |
#define NFSFT_DEFAULT_THRESHOLD 1000 |
enum bool |
Definition at line 46 of file kernel/nfsft/api.h.
void alpha_al_row | ( | R * | alpha, |
const int | N, | ||
const int | n | ||
) |
Definition at line 65 of file legendre.c.
void beta_al_row | ( | R * | beta, |
const int | N, | ||
const int | n | ||
) |
Definition at line 73 of file legendre.c.
void gamma_al_row | ( | R * | gamma, |
const int | N, | ||
const int | n | ||
) |
Definition at line 81 of file legendre.c.
|
inline |
Compute three-term-recurrence coefficients
Definition at line 89 of file legendre.c.
Referenced by nfsft_precompute().
|
inline |
Compute three-term-recurrence coefficients
Definition at line 98 of file legendre.c.
Referenced by nfsft_precompute().
|
inline |
Compute three-term-recurrence coefficients
Definition at line 107 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
Definition at line 116 of file legendre.c.
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
Definition at line 161 of file legendre.c.
|
inlinestatic |
Converts coefficients
to coefficients
for each order
nfsft_plan
containing the coefficients Definition at line 115 of file nfsft.c.
References nfsft_plan::f_hat_intern, nfsft_plan::N, and NFSFT_INDEX.
Referenced by nfsft_trafo().
|
inlinestatic |
Transposed version of the function c2e.
nfsft_plan
containing the coefficients Definition at line 193 of file nfsft.c.
References nfsft_plan::f_hat, nfsft_plan::N, and NFSFT_INDEX.
Referenced by nfsft_adjoint().
void nfsft_init | ( | nfsft_plan * | plan, |
int | N, | ||
int | M | ||
) |
Creates a transform plan.
Definition at line 260 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.
nfsft_planstructure
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().
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 | ||
) |
Performes precomputation up to the next power of two with respect to a given bandwidth
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_PERSISTENT_DATA, nfsft_wisdom::gamma, gamma_al_all(), nfsft_wisdom::initialized, nfsft_wisdom::N_MAX, nfft_free(), nfft_malloc(), NFSFT_BREAK_EVEN, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NO_FAST_ALGORITHM, nfsft_wisdom::set, nfsft_wisdom::T_MAX, and wisdom.
Referenced by main().
void nfsft_forget | ( | void | ) |
Forgets all precomputed data.
Definition at line 579 of file nfsft.c.
References nfsft_wisdom::alpha, nfsft_wisdom::beta, nfsft_wisdom::gamma, nfsft_wisdom::initialized, nfsft_wisdom::N_MAX, nfft_free(), NFSFT_BREAK_EVEN, NFSFT_NO_DIRECT_ALGORITHM, NFSFT_NO_FAST_ALGORITHM, nfsft_wisdom::set, and wisdom.
Referenced by main().
void nfsft_finalize | ( | nfsft_plan * | plan | ) |
Destroys a plan.
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_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().
|
static |
void nfsft_trafo_direct | ( | nfsft_plan * | plan | ) |
|
static |
void nfsft_adjoint_direct | ( | nfsft_plan * | plan | ) |
void nfsft_trafo | ( | nfsft_plan * | plan | ) |
Executes a NFSFT, i.e. computes for
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_wisdom::initialized, nfsft_plan::MEASURE_TIME_t, nfsft_plan::N, nfsft_wisdom::N_MAX, 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, nfsft_wisdom::set, wisdom, and nfsft_plan::x.
Referenced by main().
void nfsft_adjoint | ( | nfsft_plan * | plan | ) |
Executes an adjoint NFSFT, i.e. computes for
Definition at line 1316 of file nfsft.c.
References c2e_transposed(), nfsft_plan::f, nfsft_plan::f_hat, nfsft_plan::flags, nfsft_wisdom::initialized, nfsft_plan::MEASURE_TIME_t, nfsft_plan::N, nfsft_wisdom::N_MAX, 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, nfsft_wisdom::set, wisdom, and nfsft_plan::x.
Referenced by main().
void nfsft_precompute_x | ( | nfsft_plan * | plan | ) |
bool nfsft_wisdom::initialized |
Indicates wether the structure has been initialized.
Definition at line 59 of file kernel/nfsft/api.h.
Referenced by nfsft_adjoint(), nfsft_forget(), nfsft_precompute(), and nfsft_trafo().
unsigned int nfsft_wisdom::flags |
Definition at line 60 of file kernel/nfsft/api.h.
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.
Referenced by nfsft_adjoint(), nfsft_forget(), nfsft_precompute(), and nfsft_trafo().
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.
Referenced by nfsft_precompute().
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_forget(), and nfsft_precompute().
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_forget(), and nfsft_precompute().
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_forget(), and nfsft_precompute().
double nfsft_wisdom::threshold |
The threshold /f$\kappa/f$.
Definition at line 91 of file kernel/nfsft/api.h.
fpt_set nfsft_wisdom::set |
Structure for discrete polynomial transform (DPT)
Definition at line 97 of file kernel/nfsft/api.h.
Referenced by nfsft_adjoint(), nfsft_forget(), nfsft_precompute(), and nfsft_trafo().
|
static |
The global wisdom structure for precomputed data.
wisdom.initialized
is set to false
and wisdom.flags
is set to 0U
.
Definition at line 90 of file nfsft.c.
Referenced by nfsft_adjoint(), nfsft_forget(), nfsft_precompute(), and nfsft_trafo().