NFFT  3.3.2alpha
Modules | Data Structures | Macros | Typedefs | Functions | Variables
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)
 

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 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 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
 
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 (fastsum_plan *ths)
 finalization of fastsum plan More...
 
void fastsum_exact (fastsum_plan *ths)
 direct computation of sums 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)
 
multiquadric (R x, int der, const R *param)
 
inverse_multiquadric (R x, int der, const R *param)
 
logarithm (R x, int der, const R *param)
 
thinplate_spline (R x, int der, const R *param)
 
one_over_square (R x, int der, const R *param)
 
one_over_modulus (R x, int der, const R *param)
 
one_over_x (R x, int der, const R *param)
 
inverse_multiquadric3 (R x, int der, const R *param)
 
sinc_kernel (R x, int der, const R *param)
 
cosc (R x, int der, const R *param)
 
kcot (R x, int der, const R *param)
 
one_over_cube (R x, int der, const R *param)
 

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

 
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
 
fastsum_plan_::MEASURE_TIME_t [8]
 Measured time for each step if MEASURE_TIME is set.
 

Detailed Description

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 51 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()

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 691 of file fastsum.c.

◆ fastsum_finalize()

void fastsum_finalize ( fastsum_plan ths)

finalization of fastsum plan

finalize plan

Parameters
thsThe pointer to a fastsum plan.

Definition at line 844 of file fastsum.c.

◆ fastsum_exact()

void fastsum_exact ( fastsum_plan ths)

direct computation of sums

direct summation

Parameters
thsThe pointer to a fastsum plan.

Definition at line 877 of file fastsum.c.

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

◆ fastsum_precompute()

void fastsum_precompute ( fastsum_plan ths)

precomputation for fastsum

sort source nodes, precompute Fourier coefficients, etc.

Parameters
thsThe pointer to a fastsum plan.

Definition at line 907 of file fastsum.c.

References fastsum_plan_::MEASURE_TIME_t.

◆ 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 1055 of file fastsum.c.

References fastsum_plan_::MEASURE_TIME_t.

Variable Documentation

◆ d

int fastsum_plan_::d

api

number of dimensions

Definition at line 76 of file fastsum.h.

Referenced by BuildBox().

◆ flags

unsigned fastsum_plan_::flags

flags precomp.

and approx.type

Definition at line 90 of file fastsum.h.

◆ pre_K

C* fastsum_plan_::pre_K

internal

DS_PRE - direct summation precomputed K(x_j-y_l)

Definition at line 95 of file fastsum.h.

◆ n

int fastsum_plan_::n

FS__ - fast summation.

expansion degree

Definition at line 98 of file fastsum.h.

◆ Ad

int fastsum_plan_::Ad

near field

number of spline knots for nearfield computation of regularized kernel

Definition at line 109 of file fastsum.h.