This module implements fast polynomial transforms. More...

Macros
#define	FPT_NO_FAST_ALGORITHM (1U << 2)
	If set, TODO complete comment.
#define	FPT_NO_DIRECT_ALGORITHM (1U << 3)
	If set, TODO complete comment.
#define	FPT_NO_STABILIZATION (1U << 0)
	If set, no stabilization will be used.
#define	FPT_PERSISTENT_DATA (1U << 4)
	If set, TODO complete comment.
#define	FPT_FUNCTION_VALUES (1U << 5)
	If set, the output are function values at Chebyshev nodes rather than Chebyshev coefficients.
#define	FPT_AL_SYMMETRY (1U << 6)
	If set, TODO complete comment.

Functions
fpt_set	fpt_init (const int M, const int t, const unsigned int flags)
void	fpt_precompute (fpt_set set, const int m, double alpha, double beta, double *gam, int k_start, const double threshold)
void	fpt_transposed (fpt_set set, const int m, double _Complex x, double _Complex y, const int k_end, const unsigned int flags)

Detailed Description

This module implements fast polynomial transforms.

In the following, we abbreviate the term "fast polynomial transforms" by FPT.

Let $\alpha_n,\;\beta_n,\;\gamma_n,\;n=0,\dots,N$ be given recursion coefficients of the polynomials $P_n$ defined by $P_{-1}(x) = 0$ , $P_{0}(x) = 1$ and

$\‍[ P_n(x) = (\alpha_nx+\beta_n) P_{n-1}(x) + \gamma_n P_{n-2}(x) ,\qquad n=1,2,\dots \‍]$

for $x\in[-1,1]$ . The Chebyshev polnyomials of the first kind are defined by

$\‍[ T_n(x) = \cos(n\, \arccos x). \‍]$

Let $f\colon [-1,1]\to\mathbb R$ be a polynomial of degree $N\in\mathbb N$ . The FPT transforms the polynomial coefficients $[x_n]_{n=0..N}$ from

$\‍[ f = \sum_{n=0}^N x_n P_n \‍]$

into Chebyshev coefficients $[y_n]_{n=0..N}$ from

$\‍[ f = \sum_{n=0}^N y_n T_n. \‍]$

Macro Definition Documentation

◆ FPT_NO_FAST_ALGORITHM

#define FPT_NO_FAST_ALGORITHM (1U << 2)

If set, TODO complete comment.

Definition at line 638 of file nfft3.h.

Referenced by fpt_init(), and fpt_transposed().

◆ FPT_NO_DIRECT_ALGORITHM

#define FPT_NO_DIRECT_ALGORITHM (1U << 3)

If set, TODO complete comment.

Definition at line 639 of file nfft3.h.

Referenced by fpt_init().

◆ FPT_NO_STABILIZATION

#define FPT_NO_STABILIZATION (1U << 0)

If set, no stabilization will be used.

Definition at line 637 of file nfft3.h.

◆ FPT_PERSISTENT_DATA

#define FPT_PERSISTENT_DATA (1U << 4)

If set, TODO complete comment.

Definition at line 640 of file nfft3.h.

Referenced by nfsft_precompute().

◆ FPT_FUNCTION_VALUES

#define FPT_FUNCTION_VALUES (1U << 5)

If set, the output are function values at Chebyshev nodes rather than Chebyshev coefficients.

Definition at line 644 of file nfft3.h.

Referenced by fpt_transposed().

◆ FPT_AL_SYMMETRY

#define FPT_AL_SYMMETRY (1U << 6)

If set, TODO complete comment.

Definition at line 645 of file nfft3.h.

Referenced by fpt_transposed(), and nfsft_precompute().

Function Documentation

◆ fpt_init()

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

extern

Initializes a set of precomputed data for DPT transforms of equal length.

M The maximum DPT transform index $M \in \mathbb{N}_0$ . The individual transforms are addressed by and index number $m \in \mathbb{N}_0$ with range $m = 0,\ldots,M$ . The total number of transforms is therefore .
t The exponent $t \in \mathbb{N}, t \ge 2$ of the transform length $N = 2^t \in \mathbb{N}, N \ge 4$
flags A bitwise combination of the flags FPT_NO_STABILIZATION,

Author: Jens Keiner

Definition at line 795 of file fpt.c.

References fpt_data_::_alpha, fpt_data_::_beta, fpt_data_::_gamma, fpt_set_s_::dpt, fpt_set_s_::flags, FPT_NO_DIRECT_ALGORITHM, FPT_NO_FAST_ALGORITHM, fpt_set_s_::kinds, fpt_set_s_::kindsr, fpt_set_s_::M, fpt_set_s_::N, nfft_free(), nfft_malloc(), fpt_set_s_::plans_dct2, fpt_set_s_::plans_dct3, fpt_data_::steps, fpt_set_s_::t, X, and fpt_set_s_::xcvecs.

Referenced by main(), and nfsft_precompute().

◆ fpt_precompute()

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

extern

Computes the data required for a single DPT transform.

set The set of DPT transform data where the computed data will be stored.
m The transform index $m \in \mathbb{N}, 0 \le m \le M$ .
alpha The three-term recurrence coefficients $\alpha_k \in \mathbb{R}$ for $k=0,\ldots,N$ such that alpha[k] $=\alpha_k$ .
beta The three-term recurrence coefficients $\beta_k \in \mathbb{R}$ for $k=0,\ldots,N$ such that beta[k] $=\beta_k$ .
gamma The three-term recurrence coefficients $\gamma_k \in \mathbb{R}$ for $k=0,\ldots,N$ such that gamma[k] $=\gamma_k$ .
k_start The index $k_{\text{start}} \in \mathbb{N}_0, 0 \le k_{\text{start}} \le N$
threshold The threshold $\kappa \in \mathbb{R}, \kappa > 0$ .