NFFT 3.5.3alpha
Macros | Functions
fpt.c File Reference

Implementation file for the FPT module. More...

#include "config.h"
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include "nfft3.h"
#include "infft.h"
#include "fpt.h"
Include dependency graph for fpt.c:

Go to the source code of this file.

Macros

#define K_START_TILDE(x, y)   (MAX(MIN(x,y-2),0))
 If defined, perform critical computations in three-term recurrence always in long double instead of using adaptive version that starts in double and switches to long double if required.
 
#define K_END_TILDE(x, y)   MIN(x,y-1)
 Maximum degree at top of a cascade.
 
#define FIRST_L(x, y)   (LRINT(floor((x)/(double)y)))
 Index of first block of four functions at level.
 
#define LAST_L(x, y)   (LRINT(ceil(((x)+1)/(double)y))-1)
 Index of last block of four functions at level.
 
#define N_TILDE(y)   (y-1)
 
#define IS_SYMMETRIC(x, y, z)   (x >= ((y-1.0)/z))
 
#define FPT_BREAK_EVEN   4
 
#define ABUVXPWY_SYMMETRIC(NAME, S1, S2)
 
#define ABUVXPWY_SYMMETRIC_1(NAME, S1)
 
#define ABUVXPWY_SYMMETRIC_2(NAME, S1)
 
#define FPT_DO_STEP(NAME, M1_FUNCTION, M2_FUNCTION)
 
#define FPT_DO_STEP_TRANSPOSED(NAME, M1_FUNCTION, M2_FUNCTION)
 

Functions

static void abuvxpwy (double a, double b, double _Complex *u, double _Complex *x, double *v, double _Complex *y, double *w, int n)
 
static void abuvxpwy_symmetric1 (double a, double b, double _Complex *u, double _Complex *x, double *v, double _Complex *y, double *w, int n)
 
static void abuvxpwy_symmetric2 (double a, double b, double _Complex *u, double _Complex *x, double *v, double _Complex *y, double *w, int n)
 
static void abuvxpwy_symmetric1_1 (double a, double b, double _Complex *u, double _Complex *x, double *v, double _Complex *y, int n, double *xx)
 
static void abuvxpwy_symmetric1_2 (double a, double b, double _Complex *u, double _Complex *x, double *v, double _Complex *y, int n, double *xx)
 
static void abuvxpwy_symmetric2_1 (double a, double b, double _Complex *u, double _Complex *x, double _Complex *y, double *w, int n, double *xx)
 
static void abuvxpwy_symmetric2_2 (double a, double b, double _Complex *u, double _Complex *x, double _Complex *y, double *w, int n, double *xx)
 
static void auvxpwy (double a, double _Complex *u, double _Complex *x, double *v, double _Complex *y, double *w, int n)
 
static void auvxpwy_symmetric (double a, double _Complex *u, double _Complex *x, double *v, double _Complex *y, double *w, int n)
 
static void auvxpwy_symmetric_1 (double a, double _Complex *u, double _Complex *x, double *v, double _Complex *y, double *w, int n, double *xx)
 
static void auvxpwy_symmetric_2 (double a, double _Complex *u, double _Complex *x, double *v, double _Complex *y, double *w, int n, double *xx)
 
static void fpt_do_step (double _Complex *a, double _Complex *b, double *a11, double *a12, double *a21, double *a22, double g, int tau, fpt_set set)
 
static void fpt_do_step_symmetric (double _Complex *a, double _Complex *b, double *a11, double *a12, double *a21, double *a22, double g, int tau, fpt_set set)
 
static void fpt_do_step_symmetric_u (double _Complex *a, double _Complex *b, double *a11, double *a12, double *a21, double *a22, double *x, double gam, int tau, fpt_set set)
 
static void fpt_do_step_symmetric_l (double _Complex *a, double _Complex *b, double *a11, double *a12, double *a21, double *a22, double *x, double gam, int tau, fpt_set set)
 
static void fpt_do_step_t (double _Complex *a, double _Complex *b, double *a11, double *a12, double *a21, double *a22, double g, int tau, fpt_set set)
 
static void fpt_do_step_t_symmetric (double _Complex *a, double _Complex *b, double *a11, double *a12, double *a21, double *a22, double g, int tau, fpt_set set)
 
static void fpt_do_step_t_symmetric_u (double _Complex *a, double _Complex *b, double *a11, double *a12, double *x, double gam, int tau, fpt_set set)
 
static void fpt_do_step_t_symmetric_l (double _Complex *a, double _Complex *b, double *a21, double *a22, double *x, double gam, int tau, fpt_set set)
 
static void eval_clenshaw (const double *x, double *y, int size, int k, const double *alpha, const double *beta, const double *gam)
 
static void eval_clenshaw2 (const double *x, double *z, double *y, int size1, int size, int k, const double *alpha, const double *beta, const double *gam)
 
static int eval_clenshaw_thresh2 (const double *x, double *z, double *y, int size, int k, const double *alpha, const double *beta, const double *gam, const double threshold)
 
static void eval_sum_clenshaw_fast (const int N, const int M, const double _Complex *a, const double *x, double _Complex *y, const double *alpha, const double *beta, const double *gam, const double lambda)
 
static void eval_sum_clenshaw_transposed (int N, int M, double _Complex *a, double *x, double _Complex *y, double _Complex *temp, double *alpha, double *beta, double *gam, double lambda)
 Clenshaw algorithm.
 
static void eval_sum_clenshaw_transposed_ld (int N, int M, double _Complex *a, double *x, double _Complex *y, double _Complex *temp, double *alpha, double *beta, double *gam, double lambda)
 
fpt_set fpt_init (const int M, const int t, const unsigned int flags)
 
void fpt_precompute_1 (fpt_set set, const int m, int k_start)
 
void fpt_precompute_2 (fpt_set set, const int m, double *alpha, double *beta, double *gam, int k_start, const double threshold)
 
void fpt_precompute (fpt_set set, const int m, double *alpha, double *beta, double *gam, int k_start, const double threshold)
 
void fpt_trafo_direct (fpt_set set, const int m, const double _Complex *x, double _Complex *y, const int k_end, const unsigned int flags)
 
void fpt_trafo (fpt_set set, const int m, const double _Complex *x, double _Complex *y, const int k_end, const unsigned int flags)
 
void fpt_transposed_direct (fpt_set set, const int m, double _Complex *x, double _Complex *y, const int k_end, const unsigned int flags)
 
void fpt_transposed (fpt_set set, const int m, double _Complex *x, double _Complex *y, const int k_end, const unsigned int flags)
 
void fpt_finalize (fpt_set set)
 

Detailed Description

Implementation file for the FPT module.

Author
Jens Keiner

Definition in file fpt.c.

Macro Definition Documentation

◆ K_START_TILDE

#define K_START_TILDE (   x,
 
)    (MAX(MIN(x,y-2),0))

If defined, perform critical computations in three-term recurrence always in long double instead of using adaptive version that starts in double and switches to long double if required.

Minimum degree at top of a cascade

Definition at line 48 of file fpt.c.

◆ K_END_TILDE

#define K_END_TILDE (   x,
 
)    MIN(x,y-1)

Maximum degree at top of a cascade.

Definition at line 51 of file fpt.c.

◆ FIRST_L

#define FIRST_L (   x,
 
)    (LRINT(floor((x)/(double)y)))

Index of first block of four functions at level.

Definition at line 54 of file fpt.c.

◆ LAST_L

#define LAST_L (   x,
 
)    (LRINT(ceil(((x)+1)/(double)y))-1)

Index of last block of four functions at level.

Definition at line 57 of file fpt.c.

◆ N_TILDE

#define N_TILDE (   y)    (y-1)

Definition at line 59 of file fpt.c.

◆ IS_SYMMETRIC

#define IS_SYMMETRIC (   x,
  y,
 
)    (x >= ((y-1.0)/z))

Definition at line 61 of file fpt.c.

◆ FPT_BREAK_EVEN

#define FPT_BREAK_EVEN   4

Definition at line 63 of file fpt.c.

◆ ABUVXPWY_SYMMETRIC

#define ABUVXPWY_SYMMETRIC (   NAME,
  S1,
  S2 
)
Value:
static inline void NAME(double a, double b, double _Complex* u, double _Complex* x, \
double* v, double _Complex* y, double* w, int n) \
{ \
const int n2 = n>>1; \
int l; double _Complex *u_ptr = u, *x_ptr = x, *y_ptr = y; \
double *v_ptr = v, *w_ptr = w; \
for (l = 0; l < n2; l++) \
*u_ptr++ = a * (b * (*v_ptr++) * (*x_ptr++) + (*w_ptr++) * (*y_ptr++)); \
v_ptr--; w_ptr--; \
for (l = 0; l < n2; l++) \
*u_ptr++ = a * (b * S1 * (*v_ptr--) * (*x_ptr++) + S2 * (*w_ptr--) * (*y_ptr++)); \
}

Definition at line 77 of file fpt.c.

◆ ABUVXPWY_SYMMETRIC_1

#define ABUVXPWY_SYMMETRIC_1 (   NAME,
  S1 
)
Value:
static inline void NAME(double a, double b, double _Complex* u, double _Complex* x, \
double* v, double _Complex* y, int n, double *xx) \
{ \
const int n2 = n>>1; \
int l; double _Complex *u_ptr = u, *x_ptr = x, *y_ptr = y; \
double *v_ptr = v, *xx_ptr = xx; \
for (l = 0; l < n2; l++, v_ptr++) \
*u_ptr++ = a * (b * (*v_ptr) * (*x_ptr++) + ((*v_ptr)*(1.0+*xx_ptr++)) * (*y_ptr++)); \
v_ptr--; \
for (l = 0; l < n2; l++, v_ptr--) \
*u_ptr++ = a * (b * S1 * (*v_ptr) * (*x_ptr++) + (S1 * (*v_ptr) * (1.0+*xx_ptr++)) * (*y_ptr++)); \
}

Definition at line 94 of file fpt.c.

◆ ABUVXPWY_SYMMETRIC_2

#define ABUVXPWY_SYMMETRIC_2 (   NAME,
  S1 
)
Value:
static inline void NAME(double a, double b, double _Complex* u, double _Complex* x, \
double _Complex* y, double* w, int n, double *xx) \
{ \
const int n2 = n>>1; \
int l; double _Complex *u_ptr = u, *x_ptr = x, *y_ptr = y; \
double *w_ptr = w, *xx_ptr = xx; \
for (l = 0; l < n2; l++, w_ptr++) \
*u_ptr++ = a * (b * (*w_ptr/(1.0+*xx_ptr++)) * (*x_ptr++) + (*w_ptr) * (*y_ptr++)); \
w_ptr--; \
for (l = 0; l < n2; l++, w_ptr--) \
*u_ptr++ = a * (b * (S1 * (*w_ptr)/(1.0+*xx_ptr++) ) * (*x_ptr++) + S1 * (*w_ptr) * (*y_ptr++)); \
}

Definition at line 111 of file fpt.c.

◆ FPT_DO_STEP

#define FPT_DO_STEP (   NAME,
  M1_FUNCTION,
  M2_FUNCTION 
)

Definition at line 180 of file fpt.c.

◆ FPT_DO_STEP_TRANSPOSED

#define FPT_DO_STEP_TRANSPOSED (   NAME,
  M1_FUNCTION,
  M2_FUNCTION 
)
Value:
static inline void NAME(double _Complex *a, double _Complex *b, double *a11, \
double *a12, double *a21, double *a22, double g, int tau, fpt_set set) \
{ \
\
int length = 1<<(tau+1); \
\
double norm = 1.0/(length<<1); \
\
/* Compute function values from Chebyshev-coefficients using a DCT-III. */ \
fftw_execute_r2r(set->plans_dct3[tau-1],(double*)a,(double*)a); \
fftw_execute_r2r(set->plans_dct3[tau-1],(double*)b,(double*)b); \
\
/* Perform matrix multiplication. */ \
M1_FUNCTION(norm,g,set->z,a,a11,b,a21,length); \
M2_FUNCTION(norm,g,b,a,a12,b,a22,length); \
memcpy(a,set->z,length*sizeof(double _Complex)); \
\
/* Compute Chebyshev-coefficients using a DCT-II. */ \
fftw_execute_r2r(set->plans_dct2[tau-1],(double*)a,(double*)a); \
fftw_execute_r2r(set->plans_dct2[tau-1],(double*)b,(double*)b); \
}
Holds data for a set of cascade summations.
Definition fpt.h:66

Definition at line 335 of file fpt.c.

Function Documentation

◆ abuvxpwy()

static void abuvxpwy ( double  a,
double  b,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
double *  w,
int  n 
)
inlinestatic

Definition at line 68 of file fpt.c.

◆ abuvxpwy_symmetric1()

static void abuvxpwy_symmetric1 ( double  a,
double  b,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
double *  w,
int  n 
)
inlinestatic

Definition at line 91 of file fpt.c.

◆ abuvxpwy_symmetric2()

static void abuvxpwy_symmetric2 ( double  a,
double  b,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
double *  w,
int  n 
)
inlinestatic

Definition at line 92 of file fpt.c.

◆ abuvxpwy_symmetric1_1()

static void abuvxpwy_symmetric1_1 ( double  a,
double  b,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
int  n,
double *  xx 
)
inlinestatic

Definition at line 108 of file fpt.c.

◆ abuvxpwy_symmetric1_2()

static void abuvxpwy_symmetric1_2 ( double  a,
double  b,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
int  n,
double *  xx 
)
inlinestatic

Definition at line 109 of file fpt.c.

◆ abuvxpwy_symmetric2_1()

static void abuvxpwy_symmetric2_1 ( double  a,
double  b,
double _Complex *  u,
double _Complex *  x,
double _Complex *  y,
double *  w,
int  n,
double *  xx 
)
inlinestatic

Definition at line 125 of file fpt.c.

◆ abuvxpwy_symmetric2_2()

static void abuvxpwy_symmetric2_2 ( double  a,
double  b,
double _Complex *  u,
double _Complex *  x,
double _Complex *  y,
double *  w,
int  n,
double *  xx 
)
inlinestatic

Definition at line 126 of file fpt.c.

◆ auvxpwy()

static void auvxpwy ( double  a,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
double *  w,
int  n 
)
inlinestatic

Definition at line 128 of file fpt.c.

◆ auvxpwy_symmetric()

static void auvxpwy_symmetric ( double  a,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
double *  w,
int  n 
)
inlinestatic

Definition at line 138 of file fpt.c.

◆ auvxpwy_symmetric_1()

static void auvxpwy_symmetric_1 ( double  a,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
double *  w,
int  n,
double *  xx 
)
inlinestatic

Definition at line 152 of file fpt.c.

◆ auvxpwy_symmetric_2()

static void auvxpwy_symmetric_2 ( double  a,
double _Complex *  u,
double _Complex *  x,
double *  v,
double _Complex *  y,
double *  w,
int  n,
double *  xx 
)
inlinestatic

Definition at line 166 of file fpt.c.

◆ fpt_do_step()

static void fpt_do_step ( double _Complex *  a,
double _Complex *  b,
double *  a11,
double *  a12,
double *  a21,
double *  a22,
double  g,
int  tau,
fpt_set  set 
)
inlinestatic

Definition at line 229 of file fpt.c.

◆ fpt_do_step_symmetric()

static void fpt_do_step_symmetric ( double _Complex *  a,
double _Complex *  b,
double *  a11,
double *  a12,
double *  a21,
double *  a22,
double  g,
int  tau,
fpt_set  set 
)
inlinestatic

Definition at line 230 of file fpt.c.

◆ fpt_do_step_symmetric_u()

static void fpt_do_step_symmetric_u ( double _Complex *  a,
double _Complex *  b,
double *  a11,
double *  a12,
double *  a21,
double *  a22,
double *  x,
double  gam,
int  tau,
fpt_set  set 
)
inlinestatic

Definition at line 234 of file fpt.c.

◆ fpt_do_step_symmetric_l()

static void fpt_do_step_symmetric_l ( double _Complex *  a,
double _Complex *  b,
double *  a11,
double *  a12,
double *  a21,
double *  a22,
double *  x,
double  gam,
int  tau,
fpt_set  set 
)
inlinestatic

Definition at line 285 of file fpt.c.

◆ fpt_do_step_t()

static void fpt_do_step_t ( double _Complex *  a,
double _Complex *  b,
double *  a11,
double *  a12,
double *  a21,
double *  a22,
double  g,
int  tau,
fpt_set  set 
)
inlinestatic

Definition at line 358 of file fpt.c.

◆ fpt_do_step_t_symmetric()

static void fpt_do_step_t_symmetric ( double _Complex *  a,
double _Complex *  b,
double *  a11,
double *  a12,
double *  a21,
double *  a22,
double  g,
int  tau,
fpt_set  set 
)
inlinestatic

Definition at line 359 of file fpt.c.

◆ fpt_do_step_t_symmetric_u()

static void fpt_do_step_t_symmetric_u ( double _Complex *  a,
double _Complex *  b,
double *  a11,
double *  a12,
double *  x,
double  gam,
int  tau,
fpt_set  set 
)
inlinestatic

Definition at line 364 of file fpt.c.

◆ fpt_do_step_t_symmetric_l()

static void fpt_do_step_t_symmetric_l ( double _Complex *  a,
double _Complex *  b,
double *  a21,
double *  a22,
double *  x,
double  gam,
int  tau,
fpt_set  set 
)
inlinestatic

Definition at line 387 of file fpt.c.

◆ eval_clenshaw()

static void eval_clenshaw ( const double *  x,
double *  y,
int  size,
int  k,
const double *  alpha,
const double *  beta,
const double *  gam 
)
static

Definition at line 411 of file fpt.c.

◆ eval_clenshaw2()

static void eval_clenshaw2 ( const double *  x,
double *  z,
double *  y,
int  size1,
int  size,
int  k,
const double *  alpha,
const double *  beta,
const double *  gam 
)
static

Definition at line 490 of file fpt.c.

◆ eval_clenshaw_thresh2()

static int eval_clenshaw_thresh2 ( const double *  x,
double *  z,
double *  y,
int  size,
int  k,
const double *  alpha,
const double *  beta,
const double *  gam,
const double  threshold 
)
static

Definition at line 546 of file fpt.c.

◆ eval_sum_clenshaw_fast()

static void eval_sum_clenshaw_fast ( const int  N,
const int  M,
const double _Complex *  a,
const double *  x,
double _Complex *  y,
const double *  alpha,
const double *  beta,
const double *  gam,
const double  lambda 
)
inlinestatic

Definition at line 637 of file fpt.c.

◆ eval_sum_clenshaw_transposed()

static void eval_sum_clenshaw_transposed ( int  N,
int  M,
double _Complex *  a,
double *  x,
double _Complex *  y,
double _Complex *  temp,
double *  alpha,
double *  beta,
double *  gam,
double  lambda 
)
static

Clenshaw algorithm.

Evaluates a sum of real-valued functions $P_k : \mathbb{R} \rightarrow
\mathbb{R}$

\[
  f(x) = \sum_{k=0}^N a_k P_k(x) \quad (N \in \mathbb{N}_0)
\]

obeying a three-term recurrence relation

\[
  P_{k+1}(x) = (alpha_k * x + beta_k)*P_{k}(x) + gamma_k P_{k-1}(x) \quad
  (alpha_k, beta_k, gamma_k \in \mathbb{R},\; k \ge 0)
\]

with initial conditions $P_{-1}(x) := 0$, $P_0(x) := \lambda$ for given double _Complex coefficients $\left(a_k\right)_{k=0}^N \in
\mathbb{C}^{N+1}$ at given nodes $\left(x_j\right)_{j=0}^M \in
\mathbb{R}^{M+1}$, $M \in \mathbb{N}_0$.

Definition at line 717 of file fpt.c.

◆ eval_sum_clenshaw_transposed_ld()

static void eval_sum_clenshaw_transposed_ld ( int  N,
int  M,
double _Complex *  a,
double *  x,
double _Complex *  y,
double _Complex *  temp,
double *  alpha,
double *  beta,
double *  gam,
double  lambda 
)
static

Definition at line 759 of file fpt.c.

◆ fpt_init()

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

Definition at line 795 of file fpt.c.

◆ fpt_precompute_1()

void fpt_precompute_1 ( fpt_set  set,
const int  m,
int  k_start 
)

Definition at line 942 of file fpt.c.

◆ fpt_precompute_2()

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

Definition at line 1028 of file fpt.c.

◆ fpt_precompute()

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

Definition at line 1307 of file fpt.c.

◆ fpt_trafo_direct()

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

Definition at line 1314 of file fpt.c.

◆ fpt_trafo()

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

Definition at line 1375 of file fpt.c.

◆ fpt_transposed_direct()

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

Definition at line 1683 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 
)

Definition at line 1740 of file fpt.c.

◆ fpt_finalize()

void fpt_finalize ( fpt_set  set)

Definition at line 1979 of file fpt.c.