FPT - Fast polynomial transform

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 be given recursion coefficients of the polynomials defined by , and

for . The Chebyshev polnyomials of the first kind are defined by

Let be a polynomial of degree . The FPT transforms the polynomial coefficients from

into Chebyshev coefficients from

## 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 . The individual transforms are addressed by and index number with range . The total number of transforms is therefore .
- t The exponent of the transform length
- 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 .
- alpha The three-term recurrence coefficients for such that alpha[k] .
- beta The three-term recurrence coefficients for such that beta[k] .
- gamma The three-term recurrence coefficients for such that gamma[k] .
- k_start The index
- threshold The threshold .

Author
  Jens Keiner

Definition at line 1307 of file fpt.c.

Referenced by main(), and nfsft_precompute().

## fpt_transposed()

void fpt_transposed | ( | fpt_set | set,
|  | const int | m,
|  | double _Complex * | x,
|  | double _Complex * | y,
|  | const int | k_end,
|  | const unsigned int | flags )

Computes a single DPT transform.

- set
- m
- x
- y
- k_end
- flags

Definition at line 1740 of file fpt.c.

References fpt_step_::a, fpt_data_::alpha_0, fpt_data_::alphaN, fpt_data_::beta_0, fpt_data_::betaN, fpt_set_s_::dpt, FIRST_L, fpt_set_s_::flags, FPT_AL_SYMMETRY, FPT_FUNCTION_VALUES, FPT_NO_FAST_ALGORITHM, fpt_data_::gamma_m1, fpt_data_::gammaN, K_END_TILDE, fpt_data_::k_start, K_START_TILDE, LAST_L, fpt_step_::Ns, fpt_step_::stable, fpt_data_::steps, fpt_step_::ts, X, and fpt_set_s_::xcvecs.