org.apache.commons.math3.transform

## Class FastFourierTransformer

- java.lang.Object
- - org.apache.commons.math3.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 real or complex data sets. For reference, see Applied Numerical Linear Algebra, ISBN 0898713897, chapter 6.

  There are several variants of the discrete Fourier transform, with various normalization conventions, which are specified by the parameter `DftNormalization`.

  The current implementation of the discrete Fourier transform as a fast Fourier transform requires the length of the data set to be a 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:
    $Id: FastFourierTransformer.java 1385310 2012-09-16 16:32:10Z tn $
  See Also:
    `DftNormalization`, Serialized Form

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `private static class` | `FastFourierTransformer.MultiDimensionalComplexMatrix` Deprecated. see MATH-736

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `private DftNormalization` | `normalization` The type of DFT to be performed.
    `(package private) static long` | `serialVersionUID` Serializable version identifier.
    `private static double[]` | `W_SUB_N_I` `W_SUB_N_I[i]` is the imaginary part of `exp(- 2 * i * pi / n)`: `W_SUB_N_I[i] = -sin(2 * pi/ n)`, where `n = 2^i`.
    `private static double[]` | `W_SUB_N_R` `W_SUB_N_R[i]` is the real part of `exp(- 2 * i * pi / n)`: `W_SUB_N_R[i] = cos(2 * pi/ n)`, where `n = 2^i`.

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `FastFourierTransformer(DftNormalization normalization)` Creates a new instance of this class, with various normalization conventions.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `private static void` | `bitReversalShuffle2(double[] a, double[] b)` Performs identical index bit reversal shuffles on two arrays of identical size.
    `private void` | `mdfft(FastFourierTransformer.MultiDimensionalComplexMatrix mdcm, TransformType type, int d, int[] subVector)` Deprecated. see MATH-736
    `java.lang.Object` | `mdfft(java.lang.Object mdca, TransformType type)` Deprecated. see MATH-736
    `private static void` | `normalizeTransformedData(double[][] dataRI, DftNormalization normalization, TransformType type)` Applies the proper normalization to the specified transformed data.
    `Complex[]` | `transform(Complex[] f, TransformType type)` Returns the (forward, inverse) transform of the specified complex data set.
    `Complex[]` | `transform(double[] f, TransformType type)` Returns the (forward, inverse) transform of the specified real data set.
    `Complex[]` | `transform(UnivariateFunction f, double min, double max, int n, TransformType type)` Returns the (forward, inverse) transform of the specified real function, sampled on the specified interval.
    `static void` | `transformInPlace(double[][] dataRI, DftNormalization normalization, TransformType type)` Computes the standard transform of the specified complex data.

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

    - #### W_SUB_N_R

          private static final double[] W_SUB_N_R

      `W_SUB_N_R[i]` is the real part of `exp(- 2 * i * pi / n)`: `W_SUB_N_R[i] = cos(2 * pi/ n)`, where `n = 2^i`.

    - #### W_SUB_N_I

          private static final double[] W_SUB_N_I

      `W_SUB_N_I[i]` is the imaginary part of `exp(- 2 * i * pi / n)`: `W_SUB_N_I[i] = -sin(2 * pi/ n)`, where `n = 2^i`.

    - #### normalization

          private final DftNormalization normalization

      The type of DFT to be performed.

  - ### Constructor Detail

    - #### FastFourierTransformer

          public FastFourierTransformer(DftNormalization normalization)

      Creates a new instance of this class, with various normalization conventions.
      Parameters:
        `normalization` - the type of normalization to be applied to the transformed data

  - ### Method Detail

    - #### bitReversalShuffle2

          private static void bitReversalShuffle2(double[] a,
                                 double[] b)

      Performs identical index bit reversal shuffles on two arrays of identical size. Each element in the array is swapped with another element based on the bit-reversal of the index. For example, in an array with length 16, item at binary index 0011 (decimal 3) would be swapped with the item at binary index 1100 (decimal 12).
      Parameters:
        `a` - the first array to be shuffled
        `b` - the second array to be shuffled

    - #### normalizeTransformedData

          private static void normalizeTransformedData(double[][] dataRI,
                                      DftNormalization normalization,
                                      TransformType type)

      Applies the proper normalization to the specified transformed data.
      Parameters:
        `dataRI` - the unscaled transformed data
        `normalization` - the normalization to be applied
        `type` - the type of transform (forward, inverse) which resulted in the specified data

    - #### transformInPlace

          public static void transformInPlace(double[][] dataRI,
                              DftNormalization normalization,
                              TransformType type)

      Computes the standard transform of the specified complex data. The computation is done in place. The input data is laid out as follows
      - `dataRI[0][i]` is the real part of the `i`-th data point,
      - `dataRI[1][i]` is the imaginary part of the `i`-th data point.
      Parameters:
        `dataRI` - the two dimensional array of real and imaginary parts of the data
        `normalization` - the normalization to be applied to the transformed data
        `type` - the type of transform (forward, inverse) to be performed
      Throws:
        `DimensionMismatchException` - if the number of rows of the specified array is not two, or the array is not rectangular
        `MathIllegalArgumentException` - if the number of data points is not a power of two

    - #### transform

          public Complex[] transform(double[] f,
                            TransformType type)

      Returns the (forward, inverse) transform of the specified real data set.
      Parameters:
        `f` - the real data array to be transformed
        `type` - the type of transform (forward, inverse) to be performed
      Returns:
        the complex transformed array
      Throws:
        `MathIllegalArgumentException` - if the length of the data array is not a power of two

    - #### transform

          public Complex[] transform(UnivariateFunction f,
                            double min,
                            double max,
                            int n,
                            TransformType type)

      Returns the (forward, inverse) transform of the specified real function, sampled on the specified interval.
      Parameters:
        `f` - the function to be sampled and transformed
        `min` - the (inclusive) lower bound for the interval
        `max` - the (exclusive) upper bound for the interval
        `n` - the number of sample points
        `type` - the type of transform (forward, inverse) to be performed
      Returns:
        the complex transformed array
      Throws:
        `NumberIsTooLargeException` - if the lower bound is greater than, or equal to the upper bound
        `NotStrictlyPositiveException` - if the number of sample points `n` is negative
        `MathIllegalArgumentException` - if the number of sample points `n` is not a power of two

    - #### transform

          public Complex[] transform(Complex[] f,
                            TransformType type)

      Returns the (forward, inverse) transform of the specified complex data set.
      Parameters:
        `f` - the complex data array to be transformed
        `type` - the type of transform (forward, inverse) to be performed
      Returns:
        the complex transformed array
      Throws:
        `MathIllegalArgumentException` - if the length of the data array is not a power of two

    - #### mdfft

          @Deprecated
          public java.lang.Object mdfft(java.lang.Object mdca,
                                          TransformType type)

      Deprecated. see MATH-736
      Performs a multi-dimensional Fourier transform on a given array. Use `transform(Complex[], TransformType)` in a row-column implementation in any number of dimensions with O(N×log(N)) complexity with N = n1 × n2 ×n3 × ... × nd, where nk is the number of elements in dimension k, and d is the total number of dimensions.
      Parameters:
        `mdca` - Multi-Dimensional Complex Array, i.e. `Complex[][][][]`
        `type` - the type of transform (forward, inverse) to be performed
      Returns:
        transform of `mdca` as a Multi-Dimensional Complex Array, i.e. `Complex[][][][]`
      Throws:
        `java.lang.IllegalArgumentException` - if any dimension is not a power of two

    - #### mdfft

          @Deprecated
          private void mdfft(FastFourierTransformer.MultiDimensionalComplexMatrix mdcm,
                              TransformType type,
                              int d,
                              int[] subVector)

      Deprecated. see MATH-736
      Performs one dimension of a multi-dimensional Fourier transform.
      Parameters:
        `mdcm` - input matrix
        `type` - the type of transform (forward, inverse) to be performed
        `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-2013 Apache Software Foundation