Class FFT

java.lang.Object
org.bzdev.math.FFT

public abstract class FFT extends Object
Fast Fourier Transform. This class uses an SPI (Service Provider Interface) to support multiple FFT implementations. The default implementation can be set by setting the system property org.bzdev.math.fft.provider to the name of the provider. If this is not set, the default name is bzdevFFT and is equivalent to

    java -Dorg.bzdev.math.fft=bzdevFFT ...
 

The method getServiceName(int,boolean,FFT.LMode) can be used to select a service provider. Alternatively, the method serviceProviders() will provide a set of all the available service-provider names. The methods newInstance(int) and newInstance(int,FFT.Mode) will create an instance of FFT using the default service provider. The first argument for these methods should be a length returned by getLength(int) or getLength(String,int). The integer argument for these methods is a desired array length and the value returned is the smallest length an FFT provider supports that is at least as large as the length specified by the integer argument. Similarly, the methods newInstance(String,int) and newInstance(String,int,FFT.Mode) will create an instance of FFT using a service provider provider whose name matches the these method's first argument.

FFTProvider describes how to write an FFT provider. The default provider requires that the array lengths are powers of 2.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    Factory class for creating FFT instances that satisfy various criteria.
    static enum 
    FFT length mode.
    static enum 
    FFT normalization mode.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Constructor.
  • Method Summary

    Modifier and Type
    Method
    Description
    static void
    convolve(double[] f, double[] g, int zeroOffset, double[] result)
    Convolution.
    static void
    convolve(FFT.Factory fftf, double[] f, double[] g, int zeroOffset, double[] result)
    Convolution specifying an FFT factory.
    static void
    crossCorrelate(double[] f, double[] g, double[] result)
    Cross correlation.
    static void
    crossCorrelate(FFT.Factory fftf, double[] f, double[] g, double[] result)
    Cross correlation specifying an FFT factory.
    static void
    cyclicConvolve(double[] f, double[] g, int zeroOffset, double[] result)
    Cyclic Convolution.
    static void
    cyclicConvolve(FFT.Factory fftf, double[] f, double[] g, int zeroOffset, double[] result)
    Cyclic Convolution, specifying an FFT factory.
    static void
    cyclicCrossCorrelate(double[] f, double[] g, double[] result)
    Cyclic cross correlation.
    static void
    cyclicCrossCorrelate(FFT.Factory fftf, double[] f, double[] g, double[] result)
    Cyclic cross correlation, specifying an FFT factory.
    abstract int
    Get the length that this instance of FFT supports.
    static int
    getLength(int n)
    Get the closest length supported by the default FFT provider for a specified length.
    static int
    getLength(String name, int n)
    Get the closest length supported by an FFT provider for a specified length.
    static int
    Get the maximum length that the default FFT provider supports.
    static int
    getMaxLength(boolean inplace)
    Get the largest array length that some FFT provider supports subject to an optional in-place constraint
    static int
    Get the maximum length that an FFT provider supports.
    final FFT.Mode
    Get the mode for this transform
    static String
    getServiceName(int length, boolean inplace, FFT.LMode lmode)
    Get the name of an FFT provider.
    abstract boolean
    Determine if this FFT instance supports in-place transforms.
    static boolean
    Determine if the default provider supports in-place transforms for all supported input array lengths.
    static boolean
    Determine if the default provider supports in-place transforms for a specific input array length.
    static boolean
    Determine if an FFT provider supports in-place transforms for all supported input array lengths.
    static boolean
    inplaceSupported(String name, int n)
    Determine if an FFT provider supports in-place transforms for a specific supported input array length.
    abstract void
    inverse(double[] xiReal, double[] xiImag, double[] xoReal, double[] xoImag)
    Compute an inverse FFT.
    static FFT
    newInstance(int n)
    Create a new instance of the FFT class using the default FFT provider with the default mode (FFT.Mode.SYMMETRIC).
    static FFT
    newInstance(int n, FFT.Mode m)
    Create a new instance of the FFT class using the default FFT provider with a specified mode.
    static FFT
    newInstance(String name, int n)
    Create a new instance of the FFT class using a named FFT provider with the default mode.
    static FFT
    newInstance(String name, int n, FFT.Mode m)
    Create a new instance of the FFT class using a named FFT provider with a specified mode.
    static FFT
    Create a new instance of the FFT class based on an existing FFT instance but with a new mode.
    static Set<String>
    Get the service-provider names of all FFT providers on the class path.
    abstract void
    transform(double[] xiReal, double[] xiImag, double[] xoReal, double[] xoImag)
    Compute an FFT.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • FFT

      protected FFT(FFT.Mode m)
      Constructor.
      Parameters:
      m - the mode for the transform
  • Method Details

    • serviceProviders

      public static Set<String> serviceProviders()
      Get the service-provider names of all FFT providers on the class path.
      Returns:
      a set of service-provider names
    • getServiceName

      public static String getServiceName(int length, boolean inplace, FFT.LMode lmode)
      Get the name of an FFT provider. This name can be used as the first argument of the methods newInstance(String,int) and newInstance(String,int,Mode). When the lmode argument has the value FFT.LMode.MAX_LENGTH and the inplace argument's value is true, the FTP provider must support in-place transforms for all of the array lengths it supports. When the lmode argument's value is FFT.LMode.DESIRED_LENGTH and the inplace argument's value is true, the FFT provider must support in-place transforms for the lowest supported length larger than the specified length. When the lmode argument's value is FFT.LMode.EXACT_LENGTH and the in place argument's value is true, the FFT provider must support in-place transforms for the length that was specified.
      Parameters:
      length - the maximum or desired length of the arrays storing the real or imaginary components used for input or output.
      inplace - true if the user requires an FFT implementation that computes a transform or its inverse in place; false otherwise
      lmode - FFT.LMode.DESIRED_LENGTH if the length argument represents a desired length; FFT.LMode.MAX_LENGTH if the length argument is an upper bound on the array lengths; FFT.LMode.EXACT_LENGTH if the length argument represents a specific length
      Returns:
      the name of an FFT service; null if none meet the constraints imposed by the arguments
    • getMaxLength

      public static int getMaxLength(boolean inplace)
      Get the largest array length that some FFT provider supports subject to an optional in-place constraint
      Parameters:
      inplace - true if an FFT must be able to use the same vectors for input and ouput; false otherwise.
      Returns:
      the array length limit
    • getLength

      public static int getLength(int n)
      Get the closest length supported by the default FFT provider for a specified length.
      Parameters:
      n - the specified length
      Returns:
      the closest length that is supported and that is larger than the specified length
    • getLength

      public static int getLength(String name, int n) throws IllegalArgumentException
      Get the closest length supported by an FFT provider for a specified length.
      Parameters:
      name - the name of the FFT provider
      n - the specified length
      Returns:
      the closest length that is supported and that is larger than the specified length
      Throws:
      IllegalArgumentException
    • inplaceSupported

      public static boolean inplaceSupported()
      Determine if the default provider supports in-place transforms for all supported input array lengths.
      Returns:
      true if the default provider supports in-place transforms; false otherwise
    • inplaceSupported

      public static boolean inplaceSupported(int n)
      Determine if the default provider supports in-place transforms for a specific input array length.
      Parameters:
      n - the length of the input and output arrays
      Returns:
      true if the default provider supports in-place transforms; false otherwise
    • inplaceSupported

      public static boolean inplaceSupported(String name) throws IllegalArgumentException
      Determine if an FFT provider supports in-place transforms for all supported input array lengths.
      Parameters:
      name - the name of the provider
      Returns:
      true if the provider supports in-place transforms; false otherwise
      Throws:
      IllegalArgumentException
    • inplaceSupported

      public static boolean inplaceSupported(String name, int n) throws IllegalArgumentException
      Determine if an FFT provider supports in-place transforms for a specific supported input array length.
      Parameters:
      name - the name of the provider
      n - the length of the input and output arrays
      Returns:
      true if the provider supports in-place transforms; false otherwise
      Throws:
      IllegalArgumentException
    • inplace

      public abstract boolean inplace()
      Determine if this FFT instance supports in-place transforms.
      Returns:
      true if this FFT in-place transforms; false otherwise
    • getMaxLength

      public static int getMaxLength()
      Get the maximum length that the default FFT provider supports.
      Returns:
      the maximum length
    • getMaxLength

      public static int getMaxLength(String name)
      Get the maximum length that an FFT provider supports.
      Parameters:
      name - the name of the FFT provider
      Returns:
      the maximum length
    • newInstance

      public static FFT newInstance(int n)
      Create a new instance of the FFT class using the default FFT provider with the default mode (FFT.Mode.SYMMETRIC). The length must be one that the FFT provider supports.
      Parameters:
      n - the length of the input and output arrays
      Returns:
      a new FFT
      See Also:
    • newInstance

      public static FFT newInstance(int n, FFT.Mode m)
      Create a new instance of the FFT class using the default FFT provider with a specified mode. The length must be one that the FFT provider supports.
      Parameters:
      n - the length of the input and output arrays
      m - the mode (FFT.Mode.NORMAL, FFT.Mode.SYMMETRIC, or FFT.Mode.REVERSED)
      Returns:
      the new FFT
      See Also:
    • newInstance

      public static FFT newInstance(String name, int n)
      Create a new instance of the FFT class using a named FFT provider with the default mode. The length must be one that the FFT provider supports.
      Parameters:
      name - the name of the FFT provider
      n - the length of the input and output arrays
      Returns:
      the new FFT
      See Also:
    • newInstance

      public static FFT newInstance(String name, int n, FFT.Mode m)
      Create a new instance of the FFT class using a named FFT provider with a specified mode. The length must be one that the FFT provider supports.
      Parameters:
      name - the name of the FFT provider
      n - the length of the input and output arrays
      m - the mode (FFT.Mode.NORMAL, FFT.Mode.SYMMETRIC, or FFT.Mode.REVERSED)
      Returns:
      the new FFT
      See Also:
    • newInstance

      public static FFT newInstance(FFT fft, FFT.Mode m)
      Create a new instance of the FFT class based on an existing FFT instance but with a new mode.
      Parameters:
      fft - an existing FFT instance
      m - the mode (FFT.Mode.NORMAL, FFT.Mode.SYMMETRIC, or FFT.Mode.REVERSED)
      Returns:
      the new FFT
      See Also:
    • getMode

      public final FFT.Mode getMode()
      Get the mode for this transform
      Returns:
      the mode
      See Also:
    • getLength

      public abstract int getLength()
      Get the length that this instance of FFT supports.
      Returns:
      the length of the input and output arrays that are passed to transform(double[],double[], double[],double[]) or inverse(double[],double[], double[],double[])
    • transform

      public abstract void transform(double[] xiReal, double[] xiImag, double[] xoReal, double[] xoImag) throws IllegalArgumentException
      Compute an FFT. The transform is defined by Xk = F∑n ∈[0,N) xne-i2πkn/N. where
      • F = 1 when the transform was created with a mode of FFT.Mode.NORMAL.
      • F =1/√N when the transform was created with a mode of FFT.Mode.SYMMETRIC.
      • F = 1/N when the transform was created with a mode of FFT.Mode.REVERSED.
      • N is the length of the argument arrays

      The arrays xiReal and xoReal may be the same array, as may the arrays xiImag and xoImag. If the transform is not an in-place transform, the implementation must specifically handle this case.

      Parameters:
      xiReal - the real components of the input values
      xiImag - the imaginary components of the input values
      xoReal - the real components of the output values
      xoImag - the imaginary components of the output values
      Throws:
      IllegalArgumentException - an array does not have the required length
    • inverse

      public abstract void inverse(double[] xiReal, double[] xiImag, double[] xoReal, double[] xoImag) throws IllegalArgumentException
      Compute an inverse FFT. The inverse transform is defined by xn = F∑k ∈[0,N) Xkei2πkn/N. where
      • F = 1/N when the transform was created with a mode of FFT.Mode.NORMAL.
      • F =1/√N when the transform was created with a mode of FFT.Mode.SYMMETRIC.
      • F = 1 when the transform was created with a mode of FFT.Mode.REVERSED.
      • N is the length of the argument arrays

      The arrays xiReal and xoReal may be the same array, as may the arrays xiImag and xoImag. If the transform is not an in-place transform, the implementation must specifically handle this case.

      Parameters:
      xiReal - the real components of the input values
      xiImag - the imaginary components of the input values
      xoReal - the real components of the output values
      xoImag - the imaginary components of the output values
      Throws:
      IllegalArgumentException - an array does not have the required length
    • convolve

      public static void convolve(double[] f, double[] g, int zeroOffset, double[] result) throws IllegalArgumentException
      Convolution. For continuous, real-valued functions, a convolution is defined as (f∗g)(t) = ∫ f(τ)g(t-τ) dτ. The discrete analog of this equation is Ck = ∑fig(k-i) The values for fi and gk-i are assumed to be zero except when i∈[0,N) and (k-i)∈[-L,M-L) where L is the value of zeroOffset. For convenience g can be represented by a vector of length Ng, the signed index covers the range [-z,Ng-z) while an unsigned index covers the range [0, Ng).

      See http://www.aip.de/groups/soe/local/numres/bookfpdf/f13-1.pdf for an explanation of how this convolution can be computed using an FFT.

      Parameters:
      f - a vector of values of length N
      g - a vector of values of length M with an offset z so that signed indices cover the range [-z, M-z).
      zeroOffset - the offset into the array g corresponding to a signed index of 0
      result - a vector of values of length N
      Throws:
      IllegalArgumentException - an array size was incorrect or an argument was out of range
    • convolve

      public static void convolve(FFT.Factory fftf, double[] f, double[] g, int zeroOffset, double[] result) throws IllegalArgumentException
      Convolution specifying an FFT factory. For continuous, real-valued functions, a convolution is defined as (f∗g)(t) = ∫ f(τ)g(t-τ) dτ. The discrete analog of this equation is Ck = ∑fig(k-i) The values for fi and gk-i are assumed to be zero except when i∈[0,N) and (k-i)∈[-L,M-L) where L is the value of zeroOffset. For convenience g can be represented by a vector of length Ng, the signed index covers the range [-z,Ng-z) while an unsigned index covers the range [0, Ng).

      See http://www.aip.de/groups/soe/local/numres/bookfpdf/f13-1.pdf for an explanation of how this convolution can be computed using an FFT.

      Parameters:
      fftf - the FFT factory used to create the FFT implementation
      f - a vector of values of length N
      g - a vector of values of length M with an offset z so that signed indices cover the range [-z, M-z).
      zeroOffset - the offset into the array g corresponding to a signed index of 0
      result - a vector of values of length N
      Throws:
      IllegalArgumentException - an array size was incorrect or an argument was out of range
    • cyclicConvolve

      public static void cyclicConvolve(double[] f, double[] g, int zeroOffset, double[] result) throws IllegalArgumentException
      Cyclic Convolution. For continuous, real-valued functions, a convolution is defined as (f∗g)(t) = ∫ f(τ)g(t-τ) dτ. The discrete analog of this equation is Ck = ∑fig(k-i) The values for fi and gk-i are assumed to be zero except when i∈[0,N) and (k-i)∈[-L,M-L) where L is the value of zeroOffset. For convenience g can be represented by a vector of length Ng, the signed index covers the range [-z,Ng-z) while an unsigned index covers the range [0, Ng).

      See http://www.aip.de/groups/soe/local/numres/bookfpdf/f13-1.pdf for an explanation of how this convolution can be computed using an FFT.

      Parameters:
      f - a vector of values of length N
      g - a vector of values of length M with an offset z so that signed indices cover the range [-z, M-z).
      zeroOffset - the offset into the array g corresponding to a signed index of 0
      result - a vector of values of length N
      Throws:
      IllegalArgumentException - an array size was incorrect or an argument was out of range
    • cyclicConvolve

      public static void cyclicConvolve(FFT.Factory fftf, double[] f, double[] g, int zeroOffset, double[] result) throws IllegalArgumentException
      Cyclic Convolution, specifying an FFT factory. For continuous, real-valued functions, a convolution is defined as (f∗g)(t) = ∫ f(τ)g(t-τ) dτ. The discrete analog of this equation is Ck = ∑fig(k-i) The values for fi and gk-i are assumed to be zero except when i∈[0,N) and (k-i)∈[-L,M-L) where L is the value of zeroOffset. For convenience g can be represented by a vector of length Ng, the signed index covers the range [-z,Ng-z) while an unsigned index covers the range [0, Ng).

      See http://www.aip.de/groups/soe/local/numres/bookfpdf/f13-1.pdf for an explanation of how this convolution can be computed using an FFT.

      Parameters:
      fftf - the FFT factory used to create the FFT implementation
      f - a vector of values of length N
      g - a vector of values of length M with an offset z so that signed indices cover the range [-z, M-z).
      zeroOffset - the offset into the array g corresponding to a signed index of 0
      result - a vector of values of length N
      Throws:
      IllegalArgumentException - an array size was incorrect or an argument was out of range
    • crossCorrelate

      public static void crossCorrelate(double[] f, double[] g, double[] result) throws IllegalArgumentException
      Cross correlation. For continuous, real-valued functions, a cross correlation is defined as (f★g)(t) = ∫ f(τ)g(t+τ) dτ. The discrete analog of this equation is Ck = ∑fig(k+i) The values for fi and gk+i are assumed to be zero except within the range of indices [0,N) and [0,M) respectively, where N is the length of the vector f and M is the length of the vector g. For the result vector, index 0 corresponds to k = 1-N, and its index N+M-2 corresponds to k = M-1. The index M-1 corresponds to k = 0.

      See http://www.aip.de/groups/soe/local/numres/bookfpdf/f13-1.pdf for an explanation of how s convolution can be computed using an FFT. This applies as well to a cross correlation, however, the position of the array g is shifted compared to the position used in a convolution.

      Parameters:
      f - a vector of values of length N
      g - a vector of values of length M.
      result - a vector of values of length N + M - 1 that will contain the cross correlation of f and g
      Throws:
      IllegalArgumentException - an array size was incorrect
    • crossCorrelate

      public static void crossCorrelate(FFT.Factory fftf, double[] f, double[] g, double[] result) throws IllegalArgumentException
      Cross correlation specifying an FFT factory. For continuous, real-valued functions, a cross correlation is defined as (f★g)(t) = ∫ f(τ)g(t+τ) dτ. The discrete analog of this equation is Ck = ∑fig(k+i) The values for fi and gk+i are assumed to be zero except within the range of indices [0,N) and [0,M) respectively, where N is the length of the vector f and M is the length of the vector g. For the result vector, index 0 corresponds to k = 1-N, and its index N+M-2 corresponds to k = M-1. The index M-1 corresponds to k = 0.

      See http://www.aip.de/groups/soe/local/numres/bookfpdf/f13-1.pdf for an explanation of how s convolution can be computed using an FFT. This applies as well to a cross correlation, however, the position of the array g is shifted compared to the position used in a convolution.

      Parameters:
      fftf - the FFT factory used to create the FFT implementation
      f - a vector of values of length N
      g - a vector of values of length M.
      result - a vector of values of length N + M - 1 that will contain the cross correlation of f and g
      Throws:
      IllegalArgumentException - an array size was incorrect
    • cyclicCrossCorrelate

      public static void cyclicCrossCorrelate(double[] f, double[] g, double[] result) throws IllegalArgumentException
      Cyclic cross correlation. For continuous, real-valued functions, a cross correlation is defined as (f★g)(t) = ∫ f(τ)g(t+τ) dτ. The discrete analog of this equation is Ck = ∑fig(k+i) The values for fi and gk+i are assumed to be zero except within the range of indices [0,N) and [0,M) respectively, where N is the length of the vector f and M is the length of the vector g. For the result vector, index 0 corresponds to k = 1-N, and its index N+M-2 corresponds to k = M-1. The index M-1 corresponds to k = 0.

      See http://www.aip.de/groups/soe/local/numres/bookfpdf/f13-1.pdf for an explanation of how s convolution can be computed using an FFT. This applies as well to a cross correlation, however, the position of the array g is shifted compared to the position used in a convolution.

      Parameters:
      f - a vector of values of length N
      g - a vector of values of length M.
      result - a vector of values of length N that will contain the cross correlation of f and g
      Throws:
      IllegalArgumentException - an array size was incorrect
    • cyclicCrossCorrelate

      public static void cyclicCrossCorrelate(FFT.Factory fftf, double[] f, double[] g, double[] result) throws IllegalArgumentException
      Cyclic cross correlation, specifying an FFT factory. For continuous, real-valued functions, a cross correlation is defined as (f★g)(t) = ∫ f(τ)g(t+τ) dτ. The discrete analog of this equation is Ck = ∑fig(k+i) The values for fi and gk+i are assumed to be zero except within the range of indices [0,N) and [0,M) respectively, where N is the length of the vector f and M is the length of the vector g. For the result vector, index 0 corresponds to k = 1-N, and its index N+M-2 corresponds to k = M-1. The index M-1 corresponds to k = 0.

      See http://www.aip.de/groups/soe/local/numres/bookfpdf/f13-1.pdf for an explanation of how s convolution can be computed using an FFT. This applies as well to a cross correlation, however, the position of the array g is shifted compared to the position used in a convolution.

      Parameters:
      fftf - the FFT factory used to create the FFT implementation
      f - a vector of values of length N
      g - a vector of values of length M.
      result - a vector of values of length N that will contain the cross correlation of f and g
      Throws:
      IllegalArgumentException - an array size was incorrect