## 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: 885278 $ $Date: 2009-11-29 16:47:51 -0500 (Sun, 29 Nov 2009) $
See Also:
  Serialized Form

Nested Class Summary
`private static class` `FastFourierTransformer.MultiDimensionalComplexMatrix` Complex matrix implementation.
`private static class` `FastFourierTransformer.RootsOfUnity` Computes the nth roots of unity.

Field Summary
`private static java.lang.String` `DIMENSION_MISMATCH_MESSAGE` Message for dimension mismatch.
`private static java.lang.String` `MISSING_ROOTS_OF_UNITY_MESSAGE` Message for not computed roots of unity.
`private static java.lang.String` `NOT_POWER_OF_TWO_MESSAGE` Message for not power of 2.
`private static java.lang.String` `OUT_OF_RANGE_ROOT_INDEX_MESSAGE` Message for out of range root index.
`private FastFourierTransformer.RootsOfUnity` `roots` roots of unity
`(package private) static long` `serialVersionUID` Serializable version identifier.

Constructor Summary
`FastFourierTransformer()` Construct a default transformer.

Method Summary
`protected Complex[]` `fft(Complex[] data)` Perform the base-4 Cooley-Tukey FFT algorithm (including inverse).
`protected Complex[]` `fft(double[] f, boolean isInverse)` Perform the base-4 Cooley-Tukey FFT algorithm (including inverse).
`Complex[]` `inversetransform(Complex[] f)` Inversely transform the given complex data set.
`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[]` `inversetransform2(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.
`static boolean` `isPowerOf2(long n)` Returns true if the argument is power of 2.
`private void` `mdfft(FastFourierTransformer.MultiDimensionalComplexMatrix mdcm, boolean forward, int d, int[] subVector)` Performs one dimension of a multi-dimensional Fourier transform.
`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 Complex[]` `scaleArray(Complex[] f, double d)` Multiply every component in the given complex array by the given real number.
`static double[]` `scaleArray(double[] f, double d)` Multiply every component in the given real array by the given real number.
`Complex[]` `transform(Complex[] f)` Transform the given complex data set.
`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[]` `transform2(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.
`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`

Field Detail

### serialVersionUID

    static final long serialVersionUID

  Serializable version identifier.

  See Also:
    Constant Field Values

### NOT_POWER_OF_TWO_MESSAGE

    private static final java.lang.String NOT_POWER_OF_TWO_MESSAGE

  Message for not power of 2.

  See Also:
    Constant Field Values

### DIMENSION_MISMATCH_MESSAGE

    private static final java.lang.String DIMENSION_MISMATCH_MESSAGE

  Message for dimension mismatch.

  See Also:
    Constant Field Values

### MISSING_ROOTS_OF_UNITY_MESSAGE

    private static final java.lang.String MISSING_ROOTS_OF_UNITY_MESSAGE

  Message for not computed roots of unity.

  See Also:
    Constant Field Values

### OUT_OF_RANGE_ROOT_INDEX_MESSAGE

    private static final java.lang.String OUT_OF_RANGE_ROOT_INDEX_MESSAGE

  Message for out of range root index.

  See Also:
    Constant Field Values

### roots

    private FastFourierTransformer.RootsOfUnity roots

  roots of unity

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=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:
    `java.lang.IllegalArgumentException` - if any dimension is not a power of two

### mdfft

    private void mdfft(FastFourierTransformer.MultiDimensionalComplexMatrix mdcm,
                       boolean forward,
                       int d,
                       int[] subVector)
                throws java.lang.IllegalArgumentException

  Performs one dimension of a multi-dimensional Fourier transform.

  Parameters:
    `mdcm` - input matrix
    `forward` - inverseTransform2 is preformed if this is false
    `d` - index of the dimension to process
    `subVector` - recursion subvector
  Throws:
    `java.lang.IllegalArgumentException` - if any dimension is not a power of two

Copyright (c) 2003-2011 Apache Software Foundation