Fast Fourier Transformation class. More...

#include <GFft.hpp>

Inheritance diagram for GFft:

Public Member Functions
	GFft (void)
	Void constructor. More...

	GFft (const GNdarray &array)
	N-dimensional array constructor. More...

	GFft (const GFft &fft)
	Copy constructor. More...

virtual	~GFft (void)
	Destructor. More...

std::complex< double > &	operator() (const int &ix)
	1-dimensional FFT element access operator More...

std::complex< double > &	operator() (const int &ix, const int &iy)
	2-dimensional FFT element access operator More...

const std::complex< double > &	operator() (const int &ix) const
	1-dimensional FFT element access operator (const variant) More...

const std::complex< double > &	operator() (const int &ix, const int &iy) const
	2-dimensional FFT element access operator (const variant) More...

GFft &	operator= (const GFft &fft)
	Assignment operator. More...

GFft &	operator+= (const GFft &fft)
	Unary addition operator. More...

GFft &	operator-= (const GFft &fft)
	Unary subtraction operator. More...

GFft &	operator*= (const GFft &fft)
	Unary multiplication operator. More...

GFft &	operator/= (const GFft &fft)
	Unary division operator. More...

GFft	operator- (void) const
	Unary minus operator. More...

void	clear (void)
	Clear Fast Fourier Transform. More...

GFft *	clone (void) const
	Clone Fast Fourier Transform. More...

std::string	classname (void) const
	Return class name. More...

int	dim (void) const
	Return dimension of Fast Fourier Transformation. More...

int	size (void) const
	Return number of elements in array. More...

const std::vector< int > &	shape (void) const
	Return shape of array. More...

const std::vector< int > &	strides (void) const
	Return strides of array. More...

void	forward (const GNdarray &array)
	Forward Fast Fourier Transform. More...

GNdarray	backward (void) const
	Backward Fast Fourier Transform. More...

std::string	print (const GChatter &chatter=NORMAL) const
	Print Fast Fourier Transform information. More...

Public Member Functions inherited from GBase
virtual	~GBase (void)
	Destructor. More...

Protected Member Functions
void	init_members (void)
	Initialise class members. More...

void	copy_members (const GFft &fft)
	Copy class members. More...

void	free_members (void)
	Delete class members. More...

void	set_data (const GNdarray &array)
	Set data from n-dimensional array. More...

bool	has_same_shape (const GFft &fft) const
	Check if FFT has the same shape. More...

void	require_same_shape (const std::string &method, const GFft &fft) const
	Throw exception if FFT shapes differ. More...

void	transform (std::complex< double > *data, const int &stride, const int &n, const GFftWavetable &wavetable, const bool &forward=true)
	Perform Fast Fourier Transform. More...

void	factor2 (const std::complex< double > in, const int &istride, std::complex< double > out, const int &ostride, const GFftWavetable &wavetable, const int &sign, const int &product, const int &n, const int &index)
	Compute FFT for factor 2. More...

void	factor3 (const std::complex< double > in, const int &istride, std::complex< double > out, const int &ostride, const GFftWavetable &wavetable, const int &sign, const int &product, const int &n, const int &index)
	Compute FFT for factor 3. More...

void	factor4 (const std::complex< double > in, const int &istride, std::complex< double > out, const int &ostride, const GFftWavetable &wavetable, const int &sign, const int &product, const int &n, const int &index)
	Compute FFT for factor 4. More...

void	factor5 (const std::complex< double > in, const int &istride, std::complex< double > out, const int &ostride, const GFftWavetable &wavetable, const int &sign, const int &product, const int &n, const int &index)
	Compute FFT for factor 5. More...

void	factor6 (const std::complex< double > in, const int &istride, std::complex< double > out, const int &ostride, const GFftWavetable &wavetable, const int &sign, const int &product, const int &n, const int &index)
	Compute FFT for factor 6. More...

void	factor7 (const std::complex< double > in, const int &istride, std::complex< double > out, const int &ostride, const GFftWavetable &wavetable, const int &sign, const int &product, const int &n, const int &index)
	Compute FFT for factor 7. More...

void	factorn (std::complex< double > in, const int &istride, std::complex< double > out, const int &ostride, const GFftWavetable &wavetable, const int &sign, const int &factor, const int &product, const int &n, const int &index)
	Compute FFT for arbitrary factor. More...

std::vector< std::complex < double > >	get_w (const GFftWavetable &wavetable, const int &index, const int &k, const int &q, const int &n, const int &sign) const
	Extract coefficients from wavetable. More...

std::complex< double >	timesi (const std::complex< double > &value) const
	Return complex value times i. More...

Protected Attributes
int	m_size
	Size of data array. More...

std::complex< double > *	m_data
	Pointer on array data. More...

std::vector< int >	m_shape
	Array dimensions. More...

std::vector< int >	m_strides
	Steps in each dimension. More...

std::vector< GFftWavetable >	m_wavetable
	Trigonometric coefficients. More...

Detailed Description

Fast Fourier Transformation class.

This class implements a Fast Fourier Transformation of an n-dimensional double precision floating point array.

The class implementation is based on the Fast Fourier Transformation functions that are provided by the GNU Scientific Library (GSL) (version 2.2.1). The mixed-radix routines for complex numbers have been adopted that work for any array lengths. The mixed-radix routines are a reimplementation of the FFTPACK library of Paul Swarztrauber.

The GSL is documented at https://www.gnu.org/software/gsl/manual

Definition at line 57 of file GFft.hpp.

Constructor & Destructor Documentation

GFft::GFft ( void )

Void constructor.

Definition at line 55 of file GFft.cpp.

References init_members().

Referenced by clone().

GFft::GFft ( const GNdarray & array )

explicit

N-dimensional array constructor.

Parameters

[in] array N-dimensional array.

Constructs a Fast Fourier Transformation from a n-dimensional array.

Definition at line 72 of file GFft.cpp.

References forward(), and init_members().

GFft::GFft ( const GFft & fft )

Copy constructor.

Parameters

[in] fft Fast Fourier Transform.

Definition at line 90 of file GFft.cpp.

References copy_members(), and init_members().

GFft::~GFft ( void )

virtual

Destructor.

Definition at line 106 of file GFft.cpp.

References free_members().

Member Function Documentation

GNdarray GFft::backward ( void ) const

Backward Fast Fourier Transform.

Returns: N-dimensional array.

GException::feature_not_implemented Array dimension is not supported.

Performs the inverse (or backward) discret Fast Fourier forward transformation for 1- and 2-dimensional arrays.

For one dimensional arrays of length \(N\) the transformation is given by

\[ z_k = \frac{1}{N} \sum_{n=0}^{N-1} X_n e^{i 2 \pi \frac{k n}{N}} \]

and for two dimensional arrays of length \( M \times N\) the transformation is given by

\[ z_{k,l} = \frac{1}{N} \sum_{n=0}^{N-1} \left( \frac{1}{M} \sum_{m=0}^{M-1} X_{m,n} e^{i 2 \pi \frac{m k}{M}} \right) e^{i 2 \pi \frac{n l}{N}} \]

Definition at line 401 of file GFft.cpp.

References GNdarray::dim(), G_BACKWARD, m_data, m_shape, m_size, m_strides, m_wavetable, norm(), shape(), gammalib::str(), and transform().

Referenced by GSkyMap::convolve().

std::string GFft::classname ( void ) const

inlinevirtual

Return class name.

Returns: String containing the class name ("GFft").

Implements GBase.

Definition at line 194 of file GFft.hpp.

void GFft::clear ( void )

virtual

Clear Fast Fourier Transform.

Implements GBase.

Definition at line 276 of file GFft.cpp.

References free_members(), and init_members().

GFft * GFft::clone ( void ) const

virtual

Clone Fast Fourier Transform.

Returns: Pointer to deep copy of Fast Fourier Transform.

Implements GBase.

Definition at line 294 of file GFft.cpp.

References GFft().

void GFft::copy_members ( const GFft & fft )

protected

Copy class members.

Parameters

[in] fft Fast Fourier Transform.

Definition at line 558 of file GFft.cpp.

References m_data, m_shape, m_size, m_strides, and m_wavetable.

Referenced by GFft(), and operator=().

int GFft::dim ( void ) const

inline

Return dimension of Fast Fourier Transformation.

Returns: Dimension of Fast Fourier Transformation.

Returns the dimension of the Fast Fourier Transformation.

Definition at line 268 of file GFft.hpp.

References m_shape.

Referenced by print().

void GFft::factor2	(	const std::complex< double > *	in,
		const int &	istride,
		std::complex< double > *	out,
		const int &	ostride,
		const GFftWavetable &	wavetable,
		const int &	sign,
		const int &	product,
		const int &	n,
		const int &	index
	)

protected

Compute FFT for factor 2.

Parameters

[in]	in	Pointer to input array.
[in]	istride	Step size when traversing input array.
[in]	out	Pointer to output array.
[in]	ostride	Step size when traversing output array.
[in]	wavetable	Trigonometric coefficients.
[in]	sign	Forward (-1) or backward (+1).
[in]	product	...
[in]	n	Logical array length.
[in]	index	Start index of trigonometric coefficients.

Definition at line 825 of file GFft.cpp.

References get_w().

Referenced by transform().

void GFft::factor3	(	const std::complex< double > *	in,
		const int &	istride,
		std::complex< double > *	out,
		const int &	ostride,
		const GFftWavetable &	wavetable,
		const int &	sign,
		const int &	product,
		const int &	n,
		const int &	index
	)

protected

Compute FFT for factor 3.

Parameters

[in]	in	Pointer to input array.
[in]	istride	Step size when traversing input array.
[in]	out	Pointer to output array.
[in]	ostride	Step size when traversing output array.
[in]	wavetable	Trigonometric coefficients.
[in]	sign	Forward (-1) or backward (+1).
[in]	product	...
[in]	n	Logical array length.
[in]	index	Start index of trigonometric coefficients.

Definition at line 885 of file GFft.cpp.

References get_w(), sqrt(), and timesi().

Referenced by transform().

void GFft::factor4	(	const std::complex< double > *	in,
		const int &	istride,
		std::complex< double > *	out,
		const int &	ostride,
		const GFftWavetable &	wavetable,
		const int &	sign,
		const int &	product,
		const int &	n,
		const int &	index
	)

protected

Compute FFT for factor 4.

Parameters

[in]	in	Pointer to input array.
[in]	istride	Step size when traversing input array.
[in]	out	Pointer to output array.
[in]	ostride	Step size when traversing output array.
[in]	wavetable	Trigonometric coefficients.
[in]	sign	Forward (-1) or backward (+1).
[in]	product	...
[in]	n	Logical array length.
[in]	index	Start index of trigonometric coefficients.

Definition at line 957 of file GFft.cpp.

References get_w(), and timesi().

Referenced by transform().

void GFft::factor5	(	const std::complex< double > *	in,
		const int &	istride,
		std::complex< double > *	out,
		const int &	ostride,
		const GFftWavetable &	wavetable,
		const int &	sign,
		const int &	product,
		const int &	n,
		const int &	index
	)

protected

Compute FFT for factor 5.

Parameters

[in]	in	Pointer to input array.
[in]	istride	Step size when traversing input array.
[in]	out	Pointer to output array.
[in]	ostride	Step size when traversing output array.
[in]	wavetable	Trigonometric coefficients.
[in]	sign	Forward (-1) or backward (+1).
[in]	product	...
[in]	n	Logical array length.
[in]	index	Start index of trigonometric coefficients.

Definition at line 1029 of file GFft.cpp.

References get_w(), sin(), sqrt(), timesi(), and gammalib::twopi.

Referenced by transform().

void GFft::factor6	(	const std::complex< double > *	in,
		const int &	istride,
		std::complex< double > *	out,
		const int &	ostride,
		const GFftWavetable &	wavetable,
		const int &	sign,
		const int &	product,
		const int &	n,
		const int &	index
	)

protected

Compute FFT for factor 6.

Parameters

[in]	in	Pointer to input array.
[in]	istride	Step size when traversing input array.
[in]	out	Pointer to output array.
[in]	ostride	Step size when traversing output array.
[in]	wavetable	Trigonometric coefficients.
[in]	sign	Forward (-1) or backward (+1).
[in]	product	...
[in]	n	Logical array length.
[in]	index	Start index of trigonometric coefficients.

Definition at line 1118 of file GFft.cpp.

References get_w(), sqrt(), and timesi().

Referenced by transform().

void GFft::factor7	(	const std::complex< double > *	in,
		const int &	istride,
		std::complex< double > *	out,
		const int &	ostride,
		const GFftWavetable &	wavetable,
		const int &	sign,
		const int &	product,
		const int &	n,
		const int &	index
	)

protected

Compute FFT for factor 7.

Parameters

[in]	in	Pointer to input array.
[in]	istride	Step size when traversing input array.
[in]	out	Pointer to output array.
[in]	ostride	Step size when traversing output array.
[in]	wavetable	Trigonometric coefficients.
[in]	sign	Forward (-1) or backward (+1).
[in]	product	...
[in]	n	Logical array length.
[in]	index	Start index of trigonometric coefficients.

Definition at line 1214 of file GFft.cpp.

References cos(), get_w(), sin(), timesi(), and gammalib::twopi.

Referenced by transform().

void GFft::factorn	(	std::complex< double > *	in,
		const int &	istride,
		std::complex< double > *	out,
		const int &	ostride,
		const GFftWavetable &	wavetable,
		const int &	sign,
		const int &	factor,
		const int &	product,
		const int &	n,
		const int &	index
	)

protected

Compute FFT for arbitrary factor.

Parameters

[in]	in	Pointer to input array.
[in]	istride	Step size when traversing input array.
[in]	out	Pointer to output array.
[in]	ostride	Step size when traversing output array.
[in]	wavetable	Trigonometric coefficients.
[in]	sign	Forward (-1) or backward (+1).
[in]	factor	Factor.
[in]	product	...
[in]	n	Logical array length.
[in]	index	Start index of trigonometric coefficients.

Definition at line 1343 of file GFft.cpp.

Referenced by transform().

void GFft::forward ( const GNdarray & array )

Forward Fast Fourier Transform.

Parameters

[in] array N-dimensional array.

GException::feature_not_implemented Array dimension is not supported.

Performs discret Fast Fourier forward transformation for 1- and 2-dimensional arrays.

For one dimensional arrays of length \(N\) the transformation is given by

\[ X_k = \sum_{n=0}^{N-1} z_n e^{-i 2 \pi \frac{k n}{N}} \]

and for two dimensional arrays of length \( M \times N\) the transformation is given by

\[ X_{k,l} = \sum_{n=0}^{N-1} \left( \sum_{m=0}^{M-1} z_{m,n} e^{-i 2 \pi \frac{m k}{M}} \right) e^{-i 2 \pi \frac{n l}{N}} \]

Definition at line 328 of file GFft.cpp.

References GNdarray::dim(), G_FORWARD, m_data, m_shape, m_size, m_strides, m_wavetable, set_data(), gammalib::str(), and transform().

Referenced by GFft(), and transform().

void GFft::free_members ( void )

protected

Delete class members.

Definition at line 582 of file GFft.cpp.

References m_data, and m_size.

Referenced by clear(), operator=(), set_data(), and ~GFft().

std::vector< std::complex< double > > GFft::get_w	(	const GFftWavetable &	wavetable,
		const int &	index,
		const int &	k,
		const int &	q,
		const int &	n,
		const int &	sign
	)		const

protected

Extract coefficients from wavetable.

Parameters

[in]	index	Start index of trigonometric coefficients.
[in]	k	...
[in]	q	...
[in]	n	Number of coefficients.
[in]	sign	Forward (-1) or backward (+1) transformation.
[in]	wavetable	Trigonometric coefficients.

Definition at line 1535 of file GFft.cpp.

Referenced by factor2(), factor3(), factor4(), factor5(), factor6(), and factor7().

bool GFft::has_same_shape ( const GFft & fft ) const

protected

Check if FFT has the same shape.

Parameters

[in] fft Fast Fourier Transform.

Returns: True if the FFT has the same shape.

Definition at line 646 of file GFft.cpp.

References m_shape.

Referenced by require_same_shape().

void GFft::init_members ( void )

protected

Initialise class members.

Definition at line 539 of file GFft.cpp.

References m_data, m_shape, m_size, m_strides, and m_wavetable.

Referenced by clear(), GFft(), operator=(), and set_data().

std::complex< double > & GFft::operator() ( const int & ix )

inline

1-dimensional FFT element access operator

Parameters

[in] ix Element index [0,...,shape(0)-1].

Returns: Reference to FFT element.

Definition at line 207 of file GFft.hpp.

References m_data.

std::complex< double > & GFft::operator()	(	const int &	ix,
		const int &	iy
	)

inline

2-dimensional FFT element access operator

Parameters

[in]	ix	Index in first dimension [0,...,shape(0)-1].
[in]	iy	Index in second dimension [0,...,shape(1)-1].

Returns: Reference to FFT element.

Definition at line 222 of file GFft.hpp.

References m_data, and m_strides.

const std::complex< double > & GFft::operator() ( const int & ix ) const

inline

1-dimensional FFT element access operator (const variant)

Parameters

[in] ix Element index [0,...,shape(0)-1].

Returns: Const reference to FFT element.

Definition at line 236 of file GFft.hpp.

References m_data.

const std::complex< double > & GFft::operator()	(	const int &	ix,
		const int &	iy
	)		const

inline

2-dimensional FFT element access operator (const variant)

Parameters

[in]	ix	Index in first dimension [0,...,shape(0)-1].
[in]	iy	Index in second dimension [0,...,shape(1)-1].

Returns: Const reference to FFT element.

Definition at line 251 of file GFft.hpp.

References m_data, and m_strides.

GFft & GFft::operator*= ( const GFft & fft )

Unary multiplication operator.

Parameters

[in] fft Fast Fourier transform.

Returns: Fast Fourier transform.

Multiplies a Fast Fourier Transform to another Fast Fourier Transform. The method requires that both FFTs have the same dimension.

Definition at line 206 of file GFft.cpp.

References G_OP_MUL, m_data, m_size, and require_same_shape().

GFft & GFft::operator+= ( const GFft & fft )

Unary addition operator.

Parameters

[in] fft Fast Fourier Transform.

Returns: Fast Fourier Transform.

Adds a Fast Fourier Transform to another Fast Fourier Transform. The method requires that both FFTs have the same dimension.

Definition at line 158 of file GFft.cpp.

References G_OP_ADD, m_data, m_size, and require_same_shape().

GFft GFft::operator- ( void ) const

Unary minus operator.

Returns: Fast Fourier transformation.

Negates all elements of the Fast Fourier Transformation.

Definition at line 252 of file GFft.cpp.

References size().

GFft & GFft::operator-= ( const GFft & fft )

Unary subtraction operator.

Parameters

[in] fft Fast Fourier transform.

Returns: Fast Fourier transform.

Subtracts a Fast Fourier Transform from another Fast Fourier Transform. The method requires that both FFTs have the same dimension.

Definition at line 182 of file GFft.cpp.

References G_OP_SUB, m_data, m_size, and require_same_shape().

GFft & GFft::operator/= ( const GFft & fft )

Unary division operator.

Parameters

[in] fft Fast Fourier transform.

Returns: Fast Fourier transform.

Divides a Fast Fourier Transform by another Fast Fourier Transform. The method requires that both FFTs have the same dimension.

Definition at line 230 of file GFft.cpp.

References G_OP_DIV, m_data, m_size, and require_same_shape().

GFft & GFft::operator= ( const GFft & fft )

Assignment operator.

Parameters

[in] fft Fast Fourier Transform.

Returns: Fast Fourier Transform.

Definition at line 128 of file GFft.cpp.

References copy_members(), free_members(), and init_members().

std::string GFft::print ( const GChatter & chatter = NORMAL ) const

virtual

Print Fast Fourier Transform information.

Parameters

[in] chatter Chattiness.

Returns: String containing Fast Fourier Transform information.

Implements GBase.

Definition at line 485 of file GFft.cpp.

References dim(), m_shape, m_size, gammalib::parformat(), SILENT, size(), gammalib::str(), and VERBOSE.

void GFft::require_same_shape	(	const std::string &	method,
		const GFft &	fft
	)		const

protected

Throw exception if FFT shapes differ.

Parameters

[in]	method	Method that throws exception.
[in]	fft	Fast Fourier Transform.

Exceptions

GException::invalid_argument FFT shapes differ.

Definition at line 676 of file GFft.cpp.

References has_same_shape(), m_shape, and gammalib::str().

Referenced by operator*=(), operator+=(), operator-=(), and operator/=().

void GFft::set_data ( const GNdarray & array )

protected

Set data from n-dimensional array.

Parameters

[in] array N-dimensional array

Definition at line 603 of file GFft.cpp.

References free_members(), init_members(), m_data, m_shape, m_size, m_strides, m_wavetable, GNdarray::shape(), GNdarray::size(), and GNdarray::strides().

Referenced by forward().

const std::vector< int > & GFft::shape ( void ) const

inline

Return shape of array.

Returns: Shape of array

Returns the shape of the array.

Definition at line 296 of file GFft.hpp.

References m_shape.

Referenced by backward().

int GFft::size ( void ) const

inline

Return number of elements in array.

Returns: Number of elements in array

Returns the number of elements in the array.

Definition at line 282 of file GFft.hpp.

References m_size.

Referenced by operator-(), and print().

const std::vector< int > & GFft::strides ( void ) const

inline

Return strides of array.

Returns: Strides of array

Returns the strides of the array.

Definition at line 310 of file GFft.hpp.

References m_strides.

std::complex< double > GFft::timesi ( const std::complex< double > & value ) const

inlineprotected

Return complex value times i.

Parameters

[in] value Complex value.

Returns: Complex value times i.

Returns complex value times i.

Definition at line 397 of file GFft.hpp.

Referenced by factor3(), factor4(), factor5(), factor6(), and factor7().

void GFft::transform	(	std::complex< double > *	data,
		const int &	stride,
		const int &	n,
		const GFftWavetable &	wavetable,
		const bool &	forward = `true`
	)

protected

Perform Fast Fourier Transform.

Parameters

[in]	data	Pointer to complex array to be transformed.
[in]	stride	Step size when traversing complex array.
[in]	n	Number of elements in complex array.
[in]	wavetable	Trigonometric coefficients.
[in]	forward	Forward transform if true, otherwise backward transform.