NFFT  3.5.3
Modules | Data Structures | Macros | Typedefs | Functions | Variables
Fast summation

Direct and fast summation (convolution) More...

Collaboration diagram for Fast summation:

Modules

 fastsum_matlab
 
 fastsum_test
 

Data Structures

struct  fastsum_plan_
 plan for fast summation algorithm More...
 

Macros

#define X(name)   NFFT(name)
 Include header for C99 complex datatype. More...
 
#define NF_KUB
 
#define EXACT_NEARFIELD   (1U<< 0)
 Constant symbols.
 
#define NEARFIELD_BOXES   (1U<< 1)
 
#define STORE_PERMUTATION_X_ALPHA   (1U<< 2)
 If this flag is set, and eps_I > 0.0 and NEARFIELD_BOXES is not set, then the vector permutation_x_alpha is stored.
 

Typedefs

typedef C(* kernel) (R, int, const R *)
 
typedef struct fastsum_plan_ fastsum_plan
 plan for fast summation algorithm
 

Functions

static int max_i (int a, int b)
 max
 
static R fak (int n)
 factorial
 
static R binom (int n, int m)
 binomial coefficient
 
static R BasisPoly (int m, int r, R xx)
 basis polynomial for regularized kernel
 
regkern (kernel k, R xx, int p, const R *param, R a, R b)
 regularized kernel with K_I arbitrary and K_B smooth to zero
 
static C regkern1 (kernel k, R xx, int p, const R *param, R a, R b)
 regularized kernel with K_I arbitrary and K_B periodized (used in 1D)
 
static C regkern3 (kernel k, R xx, int p, const R *param, R a, R b)
 regularized kernel for even kernels with K_I even and K_B mirrored More...
 
kubintkern (const R x, const C *Add, const int Ad, const R a)
 linear spline interpolation in near field with even kernels More...
 
static C kubintkern1 (const R x, const C *Add, const int Ad, const R a)
 cubic spline interpolation in near field with arbitrary kernels
 
static void quicksort (int d, int t, R *x, C *alpha, int *permutation_x_alpha, int N)
 quicksort algorithm for source knots and associated coefficients
 
static void BuildBox (fastsum_plan *ths)
 initialize box-based search data structures
 
static C calc_SearchBox (int d, R *y, R *x, C *alpha, int start, int end_lt, const C *Add, const int Ad, int p, R a, const kernel k, const R *param, const unsigned flags)
 inner computation function for box-based near field correction
 
static C SearchBox (R *y, fastsum_plan *ths)
 box-based near field correction
 
static void BuildTree (int d, int t, R *x, C *alpha, int *permutation_x_alpha, int N)
 recursive sort of source knots dimension by dimension to get tree structure
 
static C SearchTree (const int d, const int t, const R *x, const C *alpha, const R *xmin, const R *xmax, const int N, const kernel k, const R *param, const int Ad, const C *Add, const int p, const unsigned flags)
 fast search in tree of source knots for near field computation
 
static void fastsum_precompute_kernel (fastsum_plan *ths)
 
void fastsum_init_guru_kernel (fastsum_plan *ths, int d, kernel k, R *param, unsigned flags, int nn, int p, R eps_I, R eps_B)
 initialize node independent part of fast summation plan More...
 
void fastsum_init_guru_source_nodes (fastsum_plan *ths, int N_total, int nn_oversampled, int m)
 initialize source nodes dependent part of fast summation plan More...
 
void fastsum_init_guru_target_nodes (fastsum_plan *ths, int M_total, int nn_oversampled, int m)
 initialize target nodes dependent part of fast summation plan More...
 
void fastsum_init_guru (fastsum_plan *ths, int d, int N_total, int M_total, kernel k, R *param, unsigned flags, int nn, int m, int p, R eps_I, R eps_B)
 initialization of fastsum plan More...
 
void fastsum_finalize_source_nodes (fastsum_plan *ths)
 finalization of fastsum plan More...
 
void fastsum_finalize_target_nodes (fastsum_plan *ths)
 finalization of fastsum plan More...
 
void fastsum_finalize_kernel (fastsum_plan *ths)
 finalization of fastsum plan More...
 
void fastsum_finalize (fastsum_plan *ths)
 finalization of fastsum plan More...
 
void fastsum_exact (fastsum_plan *ths)
 direct computation of sums More...
 
void fastsum_precompute_source_nodes (fastsum_plan *ths)
 precomputation for fastsum More...
 
void fastsum_precompute_target_nodes (fastsum_plan *ths)
 precomputation for fastsum More...
 
void fastsum_precompute (fastsum_plan *ths)
 precomputation for fastsum More...
 
void fastsum_trafo (fastsum_plan *ths)
 fast NFFT-based summation More...
 
 fastsum_plan_::NFFT (plan) mv1
 source nfft plan

 
 fastsum_plan_::FFTW (plan) fft_plan
 
gaussian (R x, int der, const R *param)
 K(x)=exp(-x^2/c^2)
 
multiquadric (R x, int der, const R *param)
 K(x)=sqrt(x^2+c^2)
 
inverse_multiquadric (R x, int der, const R *param)
 K(x)=1/sqrt(x^2+c^2)
 
logarithm (R x, int der, const R *param)
 K(x)=log |x|.
 
thinplate_spline (R x, int der, const R *param)
 K(x) = x^2 log |x|.
 
one_over_square (R x, int der, const R *param)
 K(x) = 1/x^2.
 
one_over_modulus (R x, int der, const R *param)
 K(x) = 1/|x|.
 
one_over_x (R x, int der, const R *param)
 K(x) = 1/x.
 
inverse_multiquadric3 (R x, int der, const R *param)
 K(x) = 1/sqrt(x^2+c^2)^3.
 
sinc_kernel (R x, int der, const R *param)
 K(x) = sin(cx)/x.
 
cosc (R x, int der, const R *param)
 K(x) = cos(cx)/x.
 
kcot (R x, int der, const R *param)
 K(x) = cot(cx)
 
one_over_cube (R x, int der, const R *param)
 K(x) = 1/x^3.
 
log_sin (R x, int der, const R *param)
 K(x) = log(|sin(cx)|)
 
laplacian_rbf (R x, int der, const R *param)
 K(x) = exp(-|x|/c)
 

Variables

int fastsum_plan_::d
 api More...
 
int fastsum_plan_::N_total
 number of source knots

 
int fastsum_plan_::M_total
 number of target knots

 
C * fastsum_plan_::alpha
 source coefficients

 
C * fastsum_plan_::f
 target evaluations

 
R * fastsum_plan_::x
 source knots in d-ball with radius 1/4-eps_b/2
 
R * fastsum_plan_::y
 target knots in d-ball with radius 1/4-eps_b/2
 
kernel fastsum_plan_::k
 kernel function

 
R * fastsum_plan_::kernel_param
 parameters for kernel function

 
unsigned fastsum_plan_::flags
 flags precomp. More...
 
C * fastsum_plan_::pre_K
 internal More...
 
int fastsum_plan_::n
 FS__ - fast summation. More...
 
C * fastsum_plan_::b
 expansion coefficients

 
C * fastsum_plan_::f_hat
 Fourier coefficients of nfft plans.
 
int fastsum_plan_::p
 degree of smoothness of regularization
 
fastsum_plan_::eps_I
 inner boundary

 
fastsum_plan_::eps_B
 outer boundary

 
int fastsum_plan_::Ad
 near field More...
 
C * fastsum_plan_::Add
 spline values
 
int fastsum_plan_::box_count
 
int fastsum_plan_::box_count_per_dim
 
int * fastsum_plan_::box_offset
 
R * fastsum_plan_::box_x
 
C * fastsum_plan_::box_alpha
 
int * fastsum_plan_::permutation_x_alpha
 permutation vector of source nodes if STORE_PERMUTATION_X_ALPHA is set
 
fastsum_plan_::MEASURE_TIME_t [8]
 Measured time for each step if MEASURE_TIME is set.
 

Detailed Description

Direct and fast summation (convolution)

Computes the sums

\[ f(y_j) = \sum_{k=1}^N \alpha_k K(x_k-y_j),\quad j=1\dots M. \]

Macro Definition Documentation

◆ X

#define X (   name)    NFFT(name)

Include header for C99 complex datatype.

Include header for utils from NFFT3 library. Include header for NFFT3 library.

Definition at line 57 of file fastsum.h.

Function Documentation

◆ regkern3()

static C regkern3 ( kernel  k,
xx,
int  p,
const R *  param,
a,
b 
)
static

regularized kernel for even kernels with K_I even and K_B mirrored

regularized kernel for even kernels with K_I even and K_B mirrored smooth to K(1/2) (used in dD, d>1)

Definition at line 230 of file fastsum.c.

◆ kubintkern()

C kubintkern ( const R  x,
const C *  Add,
const int  Ad,
const R  a 
)

linear spline interpolation in near field with even kernels

cubic spline interpolation in near field with even kernels

Definition at line 318 of file fastsum.c.

◆ fastsum_init_guru_kernel()

void fastsum_init_guru_kernel ( fastsum_plan ths,
int  d,
kernel  k,
R *  param,
unsigned  flags,
int  nn,
int  p,
eps_I,
eps_B 
)

initialize node independent part of fast summation plan

Parameters
thsThe pointer to a fastsum plan.
dThe dimension of the problem.
kernelThe kernel function.
paramThe parameters for the kernel function.
flagsFastsum flags.
nnThe expansion degree.
pThe degree of smoothness.
eps_IThe inner boundary.
eps_Bthe outer boundary.

Definition at line 779 of file fastsum.c.

◆ fastsum_init_guru_source_nodes()

void fastsum_init_guru_source_nodes ( fastsum_plan ths,
int  N_total,
int  nn_oversampled,
int  m 
)

initialize source nodes dependent part of fast summation plan

Parameters
thsThe pointer to a fastsum plan.
N_totalThe number of source knots x.
nn_oversampledThe oversampled expansion degree for nfft.
mThe cut-off parameter for the NFFT.

Definition at line 887 of file fastsum.c.

References fastsum_plan_::d.

◆ fastsum_init_guru_target_nodes()

void fastsum_init_guru_target_nodes ( fastsum_plan ths,
int  M_total,
int  nn_oversampled,
int  m 
)

initialize target nodes dependent part of fast summation plan

Parameters
thsThe pointer to a fastsum plan.
M_totalThe number of target knots y.
nn_oversampledThe oversampled expansion degree for nfft.
mThe cut-off parameter for the NFFT.

Definition at line 955 of file fastsum.c.

References fastsum_plan_::d.

◆ fastsum_init_guru()

void fastsum_init_guru ( fastsum_plan ths,
int  d,
int  N_total,
int  M_total,
kernel  k,
R *  param,
unsigned  flags,
int  nn,
int  m,
int  p,
eps_I,
eps_B 
)

initialization of fastsum plan

initialize fast summation plan

Parameters
thsThe pointer to a fastsum plan.
dThe dimension of the problem.
N_totalThe number of source knots x.
M_totalThe number of target knots y.
kernelThe kernel function.
paramThe parameters for the kernel function.
flagsFastsum flags.
nnThe expansion degree.
mThe cut-off parameter for the NFFT.
pThe degree of smoothness.
eps_IThe inner boundary.
eps_Bthe outer boundary.

Definition at line 987 of file fastsum.c.

◆ fastsum_finalize_source_nodes()

void fastsum_finalize_source_nodes ( fastsum_plan ths)

finalization of fastsum plan

finalize source nodes dependent part of plan

Parameters
thsThe pointer to a fastsum plan.

Definition at line 996 of file fastsum.c.

Referenced by fastsum_finalize().

◆ fastsum_finalize_target_nodes()

void fastsum_finalize_target_nodes ( fastsum_plan ths)

finalization of fastsum plan

finalize target nodes dependent part of plan

Parameters
thsThe pointer to a fastsum plan.

Definition at line 1020 of file fastsum.c.

Referenced by fastsum_finalize().

◆ fastsum_finalize_kernel()

void fastsum_finalize_kernel ( fastsum_plan ths)

finalization of fastsum plan

finalize node independent part of plan

Parameters
thsThe pointer to a fastsum plan.

Definition at line 1029 of file fastsum.c.

References fastsum_plan_::eps_I, EXACT_NEARFIELD, and fastsum_plan_::flags.

Referenced by fastsum_finalize().

◆ fastsum_finalize()

void fastsum_finalize ( fastsum_plan ths)

finalization of fastsum plan

finalize plan

Parameters
thsThe pointer to a fastsum plan.

Definition at line 1048 of file fastsum.c.

References fastsum_finalize_kernel(), fastsum_finalize_source_nodes(), and fastsum_finalize_target_nodes().

◆ fastsum_exact()

void fastsum_exact ( fastsum_plan ths)

direct computation of sums

direct summation

Parameters
thsThe pointer to a fastsum plan.

Definition at line 1056 of file fastsum.c.

References fastsum_plan_::f, and fastsum_plan_::M_total.

◆ fastsum_precompute_source_nodes()

void fastsum_precompute_source_nodes ( fastsum_plan ths)

precomputation for fastsum

sort source nodes, precompute nfft source plan.

Parameters
thsThe pointer to a fastsum plan.

Definition at line 1086 of file fastsum.c.

References fastsum_plan_::MEASURE_TIME_t.

Referenced by fastsum_precompute().

◆ fastsum_precompute_target_nodes()

void fastsum_precompute_target_nodes ( fastsum_plan ths)

precomputation for fastsum

precompute nfft target plan.

Parameters
thsThe pointer to a fastsum plan.

Definition at line 1141 of file fastsum.c.

References fastsum_plan_::MEASURE_TIME_t.

Referenced by fastsum_precompute().

◆ fastsum_precompute()

void fastsum_precompute ( fastsum_plan ths)

precomputation for fastsum

sort source nodes, precompute nfft plans etc.

Parameters
thsThe pointer to a fastsum plan.

Definition at line 1173 of file fastsum.c.

References fastsum_precompute_source_nodes(), and fastsum_precompute_target_nodes().

◆ fastsum_trafo()

void fastsum_trafo ( fastsum_plan ths)

fast NFFT-based summation

fast NFFT-based summation algorithm

Parameters
thsThe pointer to a fastsum plan.

Definition at line 1180 of file fastsum.c.

References fastsum_plan_::MEASURE_TIME_t.

Variable Documentation

◆ d

int fastsum_plan_::d

api

number of dimensions

Definition at line 86 of file fastsum.h.

Referenced by BuildBox(), fastsum_init_guru_source_nodes(), and fastsum_init_guru_target_nodes().

◆ flags

unsigned fastsum_plan_::flags

flags precomp.

and approx.type

Definition at line 100 of file fastsum.h.

Referenced by fastsum_finalize_kernel().

◆ pre_K

C* fastsum_plan_::pre_K

internal

DS_PRE - direct summation precomputed K(x_j-y_l)

Definition at line 105 of file fastsum.h.

◆ n

int fastsum_plan_::n

FS__ - fast summation.

expansion degree

Definition at line 108 of file fastsum.h.

◆ Ad

int fastsum_plan_::Ad

near field

number of spline knots for nearfield computation of regularized kernel

Definition at line 120 of file fastsum.h.