Detailed Description

Performs complex-to-complex FFTs.

Synopsis

#include <lal/ComplexFFT.h>

Perform complex-to-complex fast Fourier transforms of vectors using the package FFTW [11] .

Description

This package provides a (X)LAL-style interface with the FFTW fast Fourier transform package [11] .

The routines LALCreateForwardComplexFFTPlan() and LALCreateReverseComplexFFTPlan() create plans for computing the forward and reverse FFTs of a given size. The optimum plan is either estimated (reasonably fast) if the measure flag is zero, or measured (can be time-consuming, but gives better performance) if the measure flag is non-zero. The routine LALDestroyComplexFFTPlan() destroys either of these flavours of plans.

The routine LALCOMPLEX8VectorFFT() performs either the forward or reverse FFT depending on the plan. The discrete Fourier transform $H_k$ , $k=0\ldots n-1$ of a vector $h_j$ , $j=0\ldots n-1$ , of length $n$ is defined by

$H_k = \sum_{j=0}^{n-1} h_j e^{-2\pi ijk/n}$

and, similarly, the inverse Fourier transform is defined by

$h_j = \frac{1}{n}\sum_{k=0}^{n-1} H_k e^{2\pi ijk/n}.$

However, the present implementation of the reverse FFT omits the factor of $1/n$ . The input and output vectors must be distinct.

Operating Instructions

const UINT4 n = 17;
static LALStatus status;
ComplexFFTPlan *pfwd = NULL;
ComplexFFTPlan *prev = NULL;
COMPLEX8Vector *avec = NULL;
COMPLEX8Vector *bvec = NULL;
COMPLEX8Vector *cvec = NULL;
 
LALCreateForwardComplexFFTPlan( &status, &pfwd, n, 0 );
LALCreateReverseComplexFFTPlan( &status, &prev, n, 0 );
LALCCreateVector( &status, &avec, n );
LALCCreateVector( &status, &bvec, n );
LALCCreateVector( &status, &cvec, n );
 
<assign data>
 
LALCOMPLEX8VectorFFT( &status, bvec, avec, pfwd );
LALCOMPLEX8VectorFFT( &status, cvec, bvec, prev );
 
LALDestroyComplexFFTPlan( &status, &pfwd );
LALDestroyComplexFFTPlan( &status, &prev );
LALCDestroyVector( &status, &avec );
LALCDestroyVector( &status, &bvec );
LALCDestroyVector( &status, &cvec );

Algorithm

The FFTW [11] is used.

Uses

Notes

The sign convention used here is the opposite of the definition in Numerical Recipes [22] , but agrees with the one used by FFTW [11] and the other LIGO software components.
The result of the inverse FFT must be multiplied by $1/n$ to recover the original vector. This is different from the datacondAPI where the factor is applied by default.
The size $n$ of the transform can be any positive integer; the performance is $O(n\log n)$ . However, better performance is obtained if $n$ is the product of powers of 2, 3, 5, 7, and zero or one power of either 11 or 13. Transforms when $n$ is a power of 2 are especially fast. See Ref. [11] .
LALMalloc() is used by all the fftw routines.
The input and output vectors for LALCOMPLEX8VectorFFT() must be distinct.

Prototypes
COMPLEX8FFTPlan *	XLALCreateCOMPLEX8FFTPlan (UINT4 size, int fwdflg, int measurelvl)
	Returns a new COMPLEX8FFTPlan A COMPLEX8FFTPlan is required to perform a FFT that involves complex data. More...

COMPLEX8FFTPlan *	XLALCreateForwardCOMPLEX8FFTPlan (UINT4 size, int measurelvl)
	Returns a new COMPLEX8FFTPlan for a forward transform. More...

COMPLEX8FFTPlan *	XLALCreateReverseCOMPLEX8FFTPlan (UINT4 size, int measurelvl)
	Returns a new COMPLEX8FFTPlan for a reverse transform. More...

void	XLALDestroyCOMPLEX8FFTPlan (COMPLEX8FFTPlan *plan)
	Destroys a COMPLEX8FFTPlan. More...

int	XLALCOMPLEX8VectorFFT (COMPLEX8Vector _LAL_RESTRICT_ output, const COMPLEX8Vector _LAL_RESTRICT_ input, const COMPLEX8FFTPlan *plan)
	Perform a COMPLEX8Vector to COMPLEX8Vector FFT. More...

COMPLEX16FFTPlan *	XLALCreateCOMPLEX16FFTPlan (UINT4 size, int fwdflg, int measurelvl)
	Returns a new COMPLEX16FFTPlan. More...

COMPLEX16FFTPlan *	XLALCreateForwardCOMPLEX16FFTPlan (UINT4 size, int measurelvl)
	Returns a new COMPLEX16FFTPlan for a forward transform. More...

COMPLEX16FFTPlan *	XLALCreateReverseCOMPLEX16FFTPlan (UINT4 size, int measurelvl)
	Returns a new COMPLEX16FFTPlan for a reverse transform. More...

void	XLALDestroyCOMPLEX16FFTPlan (COMPLEX16FFTPlan *plan)
	Destroys a COMPLEX16FFTPlan. More...

int	XLALCOMPLEX16VectorFFT (COMPLEX16Vector _LAL_RESTRICT_ output, const COMPLEX16Vector _LAL_RESTRICT_ input, const COMPLEX16FFTPlan *plan)
	Perform a COMPLEX16Vector to COMPLEX16Vector FFT. More...

Data Structures
struct	COMPLEX8FFTPlan
	Plan to perform an FFT of COMPLEX8 data. More...

struct	COMPLEX16FFTPlan
	Plan to perform an FFT of COMPLEX16 data. More...

Macros
#define	SINGLE_PRECISION

#define	tagComplexFFTPlan tagCOMPLEX8FFTPlan

#define	ComplexFFTPlan COMPLEX8FFTPlan

Files
file	ComplexFFTTest.c
	Tests the routines in ComplexFFT.h.

Error Codes
#define	COMPLEXFFTH_ENULL 1
	Null pointer. More...

#define	COMPLEXFFTH_ENNUL 2
	Non-null pointer. More...

#define	COMPLEXFFTH_ESIZE 4
	Invalid input size. More...

#define	COMPLEXFFTH_ESZMM 8
	Size mismatch. More...

#define	COMPLEXFFTH_ESLEN 16
	Invalid/mismatched sequence lengths. More...

#define	COMPLEXFFTH_ESAME 32
	Input/Output data vectors are the same. More...

#define	COMPLEXFFTH_EALOC 64
	Memory allocation failed. More...

#define	COMPLEXFFTH_EFFTW 128
	Error in FFTW. More...

#define	COMPLEXFFTH_ESNGL 256
	FFTW library is not single-precision. More...

#define	COMPLEXFFTH_EINTL 512
	Error in Intel FFT library. More...

#define	COMPLEXFFTH_ESIGN 1024
	Unknown sign of transform in plan. More...

Function Documentation

◆ XLALCreateCOMPLEX8FFTPlan()

COMPLEX8FFTPlan * XLALCreateCOMPLEX8FFTPlan	(	UINT4	size,
		int	fwdflg,
		int	measurelvl
	)

Returns a new COMPLEX8FFTPlan A COMPLEX8FFTPlan is required to perform a FFT that involves complex data.

A different plan is required for each size of the complex data vectors and for each direction of transform (forward or reverse). A forward transform performs

$Z[k] = \sum_{j=0}^{N-1} e^{-2\pi ijk/N}\,z[j]$

where N, the size of the transform, is the length of the vectors z and Z. A reverse transform performs

$w[j] = \sum_{k=0}^{N-1} e^{+2\pi ijk/N}\,W[k]$

where N, the size of the transform, is the length of the vectors w and W.

Note: The reverse transform of the forward transform of some data is equal to N times the original data (we therefore call it a "reverse" transform rather than an "inverse" transform).

Parameters

[in]	size	The number of points in the complex data.
[in]	fwdflg	Set non-zero for a forward FFT plan; otherwise create a reverse plan
[in]	measurelvl	Measurement level for plan creation: 0: no measurement, just estimate the plan; 1: measure the best plan; 2: perform a lengthy measurement of the best plan; 3: perform an exhasutive measurement of the best plan.

Returns: A pointer to an allocated COMPLEX8FFTPlan structure is returned upon successful completion. Otherwise, a NULL pointer is returned and xlalErrno is set to indicate the error.

Errors:

The XLALCreateCOMPLEX8Plan() function shall fail if:

[XLAL_EBADLEN] The size of the requested plan is 0.
[XLAL_ENOMEM] Insufficient storage space is available.
[XLAL_EFAILED] The call to the underlying FFTW routine failed.

◆ XLALCreateForwardCOMPLEX8FFTPlan()

COMPLEX8FFTPlan * XLALCreateForwardCOMPLEX8FFTPlan	(	UINT4	size,
		int	measurelvl
	)

Returns a new COMPLEX8FFTPlan for a forward transform.

A COMPLEX8FFTPlan is required to perform a FFT that involves complex data. A different plan is required for each size of the complex data vectors. A forward transform performs

$Z[k] = \sum_{j=0}^{N-1} e^{-2\pi ijk/N}\,z[j]$

where N, the size of the transform, is the length of the vector z and Z.

Parameters

[in]	size	The number of points in the complex data.
[in]	measurelvl	Measurement level for plan creation: 0: no measurement, just estimate the plan; 1: measure the best plan; 2: perform a lengthy measurement of the best plan; 3: perform an exhasutive measurement of the best plan.

Returns: A pointer to an allocated COMPLEX8FFTPlan structure is returned upon successful completion. Otherwise, a NULL pointer is returned and xlalErrno is set to indicate the error.

Errors:

The XLALCreateForwardCOMPLEX8Plan() function shall fail if:

[XLAL_EBADLEN] The size of the requested plan is 0.
[XLAL_ENOMEM] Insufficient storage space is available.
[XLAL_EFAILED] The call to the underlying FFTW routine failed.

Definition at line 94 of file CudaComplexFFT.c.

◆ XLALCreateReverseCOMPLEX8FFTPlan()

COMPLEX8FFTPlan * XLALCreateReverseCOMPLEX8FFTPlan	(	UINT4	size,
		int	measurelvl
	)

Returns a new COMPLEX8FFTPlan for a reverse transform.

A COMPLEX8FFTPlan is required to perform a FFT that involves complex data. A reverse transform performs

$w[j] = \sum_{k=0}^{N-1} e^{+2\pi ijk/N}\,W[k]$

where N, the size of the transform, is the length of the vectors w and W.

Note: The reverse transform of the forward transform of some data is equal to N times the original data (we therefore call it a "reverse" transform rather than an "inverse" transform).

Parameters

[in]	size	The number of points in the complex data.
[in]	measurelvl	Measurement level for plan creation: 0: no measurement, just estimate the plan; 1: measure the best plan; 2: perform a lengthy measurement of the best plan; 3: perform an exhasutive measurement of the best plan.

Returns: A pointer to an allocated COMPLEX8FFTPlan structure is returned upon successful completion. Otherwise, a NULL pointer is returned and xlalErrno is set to indicate the error.

Errors:

The XLALCreateReverseCOMPLEX8Plan() function shall fail if:

[XLAL_EBADLEN] The size of the requested plan is 0.
[XLAL_ENOMEM] Insufficient storage space is available.
[XLAL_EFAILED] The call to the underlying FFTW routine failed.

Definition at line 104 of file CudaComplexFFT.c.

◆ XLALDestroyCOMPLEX8FFTPlan()

void XLALDestroyCOMPLEX8FFTPlan ( COMPLEX8FFTPlan * plan )

Destroys a COMPLEX8FFTPlan.

Parameters

[in] plan A pointer to the COMPLEX8FFTPlan to be destroyed.

Definition at line 114 of file CudaComplexFFT.c.

◆ XLALCOMPLEX8VectorFFT()

int XLALCOMPLEX8VectorFFT	(	COMPLEX8Vector *_LAL_RESTRICT_	output,
		const COMPLEX8Vector *_LAL_RESTRICT_	input,
		const COMPLEX8FFTPlan *	plan
	)

Perform a COMPLEX8Vector to COMPLEX8Vector FFT.

This routine computes

$Z[k] = \sum_{j=0}^{N-1} e^{\mp2\pi ijk/N}\,z[j],$

and where the minus sign is used if a forward plan is provided as the argument and the plus sign is used if a reverse plan is provided as the argument; here N is the length of the input and output vectors z and Z.

Parameters

[out]	output	The complex output data vector Z of length N
[in]	input	The input complex data vector z of length N
[in]	plan	The FFT plan to use for the transform

Note: The input and output vectors must be distinct.

Returns: 0 upon successful completion or non-zero upon failure.

Errors:

The XLALCOMPLEX8VectorFFT() function shall fail if:

[XLAL_EFAULT] A NULL pointer is provided as one of the arguments.
[XLAL_EINVAL] A argument is invalid or the input and output data vectors are the same.
[XLAL_EBADLEN] The input vector, output vector, and plan size are incompatible.
[XLAL_ENOMEM] Insufficient storage space is available.

Definition at line 133 of file CudaComplexFFT.c.

◆ XLALCreateCOMPLEX16FFTPlan()

COMPLEX16FFTPlan * XLALCreateCOMPLEX16FFTPlan	(	UINT4	size,
		int	fwdflg,
		int	measurelvl
	)

Returns a new COMPLEX16FFTPlan.

A COMPLEX16FFTPlan is required to perform a FFT that involves complex data. A different plan is required for each size of the complex data vectors and for each direction of transform (forward or reverse). A forward transform performs

$Z[k] = \sum_{j=0}^{N-1} e^{-2\pi ijk/N}\,z[j]$

where N, the size of the transform, is the length of the vectors z and Z. A reverse transform performs

$w[j] = \sum_{k=0}^{N-1} e^{+2\pi ijk/N}\,W[k]$

where N, the size of the transform, is the length of the vectors w and W.

Note: The reverse transform of the forward transform of some data is equal to N times the original data (we therefore call it a "reverse" transform rather than an "inverse" transform).

Parameters

[in]	size	The number of points in the complex data.
[in]	fwdflg	Set non-zero for a forward FFT plan; otherwise create a reverse plan
[in]	measurelvl	Measurement level for plan creation: 0: no measurement, just estimate the plan; 1: measure the best plan; 2: perform a lengthy measurement of the best plan; 3: perform an exhasutive measurement of the best plan.

Returns: A pointer to an allocated COMPLEX16FFTPlan structure is returned upon successful completion. Otherwise, a NULL pointer is returned and xlalErrno is set to indicate the error.

Errors:

The XLALCreateCOMPLEX16Plan() function shall fail if:

[XLAL_EBADLEN] The size of the requested plan is 0.
[XLAL_ENOMEM] Insufficient storage space is available.
[XLAL_EFAILED] The call to the underlying FFTW routine failed.

Definition at line 169 of file CudaComplexFFT.c.

◆ XLALCreateForwardCOMPLEX16FFTPlan()

COMPLEX16FFTPlan * XLALCreateForwardCOMPLEX16FFTPlan	(	UINT4	size,
		int	measurelvl
	)

Returns a new COMPLEX16FFTPlan for a forward transform.

A COMPLEX16FFTPlan is required to perform a FFT that involves complex data. A different plan is required for each size of the complex data vectors. A forward transform performs

$Z[k] = \sum_{j=0}^{N-1} e^{-2\pi ijk/N}\,z[j]$

where N, the size of the transform, is the length of the vector z and Z.

Parameters

[in]	size	The number of points in the complex data.
[in]	measurelvl	Measurement level for plan creation: 0: no measurement, just estimate the plan; 1: measure the best plan; 2: perform a lengthy measurement of the best plan; 3: perform an exhasutive measurement of the best plan.

Returns: A pointer to an allocated COMPLEX16FFTPlan structure is returned upon successful completion. Otherwise, a NULL pointer is returned and xlalErrno is set to indicate the error.

Errors:

The XLALCreateForwardCOMPLEX16Plan() function shall fail if:

[XLAL_EBADLEN] The size of the requested plan is 0.
[XLAL_ENOMEM] Insufficient storage space is available.
[XLAL_EFAILED] The call to the underlying FFTW routine failed.

Definition at line 236 of file CudaComplexFFT.c.

◆ XLALCreateReverseCOMPLEX16FFTPlan()

COMPLEX16FFTPlan * XLALCreateReverseCOMPLEX16FFTPlan	(	UINT4	size,
		int	measurelvl
	)

Returns a new COMPLEX16FFTPlan for a reverse transform.

A COMPLEX16FFTPlan is required to perform a FFT that involves complex data. A reverse transform performs

$w[j] = \sum_{k=0}^{N-1} e^{+2\pi ijk/N}\,W[k]$

where N, the size of the transform, is the length of the vectors w and W.

Note: The reverse transform of the forward transform of some data is equal to N times the original data (we therefore call it a "reverse" transform rather than an "inverse" transform).

Parameters

[in]	size	The number of points in the complex data.
[in]	measurelvl	Measurement level for plan creation: 0: no measurement, just estimate the plan; 1: measure the best plan; 2: perform a lengthy measurement of the best plan; 3: perform an exhasutive measurement of the best plan.

Returns: A pointer to an allocated COMPLEX16FFTPlan structure is returned upon successful completion. Otherwise, a NULL pointer is returned and xlalErrno is set to indicate the error.

Errors:

The XLALCreateReverseCOMPLEX16Plan() function shall fail if:

[XLAL_EBADLEN] The size of the requested plan is 0.
[XLAL_ENOMEM] Insufficient storage space is available.
[XLAL_EFAILED] The call to the underlying FFTW routine failed.

Definition at line 246 of file CudaComplexFFT.c.

◆ XLALDestroyCOMPLEX16FFTPlan()

void XLALDestroyCOMPLEX16FFTPlan ( COMPLEX16FFTPlan * plan )

Destroys a COMPLEX16FFTPlan.

Parameters

[in] plan A pointer to the COMPLEX16FFTPlan to be destroyed.

Definition at line 256 of file CudaComplexFFT.c.

◆ XLALCOMPLEX16VectorFFT()

int XLALCOMPLEX16VectorFFT	(	COMPLEX16Vector *_LAL_RESTRICT_	output,
		const COMPLEX16Vector *_LAL_RESTRICT_	input,
		const COMPLEX16FFTPlan *	plan
	)

Perform a COMPLEX16Vector to COMPLEX16Vector FFT.

This routine computes

$Z[k] = \sum_{j=0}^{N-1} e^{\mp2\pi ijk/N}\,z[j],$

and where the minus sign is used if a forward plan is provided as the argument and the plus sign is used if a reverse plan is provided as the argument; here N is the length of the input and output vectors z and Z.

Parameters

[out]	output	The complex output data vector Z of length N
[in]	input	The input complex data vector z of length N
[in]	plan	The FFT plan to use for the transform

Note: The input and output vectors must be distinct.

Returns: 0 upon successful completion or non-zero upon failure.

Errors:

The XLALCOMPLEX16VectorFFT() function shall fail if:

[XLAL_EFAULT] A NULL pointer is provided as one of the arguments.
[XLAL_EINVAL] A argument is invalid or the input and output data vectors are the same.
[XLAL_EBADLEN] The input vector, output vector, and plan size are incompatible.
[XLAL_ENOMEM] Insufficient storage space is available.

Definition at line 273 of file CudaComplexFFT.c.

Macro Definition Documentation

◆ SINGLE_PRECISION

#define SINGLE_PRECISION

Definition at line 145 of file ComplexFFT.c.

◆ COMPLEXFFTH_ENULL

#define COMPLEXFFTH_ENULL 1

Null pointer.

Definition at line 51 of file ComplexFFT.h.

◆ COMPLEXFFTH_ENNUL

#define COMPLEXFFTH_ENNUL 2

Non-null pointer.

Definition at line 52 of file ComplexFFT.h.

◆ COMPLEXFFTH_ESIZE

#define COMPLEXFFTH_ESIZE 4

Invalid input size.

Definition at line 53 of file ComplexFFT.h.

◆ COMPLEXFFTH_ESZMM

#define COMPLEXFFTH_ESZMM 8

Size mismatch.

Definition at line 54 of file ComplexFFT.h.

◆ COMPLEXFFTH_ESLEN

#define COMPLEXFFTH_ESLEN 16

Invalid/mismatched sequence lengths.

Definition at line 55 of file ComplexFFT.h.

◆ COMPLEXFFTH_ESAME

#define COMPLEXFFTH_ESAME 32

Input/Output data vectors are the same.

Definition at line 56 of file ComplexFFT.h.

◆ COMPLEXFFTH_EALOC

#define COMPLEXFFTH_EALOC 64

Memory allocation failed.

Definition at line 57 of file ComplexFFT.h.

◆ COMPLEXFFTH_EFFTW

#define COMPLEXFFTH_EFFTW 128

Error in FFTW.

Definition at line 58 of file ComplexFFT.h.

◆ COMPLEXFFTH_ESNGL

#define COMPLEXFFTH_ESNGL 256

FFTW library is not single-precision.

Definition at line 59 of file ComplexFFT.h.

◆ COMPLEXFFTH_EINTL

#define COMPLEXFFTH_EINTL 512

Error in Intel FFT library.

Definition at line 60 of file ComplexFFT.h.

◆ COMPLEXFFTH_ESIGN

#define COMPLEXFFTH_ESIGN 1024

Unknown sign of transform in plan.

Definition at line 61 of file ComplexFFT.h.

◆ tagComplexFFTPlan

#define tagComplexFFTPlan tagCOMPLEX8FFTPlan

Definition at line 82 of file ComplexFFT.h.

◆ ComplexFFTPlan

#define ComplexFFTPlan COMPLEX8FFTPlan

Definition at line 83 of file ComplexFFT.h.

Detailed Description

Synopsis

Description

Operating Instructions

Algorithm

Uses

Notes

Prototypes

Data Structures

Macros

Files

Error Codes

Function Documentation

◆ XLALCreateCOMPLEX8FFTPlan()

◆ XLALCreateForwardCOMPLEX8FFTPlan()

◆ XLALCreateReverseCOMPLEX8FFTPlan()

◆ XLALDestroyCOMPLEX8FFTPlan()

◆ XLALCOMPLEX8VectorFFT()

◆ XLALCreateCOMPLEX16FFTPlan()

◆ XLALCreateForwardCOMPLEX16FFTPlan()

◆ XLALCreateReverseCOMPLEX16FFTPlan()

◆ XLALDestroyCOMPLEX16FFTPlan()

◆ XLALCOMPLEX16VectorFFT()

Macro Definition Documentation

◆ SINGLE_PRECISION

◆ COMPLEXFFTH_ENULL

◆ COMPLEXFFTH_ENNUL

◆ COMPLEXFFTH_ESIZE

◆ COMPLEXFFTH_ESZMM

◆ COMPLEXFFTH_ESLEN

◆ COMPLEXFFTH_ESAME

◆ COMPLEXFFTH_EALOC

◆ COMPLEXFFTH_EFFTW

◆ COMPLEXFFTH_ESNGL

◆ COMPLEXFFTH_EINTL

◆ COMPLEXFFTH_ESIGN

◆ tagComplexFFTPlan

◆ ComplexFFTPlan