Package org.apache.commons.math.transform

Class FastFourierTransformer

java.lang.Object

org.apache.commons.math.transform.FastFourierTransformer

All Implemented Interfaces:

java.io.Serializable

public class FastFourierTransformer
extends java.lang.Object
implements java.io.Serializable

Implements the Fast Fourier Transform for transformation of one-dimensional data sets. For reference, see Applied Numerical Linear Algebra, ISBN 0898713897, chapter 6.

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:

Serialized Form

Constructor Summary

Constructors

Constructor	Description
FastFourierTransformer()	Construct a default transformer.

Method Summary

Modifier and Type	Method	Description
protected Complex[]	fft(double[] f, boolean isInverse)	Perform the base-4 Cooley-Tukey FFT algorithm (including inverse).
protected Complex[]	fft(Complex[] data)	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.
java.lang.Object	mdfft(java.lang.Object mdca, boolean forward)	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(Complex[] f)	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(java.lang.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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FastFourierTransformer

public FastFourierTransformer()

Construct a default transformer.

Method Detail

transform

public Complex[] transform(double[] f)
                    throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

transform

public Complex[] transform(UnivariateRealFunction f,
                           double min,
                           double max,
                           int n)
                    throws FunctionEvaluationException,
                           java.lang.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 transformed

min - the lower bound for the interval

max - the upper bound for the interval

n - the number of sample points

Returns:

the complex transformed array

Throws:

FunctionEvaluationException - if function cannot be evaluated at some point

java.lang.IllegalArgumentException - if any parameters are invalid

transform

public Complex[] transform(Complex[] f)
                    throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

transform2

public Complex[] transform2(double[] f)
                     throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

transform2

public Complex[] transform2(UnivariateRealFunction f,
                            double min,
                            double max,
                            int n)
                     throws FunctionEvaluationException,
                            java.lang.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 transformed

min - the lower bound for the interval

max - the upper bound for the interval

n - the number of sample points

Returns:

the complex transformed array

Throws:

FunctionEvaluationException - if function cannot be evaluated at some point

java.lang.IllegalArgumentException - if any parameters are invalid

transform2

public Complex[] transform2(Complex[] f)
                     throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

inversetransform

public Complex[] inversetransform(double[] f)
                           throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

inversetransform

public Complex[] inversetransform(UnivariateRealFunction f,
                                  double min,
                                  double max,
                                  int n)
                           throws FunctionEvaluationException,
                                  java.lang.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 transformed

min - the lower bound for the interval

max - the upper bound for the interval

n - the number of sample points

Returns:

the complex inversely transformed array

Throws:

FunctionEvaluationException - if function cannot be evaluated at some point

java.lang.IllegalArgumentException - if any parameters are invalid

inversetransform

public Complex[] inversetransform(Complex[] f)
                           throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

inversetransform2

public Complex[] inversetransform2(double[] f)
                            throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

inversetransform2

public Complex[] inversetransform2(UnivariateRealFunction f,
                                   double min,
                                   double max,
                                   int n)
                            throws FunctionEvaluationException,
                                   java.lang.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 transformed

min - the lower bound for the interval

max - the upper bound for the interval

n - the number of sample points

Returns:

the complex inversely transformed array

Throws:

FunctionEvaluationException - if function cannot be evaluated at some point

java.lang.IllegalArgumentException - if any parameters are invalid

inversetransform2

public Complex[] inversetransform2(Complex[] f)
                            throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

fft

protected Complex[] fft(double[] f,
                        boolean isInverse)
                 throws java.lang.IllegalArgumentException

Perform the base-4 Cooley-Tukey FFT algorithm (including inverse).

Parameters:

f - the real data array to be transformed

isInverse - the indicator of forward or inverse transform

Returns:

the complex transformed array

Throws:

java.lang.IllegalArgumentException - if any parameters are invalid

fft

protected Complex[] fft(Complex[] data)
                 throws java.lang.IllegalArgumentException

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:

java.lang.IllegalArgumentException - if any parameters are invalid

sample

public static double[] sample(UnivariateRealFunction f,
                              double min,
                              double max,
                              int n)
                       throws FunctionEvaluationException,
                              java.lang.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 sampled

min - the lower bound for the interval

max - the upper bound for the interval

n - the number of sample points

Returns:

the samples array

Throws:

FunctionEvaluationException - if function cannot be evaluated at some point

java.lang.IllegalArgumentException - 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 scaled

d - the real scaling coefficient

Returns:

a reference to the scaled array

scaleArray

public static Complex[] scaleArray(Complex[] f,
                                   double d)

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 scaled

d - 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

public static void verifyDataSet(double[] d)
                          throws java.lang.IllegalArgumentException

Verifies that the data set has length of power of 2.

Parameters:

d - the data array

Throws:

java.lang.IllegalArgumentException - if array length is not power of 2

verifyDataSet

public static void verifyDataSet(java.lang.Object[] o)
                          throws java.lang.IllegalArgumentException

Verifies that the data set has length of power of 2.

Parameters:

o - the data array

Throws:

java.lang.IllegalArgumentException - if array length is not power of 2

verifyInterval

public static void verifyInterval(double lower,
                                  double upper)
                           throws java.lang.IllegalArgumentException

Verifies that the endpoints specify an interval.

Parameters:

lower - lower endpoint

upper - upper endpoint

Throws:

java.lang.IllegalArgumentException - if not interval

mdfft

public java.lang.Object mdfft(java.lang.Object mdca,
                              boolean forward)
                       throws java.lang.IllegalArgumentException

Performs a multi-dimensional Fourier transform on a given array. Use inversetransform2(Complex[]) and transform2(Complex[]) in a row-column implementation in any number of dimensions with O(N×log(N)) complexity with N=n₁×n₂×n₃×...×n_d, n_x=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:

java.lang.IllegalArgumentException - if any dimension is not a power of two