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