Files
file	AlgFourier.c
	Fast Fourier and Hartley transform functions.

Functions
void	AlgFourHart1D (double *data, int num, int step)
	Computes the Hartley transform of the given one dimensional data, and does it in place. More...

AlgError	AlgFourHart2D (double **data, int useBuf, int numX, int numY)
	Computes the Hartley transform of the given two dimensional data, and does it in place. More...

void	AlgFour1D (double real, double imag, int num, int step)
	Computes the Fourier transform of the given one dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n}\). More...

void	AlgFourInv1D (double real, double imag, int num, int step)
	Computes the inverse Fourier transform of the given complex one dimensional data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n}\). More...

void	AlgFourReal1D (double *real, int num, int step)
	Computes the Fourier transform of the given one dimensional real data, and does it in place. Data are returned in the array of size \(N\) as: The data are returned in the array of size N with the layout as shown in the table (with 2M = N, r = real, i = imaginary): \|-------—\| \| r0 \( \| \| r1\) \| \| .. \| \| r(M-1) \| \| rM \| \| i1 \| \| i2 \| \| ... \| \| i(M - 1) \| where the real and imaginary components are indexed as in the arrays computed with AlgFour1D(). The transformed values data are scaled by a factor of \(\sqrt{n}\). More...

void	AlgFourRealInv1D (double *real, int num, int step)
	Computes the inverse Fourier transform of the given one one dimensional real data, and does it in place. The data should layed out in the array as returned by AlgFourReal1D(). The transformed values data are scaled by a factor of \(\sqrt{n}\). More...

AlgError	AlgFour2D (double real, double imag, int useBuf, int numX, int numY)
	Computes the Fourier transform of the given two dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y}\). More...

AlgError	AlgFourInv2D (double real, double imag, int useBuf, int numX, int numY)
	Computes the inverse Fourier transform of the given two dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y}\). More...

AlgError	AlgFourReal2D (double **real, int useBuf, int numX, int numY)
	Computes the Fourier transform of the given two dimensional real data, and does it in place. More...

AlgError	AlgFourRealInv2D (double **real, int useBuf, int numX, int numY)
	Computes the Fourier transform of the given two dimensional data which resulted from a transform using AlgFourReal2D(), and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y}\). More...

AlgError	AlgFour3D (double *real, double *imag, int useBuf, int numX, int numY, int numZ)
	Computes the Fourier transform of the given three dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y} \sqrt{n_z}\). More...

AlgError	AlgFourInv3D (double *real, double *imag, int useBuf, int numX, int numY, int numZ)
	Computes the inverse Fourier transform of the given three dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y} \sqrt{n_z}\). More...

AlgError	AlgFourReal3D (double ***real, int useBuf, int numX, int numY, int numZ)
	Computes the Fourier transform of the given three dimensional real data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y} \sqrt{n_z}\). More...

AlgError	AlgFourRealInv3D (double ***real, int useBuf, int numX, int numY, int numZ)
	Computes the Fourier transform of the given three dimensional data which resulted from a transform using AlgFourReal3D(), and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y} \sqrt{n_z}\). More...

Detailed Description

Function Documentation

◆ AlgFourHart1D()

void AlgFourHart1D	(	double *	data,
		int	num,
		int	step
	)

Computes the Hartley transform of the given one dimensional data, and does it in place.

Returns: void

Parameters

data	Given data.
num	Number of data.
step	Offset in data elements between the data to be transformed.

References ALG_DBG, ALG_DBG_LVL_1, ALG_DBG_LVL_FN, and ALG_M_SQRT2.

Referenced by AlgFour1D(), AlgFourHart2D(), AlgFourInv1D(), AlgFourReal1D(), and AlgFourRealInv1D().

◆ AlgFourHart2D()

AlgError AlgFourHart2D	(	double **	data,
		int	useBuf,
		int	numX,
		int	numY
	)

Computes the Hartley transform of the given two dimensional data, and does it in place.

Returns: Error code, may be set if buffers can not be allocated.

Parameters

data	Given data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.

References AlcFree(), AlcMalloc(), ALG_DBG, ALG_DBG_LVL_1, ALG_DBG_LVL_FN, ALG_ERR_MALLOC, ALG_ERR_NONE, and AlgFourHart1D().

◆ AlgFour1D()

void AlgFour1D	(	double *	real,
		double *	imag,
		int	num,
		int	step
	)

Computes the Fourier transform of the given one dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n}\).

Returns: void

Parameters

real	Given real data.
imag	Given imaginary data.
num	Number of data.
step	Offset in data elements between the data to be transformed.

References ALG_DBG, ALG_DBG_LVL_1, ALG_DBG_LVL_FN, and AlgFourHart1D().

◆ AlgFourInv1D()

void AlgFourInv1D	(	double *	real,
		double *	imag,
		int	num,
		int	step
	)

Computes the inverse Fourier transform of the given complex one dimensional data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n}\).

Returns: void

Parameters

real	Given real data.
imag	Given imaginary data.
num	Number of data.
step	Offset in data elements between the data to be transformed.

References ALG_DBG, ALG_DBG_LVL_1, ALG_DBG_LVL_FN, and AlgFourHart1D().

◆ AlgFourReal1D()

void AlgFourReal1D	(	double *	real,
		int	num,
		int	step
	)

Computes the Fourier transform of the given one dimensional real data, and does it in place. Data are returned in the array of size \(N\) as: The data are returned in the array of size N with the layout as shown in the table (with 2M = N, r = real, i = imaginary): |-------—| | r0 \( | | r1\) | | .. | | r(M-1) | | rM | | i1 | | i2 | | ... | | i(M - 1) | where the real and imaginary components are indexed as in the arrays computed with AlgFour1D(). The transformed values data are scaled by a factor of \(\sqrt{n}\).

Returns: void

Parameters

real	Given real data.
num	Number of data (N).
step	Offset in data elements between the data to be transformed.

References ALG_DBG, ALG_DBG_LVL_1, ALG_DBG_LVL_FN, and AlgFourHart1D().

◆ AlgFourRealInv1D()

void AlgFourRealInv1D	(	double *	real,
		int	num,
		int	step
	)

Computes the inverse Fourier transform of the given one one dimensional real data, and does it in place. The data should layed out in the array as returned by AlgFourReal1D(). The transformed values data are scaled by a factor of \(\sqrt{n}\).

Returns: void

Parameters

real	Given real/complex data.
num	Number of data.
step	Offset in data elements between the data to be transformed.

References ALG_DBG, ALG_DBG_LVL_1, ALG_DBG_LVL_FN, and AlgFourHart1D().

◆ AlgFour2D()

AlgError AlgFour2D	(	double **	real,
		double **	imag,
		int	useBuf,
		int	numX,
		int	numY
	)

Computes the Fourier transform of the given two dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y}\).

Returns: Error code, may be set if buffers can not be allocated.

Parameters

real	Given real data.
imag	Given imaginary data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.

References ALG_DBG, ALG_DBG_LVL_1, and ALG_DBG_LVL_FN.

◆ AlgFourInv2D()

AlgError AlgFourInv2D	(	double **	real,
		double **	imag,
		int	useBuf,
		int	numX,
		int	numY
	)

Computes the inverse Fourier transform of the given two dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y}\).

Returns: Error code, may be set if buffers can not be allocated.

Parameters

real	Given real data.
imag	Given imaginary data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.

References ALG_DBG, ALG_DBG_LVL_1, and ALG_DBG_LVL_FN.

◆ AlgFourReal2D()

AlgError AlgFourReal2D	(	double **	real,
		int	useBuf,
		int	numX,
		int	numY
	)

Computes the Fourier transform of the given two dimensional real data, and does it in place.

Returns

Error code, may be set if buffers can not be allocated.

    The layout of the array is similar to that in AlgFourReal1D()
    and as shown in the table (with 2M = N, r = real,
    i = imaginary):

  -------|--------|---|------------|-------|--------|---|-----------
  r00    |r01     |...|r0(M-1)     |r0M    |i01     |...|i0(M-1)
  ...    |...     |...|...         |...    |...     |...|...
  r(M-1)0|r(M-1)1 |...|r(M-1)(M-1) |r(M-1)M|i(M-1)1 |...|i(M-1)(M-1)
  rM0    |rM1     |...|rM(M-1)     |rMM    |iM1     |...|iM(M-1)
  i10    |r(M+1)1 |...|r(M+1)(M-1) |i1M    |i(M+1)1 |...|i(M+1)(M-1)
  ...    |...     |...|...         |...    |...     |...|...
  i(M-1)0|r(2M-1)1|...|r(2M-1)(M-1)|i(M-1)M|i(2M-1)1|...|i(2M-1)(M-1)

    Using contiguous buffers has a large effect for
    data larger than a CPU's fastest cache and little
    cost for smaller data arrays.
    The times below were measured for on a Lenovo T430s
    with a i7-2640M with 4kB cache. Data sizes are the
    number of double values. These times include buffer
    allocation but not array allocation or file I/O
    and are the mean of 5 runs using elapsed (wall
    clock) time.
  data sz | tm (no buf, 1 thr) | tm (buf, 1 thr) | tm (buf, 2 thr)
  --------|--------------------|-----------------|-------------
    256^2 |     3ms            |    3ms          |    2ms
    512^2 |    12ms            |    6ms          |    4ms
   1024^2 |   120ms            |   44ms          |   35ms
   2048^2 |   600ms            |  170ms          |  110ms
   4096^2 |  3300ms            |  764ms          |  460ms
   8192^2 | 17000ms            | 3600ms          | 2100ms
    The transformed values data are scaled by a factor
    of \form#635.

Parameters

real	Given real data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.

References ALG_DBG, ALG_DBG_LVL_1, and ALG_DBG_LVL_FN.

Referenced by AlgAutoCorrelate2D(), and AlgCrossCorrelate2D().

◆ AlgFourRealInv2D()

AlgError AlgFourRealInv2D	(	double **	real,
		int	useBuf,
		int	numX,
		int	numY
	)

Computes the Fourier transform of the given two dimensional data which resulted from a transform using AlgFourReal2D(), and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y}\).

Returns: Error code, may be set if buffers can not be allocated.

Parameters

real	Given real/complex data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.

References ALG_DBG, ALG_DBG_LVL_1, and ALG_DBG_LVL_FN.

Referenced by AlgAutoCorrelate2D(), and AlgCrossCorrelate2D().

◆ AlgFour3D()

AlgError AlgFour3D	(	double ***	real,
		double ***	imag,
		int	useBuf,
		int	numX,
		int	numY,
		int	numZ
	)

Computes the Fourier transform of the given three dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y} \sqrt{n_z}\).

Returns

Error code, may be set if buffers can not be allocated.

    Using contiguous buffers has a large effect for
    data larger than a CPU's fastest cache and little
    cost for smaller data arrays.

Parameters

real	Given real data.
imag	Given imaginary data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.
numZ	Number of data in each plane.

References ALG_DBG, ALG_DBG_LVL_1, and ALG_DBG_LVL_FN.

◆ AlgFourInv3D()

AlgError AlgFourInv3D	(	double ***	real,
		double ***	imag,
		int	useBuf,
		int	numX,
		int	numY,
		int	numZ
	)

Computes the inverse Fourier transform of the given three dimensional complex data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y} \sqrt{n_z}\).

Returns: Error code, may be set if buffers can not be allocated.

Parameters

real	Given real data.
imag	Given imaginary data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.
numZ	Number of data in each plane.

References ALG_DBG, ALG_DBG_LVL_1, and ALG_DBG_LVL_FN.

◆ AlgFourReal3D()

AlgError AlgFourReal3D	(	double ***	real,
		int	useBuf,
		int	numX,
		int	numY,
		int	numZ
	)

Computes the Fourier transform of the given three dimensional real data, and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y} \sqrt{n_z}\).

Returns

Error code, may be set if buffers can not be allocated.

    Using contiguous buffers has a large effect for
    data larger than a CPU's fastest cache and little

Parameters

real	Given real data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.
numZ	Number of data in each plane.

References ALG_DBG, ALG_DBG_LVL_1, and ALG_DBG_LVL_FN.

◆ AlgFourRealInv3D()

AlgError AlgFourRealInv3D	(	double ***	real,
		int	useBuf,
		int	numX,
		int	numY,
		int	numZ
	)

Computes the Fourier transform of the given three dimensional data which resulted from a transform using AlgFourReal3D(), and does it in place. The transformed values data are scaled by a factor of \(\sqrt{n_x} \sqrt{n_y} \sqrt{n_z}\).

Returns: Error code, may be set if buffers can not be allocated.

Parameters

real	Given real/complex data.
useBuf	Allocate private buffers to make columns contiguous.
numX	Number of data in each row.
numY	Number of data in each column.
numZ	Number of data in each plane.

References ALG_DBG, ALG_DBG_LVL_1, and ALG_DBG_LVL_FN.

Files

Functions

Detailed Description

Function Documentation

◆ AlgFourHart1D()

◆ AlgFourHart2D()

◆ AlgFour1D()

◆ AlgFourInv1D()

◆ AlgFourReal1D()

◆ AlgFourRealInv1D()

◆ AlgFour2D()

◆ AlgFourInv2D()

◆ AlgFourReal2D()

◆ AlgFourRealInv2D()

◆ AlgFour3D()

◆ AlgFourInv3D()

◆ AlgFourReal3D()

◆ AlgFourRealInv3D()