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
C	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...
C	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
C	gaussian (R x, int der, const R *param)
C	multiquadric (R x, int der, const R *param)
C	inverse_multiquadric (R x, int der, const R *param)
C	logarithm (R x, int der, const R *param)
C	thinplate_spline (R x, int der, const R *param)
C	one_over_square (R x, int der, const R *param)
C	one_over_modulus (R x, int der, const R *param)
C	one_over_x (R x, int der, const R *param)
C	inverse_multiquadric3 (R x, int der, const R *param)
C	sinc_kernel (R x, int der, const R *param)
C	cosc (R x, int der, const R *param)
C	kcot (R x, int der, const R *param)
C	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
R	fastsum_plan_::eps_I
	inner boundary
R	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
R	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, R  xx, int  p, const R *  param, R  a, R  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,
		R	eps_I,
		R	eps_B
	)

initialization of fastsum plan

initialize fast summation plan

Parameters

ths	The pointer to a fastsum plan.
d	The dimension of the problem.
N_total	The number of source knots x.
M_total	The number of target knots y.
kernel	The kernel function.
param	The parameters for the kernel function.
flags	Fastsum flags.
nn	The expansion degree.
m	The cut-off parameter for the NFFT.
p	The degree of smoothness.
eps_I	The inner boundary.
eps_B	the 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

ths	The 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

ths	The 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

ths	The 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

ths	The 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.