Class FastFourierTransformer
- All Implemented Interfaces:
Serializable
There are several conventions for the definition of FFT and inverse FFT, mainly on different coefficient and exponent. Here the equations are listed in the comments of the corresponding methods.
We require the length of data set to be power of 2, this greatly simplifies and speeds up the code. Users can pad the data with zeros to meet this requirement. There are other flavors of FFT, for reference, see S. Winograd, On computing the discrete Fourier transform, Mathematics of Computation, 32 (1978), 175 - 199.
- Since:
- 1.2
- Version:
- $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 févr. 2011) $
- See Also:
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected Complex[]
fft
(double[] f, boolean isInverse) Perform the base-4 Cooley-Tukey FFT algorithm (including inverse).protected Complex[]
Perform the base-4 Cooley-Tukey FFT algorithm (including inverse).Complex[]
inversetransform
(double[] f) Inversely transform the given real data set.Complex[]
inversetransform
(UnivariateRealFunction f, double min, double max, int n) Inversely transform the given real function, sampled on the given interval.Complex[]
inversetransform
(Complex[] f) Inversely transform the given complex data set.Complex[]
inversetransform2
(double[] f) Inversely transform the given real data set.Complex[]
inversetransform2
(UnivariateRealFunction f, double min, double max, int n) Inversely transform the given real function, sampled on the given interval.Complex[]
inversetransform2
(Complex[] f) Inversely transform the given complex data set.static boolean
isPowerOf2
(long n) Returns true if the argument is power of 2.Performs a multi-dimensional Fourier transform on a given array.static double[]
sample
(UnivariateRealFunction f, double min, double max, int n) Sample the given univariate real function on the given interval.static double[]
scaleArray
(double[] f, double d) Multiply every component in the given real array by the given real number.static Complex[]
scaleArray
(Complex[] f, double d) Multiply every component in the given complex array by the given real number.Complex[]
transform
(double[] f) Transform the given real data set.Complex[]
transform
(UnivariateRealFunction f, double min, double max, int n) Transform the given real function, sampled on the given interval.Complex[]
Transform the given complex data set.Complex[]
transform2
(double[] f) Transform the given real data set.Complex[]
transform2
(UnivariateRealFunction f, double min, double max, int n) Transform the given real function, sampled on the given interval.Complex[]
transform2
(Complex[] f) Transform the given complex data set.static void
verifyDataSet
(double[] d) Verifies that the data set has length of power of 2.static void
verifyDataSet
(Object[] o) Verifies that the data set has length of power of 2.static void
verifyInterval
(double lower, double upper) Verifies that the endpoints specify an interval.
-
Constructor Details
-
FastFourierTransformer
public FastFourierTransformer()Construct a default transformer.
-
-
Method Details
-
transform
Transform the given real data set.The formula is $ y_n = \Sigma_{k=0}^{N-1} e^{-2 \pi i nk/N} x_k $
- Parameters:
f
- the real data array to be transformed- Returns:
- the complex transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
transform
public Complex[] transform(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException Transform the given real function, sampled on the given interval.The formula is $ y_n = \Sigma_{k=0}^{N-1} e^{-2 \pi i nk/N} x_k $
- Parameters:
f
- the function to be sampled and transformedmin
- the lower bound for the intervalmax
- the upper bound for the intervaln
- the number of sample points- Returns:
- the complex transformed array
- Throws:
FunctionEvaluationException
- if function cannot be evaluated at some pointIllegalArgumentException
- if any parameters are invalid
-
transform
Transform the given complex data set.The formula is $ y_n = \Sigma_{k=0}^{N-1} e^{-2 \pi i nk/N} x_k $
- Parameters:
f
- the complex data array to be transformed- Returns:
- the complex transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
transform2
Transform the given real data set.The formula is $y_n = (1/\sqrt{N}) \Sigma_{k=0}^{N-1} e^{-2 \pi i nk/N} x_k$
- Parameters:
f
- the real data array to be transformed- Returns:
- the complex transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
transform2
public Complex[] transform2(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException Transform the given real function, sampled on the given interval.The formula is $y_n = (1/\sqrt{N}) \Sigma_{k=0}^{N-1} e^{-2 \pi i nk/N} x_k$
- Parameters:
f
- the function to be sampled and transformedmin
- the lower bound for the intervalmax
- the upper bound for the intervaln
- the number of sample points- Returns:
- the complex transformed array
- Throws:
FunctionEvaluationException
- if function cannot be evaluated at some pointIllegalArgumentException
- if any parameters are invalid
-
transform2
Transform the given complex data set.The formula is $y_n = (1/\sqrt{N}) \Sigma_{k=0}^{N-1} e^{-2 \pi i nk/N} x_k$
- Parameters:
f
- the complex data array to be transformed- Returns:
- the complex transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
inversetransform
Inversely transform the given real data set.The formula is $ x_k = (1/N) \Sigma_{n=0}^{N-1} e^{2 \pi i nk/N} y_n $
- Parameters:
f
- the real data array to be inversely transformed- Returns:
- the complex inversely transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
inversetransform
public Complex[] inversetransform(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException Inversely transform the given real function, sampled on the given interval.The formula is $ x_k = (1/N) \Sigma_{n=0}^{N-1} e^{2 \pi i nk/N} y_n $
- Parameters:
f
- the function to be sampled and inversely transformedmin
- the lower bound for the intervalmax
- the upper bound for the intervaln
- the number of sample points- Returns:
- the complex inversely transformed array
- Throws:
FunctionEvaluationException
- if function cannot be evaluated at some pointIllegalArgumentException
- if any parameters are invalid
-
inversetransform
Inversely transform the given complex data set.The formula is $ x_k = (1/N) \Sigma_{n=0}^{N-1} e^{2 \pi i nk/N} y_n $
- Parameters:
f
- the complex data array to be inversely transformed- Returns:
- the complex inversely transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
inversetransform2
Inversely transform the given real data set.The formula is $x_k = (1/\sqrt{N}) \Sigma_{n=0}^{N-1} e^{2 \pi i nk/N} y_n$
- Parameters:
f
- the real data array to be inversely transformed- Returns:
- the complex inversely transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
inversetransform2
public Complex[] inversetransform2(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException Inversely transform the given real function, sampled on the given interval.The formula is $x_k = (1/\sqrt{N}) \Sigma_{n=0}^{N-1} e^{2 \pi i nk/N} y_n$
- Parameters:
f
- the function to be sampled and inversely transformedmin
- the lower bound for the intervalmax
- the upper bound for the intervaln
- the number of sample points- Returns:
- the complex inversely transformed array
- Throws:
FunctionEvaluationException
- if function cannot be evaluated at some pointIllegalArgumentException
- if any parameters are invalid
-
inversetransform2
Inversely transform the given complex data set.The formula is $x_k = (1/\sqrt{N}) \Sigma_{n=0}^{N-1} e^{2 \pi i nk/N} y_n$
- Parameters:
f
- the complex data array to be inversely transformed- Returns:
- the complex inversely transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
fft
Perform the base-4 Cooley-Tukey FFT algorithm (including inverse).- Parameters:
f
- the real data array to be transformedisInverse
- the indicator of forward or inverse transform- Returns:
- the complex transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
fft
Perform the base-4 Cooley-Tukey FFT algorithm (including inverse).- Parameters:
data
- the complex data array to be transformed- Returns:
- the complex transformed array
- Throws:
IllegalArgumentException
- if any parameters are invalid
-
sample
public static double[] sample(UnivariateRealFunction f, double min, double max, int n) throws FunctionEvaluationException, IllegalArgumentException Sample the given univariate real function on the given interval.The interval is divided equally into N sections and sample points are taken from min to max-(max-min)/N. Usually f(x) is periodic such that f(min) = f(max) (note max is not sampled), but we don't require that.
- Parameters:
f
- the function to be sampledmin
- the lower bound for the intervalmax
- the upper bound for the intervaln
- the number of sample points- Returns:
- the samples array
- Throws:
FunctionEvaluationException
- if function cannot be evaluated at some pointIllegalArgumentException
- if any parameters are invalid
-
scaleArray
public static double[] scaleArray(double[] f, double d) Multiply every component in the given real array by the given real number. The change is made in place.- Parameters:
f
- the real array to be scaledd
- the real scaling coefficient- Returns:
- a reference to the scaled array
-
scaleArray
Multiply every component in the given complex array by the given real number. The change is made in place.- Parameters:
f
- the complex array to be scaledd
- the real scaling coefficient- Returns:
- a reference to the scaled array
-
isPowerOf2
public static boolean isPowerOf2(long n) Returns true if the argument is power of 2.- Parameters:
n
- the number to test- Returns:
- true if the argument is power of 2
-
verifyDataSet
Verifies that the data set has length of power of 2.- Parameters:
d
- the data array- Throws:
IllegalArgumentException
- if array length is not power of 2
-
verifyDataSet
Verifies that the data set has length of power of 2.- Parameters:
o
- the data array- Throws:
IllegalArgumentException
- if array length is not power of 2
-
verifyInterval
Verifies that the endpoints specify an interval.- Parameters:
lower
- lower endpointupper
- upper endpoint- Throws:
IllegalArgumentException
- if not interval
-
mdfft
Performs a multi-dimensional Fourier transform on a given array. Useinversetransform2(Complex[])
andtransform2(Complex[])
in a row-column implementation in any number of dimensions with O(N×log(N)) complexity with N=n1×n2×n3×...×nd, nx=number of elements in dimension x, and d=total number of dimensions.- Parameters:
mdca
- Multi-Dimensional Complex Array id est Complex[][][][]forward
- inverseTransform2 is preformed if this is false- Returns:
- transform of mdca as a Multi-Dimensional Complex Array id est Complex[][][][]
- Throws:
IllegalArgumentException
- if any dimension is not a power of two
-