NFFT  3.5.3
Macros | Functions | Variables
FPT - Fast polynomial transform

This module implements fast polynomial transforms. More...

Macros

#define FPT_NO_FAST_ALGORITHM   (1U << 2)
 If set, TODO complete comment.
 
#define FPT_NO_DIRECT_ALGORITHM   (1U << 3)
 If set, TODO complete comment.
 
#define FPT_NO_STABILIZATION   (1U << 0)
 If set, no stabilization will be used.
 
#define FPT_PERSISTENT_DATA   (1U << 4)
 If set, TODO complete comment.
 
#define FPT_FUNCTION_VALUES   (1U << 5)
 If set, the output are function values at Chebyshev nodes rather than Chebyshev coefficients.
 
#define FPT_AL_SYMMETRY   (1U << 6)
 If set, TODO complete comment.
 

Functions

fpt_set fpt_init (const int M, const int t, const unsigned int flags)
 
void fpt_precompute (fpt_set set, const int m, double *alpha, double *beta, double *gam, int k_start, const double threshold)
 
void fpt_transposed (fpt_set set, const int m, double _Complex *x, double _Complex *y, const int k_end, const unsigned int flags)
 

Variables

*We expand this macro for each supported precision * X
 

Detailed Description

This module implements fast polynomial transforms.

In the following, we abbreviate the term "fast polynomial transforms" by FPT.

Let $\alpha_n,\;\beta_n,\;\gamma_n,\;n=0,\dots,N$ be given recursion coefficients of the polynomials $P_n$ defined by $P_{-1}(x) = 0$, $P_{0}(x) = 1$ and

\[ P_n(x) = (\alpha_nx+\beta_n) P_{n-1}(x) + \gamma_n P_{n-2}(x) ,\qquad n=1,2,\dots \]

for $x\in[-1,1]$. The Chebyshev polnyomials of the first kind are defined by

\[ T_n(x) = \cos(n\, \arccos x). \]

Let $f\colon [-1,1]\to\mathbb R$ be a polynomial of degree $N\in\mathbb N$. The FPT transforms the polynomial coefficients $[x_n]_{n=0..N}$ from

\[ f = \sum_{n=0}^N x_n P_n \]

into Chebyshev coefficients $[y_n]_{n=0..N}$ from

\[ f = \sum_{n=0}^N y_n T_n. \]

Function Documentation

◆ fpt_init()

fpt_set fpt_init ( const int  M,
const int  t,
const unsigned int  flags 
)

Initializes a set of precomputed data for DPT transforms of equal length.

  • M The maximum DPT transform index $M \in \mathbb{N}_0$. The individual transforms are addressed by and index number $m \in \mathbb{N}_0$ with range $m = 0,\ldots,M$. The total number of transforms is therefore $M+1$.
  • t The exponent $t \in \mathbb{N}, t \ge 2$ of the transform length $N = 2^t \in \mathbb{N}, N \ge 4$
  • flags A bitwise combination of the flags FPT_NO_STABILIZATION,
Author
Jens Keiner

Definition at line 795 of file fpt.c.

References fpt_set_s_::flags, fpt_set_s_::M, fpt_set_s_::N, fpt_set_s_::t, and X.

Referenced by nfsft_precompute().

◆ fpt_precompute()

void fpt_precompute ( fpt_set  set,
const int  m,
double *  alpha,
double *  beta,
double *  gam,
int  k_start,
const double  threshold 
)

Computes the data required for a single DPT transform.

  • set The set of DPT transform data where the computed data will be stored.
  • m The transform index $m \in \mathbb{N}, 0 \le m \le M$.
  • alpha The three-term recurrence coefficients $\alpha_k \in \mathbb{R}$ for $k=0,\ldots,N$ such that alpha[k] $=\alpha_k$.
  • beta The three-term recurrence coefficients $\beta_k \in \mathbb{R}$ for $k=0,\ldots,N$ such that beta[k] $=\beta_k$.
  • gamma The three-term recurrence coefficients $\gamma_k \in \mathbb{R}$ for $k=0,\ldots,N$ such that gamma[k] $=\gamma_k$.
  • k_start The index $k_{\text{start}} \in \mathbb{N}_0, 0 \le k_{\text{start}} \le N$
  • threshold The threshold $\kappa \in \mathbb{R}, \kappa > 0$.
Author
Jens Keiner

Definition at line 1307 of file fpt.c.

◆ fpt_transposed()

void fpt_transposed ( fpt_set  set,
const int  m,
double _Complex *  x,
double _Complex *  y,
const int  k_end,
const unsigned int  flags 
)

Computes a single DPT transform.

  • set
  • m
  • x
  • y
  • k_end
  • flags

Definition at line 1740 of file fpt.c.

Variable Documentation

◆ X

void X

Computes a single DPT transform.

  • set
  • m
  • x
  • y
  • k_end
  • flags

Initialisation of a transform plan, guru.

  • ths The pointer to a nfft plan
  • d The dimension
  • N The multi bandwidth
  • M The number of nodes
  • n The oversampled multi bandwidth
  • m The spatial cut-off
  • flags NFFT flags to use
  • fftw_flags_off FFTW flags to use
Author
Stefan Kunis, Daniel Potts

Definition at line 94 of file nfft3.h.

Referenced by fpt_init(), nfsft_precompute(), nfsoft_adjoint(), and nfsoft_trafo().