Direct and fast summation (convolution) More...

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)

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 *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...

C	gaussian (R x, int der, const R *param)
	K(x)=exp(-x^2/c^2)

C	multiquadric (R x, int der, const R *param)
	K(x)=sqrt(x^2+c^2)

C	inverse_multiquadric (R x, int der, const R *param)
	K(x)=1/sqrt(x^2+c^2)

C	logarithm (R x, int der, const R *param)
	K(x)=log \|x\|.

C	thinplate_spline (R x, int der, const R *param)
	K(x) = x^2 log \|x\|.

C	one_over_square (R x, int der, const R *param)
	K(x) = 1/x^2.

C	one_over_modulus (R x, int der, const R *param)
	K(x) = 1/\|x\|.

C	one_over_x (R x, int der, const R *param)
	K(x) = 1/x.

C	inverse_multiquadric3 (R x, int der, const R *param)
	K(x) = 1/sqrt(x^2+c^2)^3.

C	sinc_kernel (R x, int der, const R *param)
	K(x) = sin(cx)/x.

C	cosc (R x, int der, const R *param)
	K(x) = cos(cx)/x.

C	kcot (R x, int der, const R *param)
	K(x) = cot(cx)

C	one_over_cube (R x, int der, const R *param)
	K(x) = 1/x^3.

C	log_sin (R x, int der, const R *param)
	K(x) = log(\|sin(cx)\|)

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

#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.

Referenced by fpt_init(), fpt_precompute(), fpt_transposed(), main(), nfsft_precompute(), and nfsoft_trafo().

Function Documentation

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.

References BasisPoly().

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.

Referenced by calc_SearchBox(), and SearchTree().

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

Parameters

ths	The pointer to a fastsum plan.
d	The dimension of the problem.
kernel	The kernel function.
param	The parameters for the kernel function.
flags	Fastsum flags.
nn	The expansion degree.
p	The degree of smoothness.
eps_I	The inner boundary.
eps_B	the outer boundary.

Definition at line 779 of file fastsum.c.

References fastsum_plan_::Ad, fastsum_plan_::Add, fastsum_plan_::b, fastsum_plan_::d, fastsum_plan_::eps_B, fastsum_plan_::eps_I, EXACT_NEARFIELD, fastsum_plan_::f_hat, fastsum_plan_::flags, fastsum_plan_::k, fastsum_plan_::kernel_param, max_i(), fastsum_plan_::n, one_over_x(), and fastsum_plan_::p.

Referenced by fastsum_init_guru().

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

ths	The pointer to a fastsum plan.
N_total	The number of source knots x.
nn_oversampled	The oversampled expansion degree for nfft.
m	The cut-off parameter for the NFFT.

Definition at line 887 of file fastsum.c.

References fastsum_plan_::alpha, fastsum_plan_::d, fastsum_plan_::eps_B, fastsum_plan_::eps_I, fastsum_plan_::f, fastsum_plan_::f_hat, FFT_OUT_OF_PLACE, FFTW_INIT, fastsum_plan_::flags, fastsum_plan_::n, fastsum_plan_::N_total, fastsum_plan_::permutation_x_alpha, PRE_PHI_HUT, PRE_PSI, and fastsum_plan_::x.

Referenced by fastsum_init_guru().

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

ths	The pointer to a fastsum plan.
M_total	The number of target knots y.
nn_oversampled	The oversampled expansion degree for nfft.
m	The cut-off parameter for the NFFT.

Definition at line 949 of file fastsum.c.

References fastsum_plan_::d, fastsum_plan_::f, fastsum_plan_::f_hat, FFT_OUT_OF_PLACE, FFTW_INIT, fastsum_plan_::M_total, fastsum_plan_::n, PRE_PHI_HUT, PRE_PSI, fastsum_plan_::x, and fastsum_plan_::y.

Referenced by 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.