Package net.algart.matrices.spectra

Class FastFourierTransform

java.lang.Object
net.algart.matrices.spectra.AbstractSpectralTransform
net.algart.matrices.spectra.FastFourierTransform
All Implemented Interfaces:
SpectralTransform
public class FastFourierTransform extends AbstractSpectralTransform implements SpectralTransform

Fast Fourier transform (FFT). This class implements traditional one- and multidimensional FFT algorithm over an abstract SampleArray and 1-, 2- or multidimensional AlgART numeric matrices. All samples must be complex to be processed by this class (areComplexSamplesRequired() method returns true). For needs of spectral processing real arrays and matrices, in most cases you should use SeparableFastHartleyTransform class.

More precisely, this class implements the classic fast "butterfly" algorithm (FFT) for calculating discrete Fourier transform (DFT), described at http://en.wikipedia.org/wiki/Discrete_Fourier_transform.

Namely, let x0,x1,...,xN−1 are some complex samples (represented by abstract SampleArray), and F0,F1,...,FN−1 are their Fourier spectrum: the result of DFT. Let i is the usual imaginary unit. This class implements two possible definitions of DFT:

  1. direct transform is Fk = ∑(0≤n<N) xne−2knπi/N, inverse transform is xn = N −1 ∑(0≤k<N) Fke2knπi/N.
  2. direct transform is Fk = N −1 ∑(0≤n<N) xne−2knπi/N, inverse transform is xn = ∑(0≤k<N) Fke2knπi/N;

The only difference is when to normalize the result: while inverse transform (case 1) or direct transform (case 2). The Wikipedia offers formulas of the 1st case. This class allows to calculate both variants: the 1st case is chosen if the normalizeDirectTransform argument of the constructors is false or if this class is created by a constructor without this argument (it is the default behaviour), the 2nd case is chosen if the normalizeDirectTransform argument of the constructors is true.

The formulas above correspond to one-dimensional transforms and specify the results of directTransform / inverseTransform methods. They are generalized to multidimensional case by default algorithms, implemented in AbstractSpectralTransform class, i.e. by applying the transform separably to each dimension. It is the traditional way of multidimensional generalizing Fourier transformations.

One-dimensional Fourier transform, defined by the formulas above, complies with the convolution theorem. Namely, let p0,p1,...,pN−1 is the first complex numeric function, q0,q1,...,qN−1 is the second function, and c0,c1,...,cN−1 is their convolution, defined as:

ck = ∑(0≤n<N) pnq(k−n) mod N

(here (k−n) mod N means (k−n<0 ? k−n+N : k−n)). Also, let P0,P1,...,PN−1, Q0,Q1,...,QN−1 and C0,C1,...,CN−1 are Fourier spectra of these functions. Then:

  1. Ck = PkQk (usual complex product of complex numbers Pk and Qk), if the spectra were calculated according formula 1 above (default method);
  2. Ck = NPkQk, if the spectra were calculated according formula 2 above.

The similar formulas are correct for any number of dimensions: convolution of samples corresponds to complex product of spectra.

This class contains the method spectrumOfConvolution(ArrayContext, Matrix, Matrix, Matrix, Matrix, Matrix, Matrix), which calculates a spectrum of convolution C for the given spectra P and Q of two source numeric matrices x and y according the formula A (and its generalization for any number of dimensions).

Please note: in the one-dimensional case, the spectral transofmation algorithms, implemented by directTransformMatrix / inverseTransformMatrix methods of this class, work with normal (i.e. high) performance only if the passed one-dimensional AlgART matrices are stored in SimpleMemoryModel (more precisely, if they are directly accessible). In other case, each access to every sample leads to calling accessing methods getDouble and setDouble, which can work slowly in non-simple memory models like LargeMemoryModel. There is the same problem for directTransform / inverseTransform methods, if the passed sample arrays are created via RealScalarSampleArray.asSampleArray or ComplexScalarSampleArray.asSampleArray methods on the base of updatable AlgART arrays, created by memory model other than SimpleMemoryModel.

For n-dimensional matrices (n≥2), this problem usually does not occur at all, even for non-simple memory models, if you use standard implementations of directTransformMatrix / inverseTransformMatrix from AbstractSpectralTransform class: these implementations automatically download necessary parts of the matrix into SimpleMemoryModel. This problem also does not occur while using spectrumOfConvolution(ArrayContext, Matrix, Matrix, Matrix, Matrix, Matrix, Matrix) method, if all processed matrices have the same float or double element types.

Author:
Daniel Alievsky

  • Constructor Details

    • FastFourierTransform

      public FastFourierTransform()
      Creates a new instance of this class, performing Fourier transform according to the formula 1 from the comments to this class. Equivalent to FastFourierTransform(false).
      See Also:

    • FastFourierTransform

      public FastFourierTransform(long maxTempJavaMemory)
      Creates a new instance of this class, performing Fourier transform according to the formula 1 from the comments to this class.

      The maxTempJavaMemory argument specifies the amount of Java memory (heap), that can be used by methods of this class for internal needs. It is passed to the corresponding constructor of AbstractSpectralTransform: see comments to that constructor.

      Parameters:
      maxTempJavaMemory - desired maximal amount of Java memory, in bytes, allowed for allocating by methods of this class for internal needs.
      See Also:

    • FastFourierTransform

      public FastFourierTransform(boolean normalizeDirectTransform)
      Creates a new instance of this class, performing Fourier transform according either to the formula 1 from the comments to this class, if normalizeDirectTransform argument is false, or to the formula 2, if this argument is true. The default value, used by the constructors without normalizeDirectTransform argument, is false.

      Please note: the value of normalizeDirectTransform argument affects only the transformation methods directTransform, inverseTransform, directTransformMatrix, inverseTransformMatrix. This value does not matter in spectrumOfConvolution method.

      Parameters:
      normalizeDirectTransform - true if you want to perform normalization (division by the number of samples N) after the direct transform, false (the default value) if you want to perform normalization after the inverse transform.
      See Also:

    • FastFourierTransform

      public FastFourierTransform(boolean normalizeDirectTransform, long maxTempJavaMemory)
      Creates a new instance of this class, performing Fourier transform according either to the formula 1 from the comments to this class, if normalizeDirectTransform argument is false, or to the formula 2, if this argument is true. The default value, used by the constructors without normalizeDirectTransform argument, is false.

      Please note: the value of normalizeDirectTransform argument affects only the transformation methods directTransform, inverseTransform, directTransformMatrix, inverseTransformMatrix. This value does not matter in spectrumOfConvolution method.

      The maxTempJavaMemory argument specifies the amount of Java memory (heap), that can be used by methods of this class for internal needs. It is passed to the corresponding constructor of AbstractSpectralTransform: see comments to that constructor.

      Parameters:
      normalizeDirectTransform - true if you want to perform normalization (division by the number of samples N) after the direct transform, false (the default value) if you want to perform normalization after the inverse transform.
      maxTempJavaMemory - desired maximal amount of Java memory, in bytes, allowed for allocating by methods of this class for internal needs.
      See Also:

  • Method Details

    • spectrumOfConvolution

      public void spectrumOfConvolution(ArrayContext context, Matrix<? extends UpdatablePNumberArray> cRe, Matrix<? extends UpdatablePNumberArray> cIm, Matrix<? extends PNumberArray> pRe, Matrix<? extends PNumberArray> pIm, Matrix<? extends PNumberArray> qRe, Matrix<? extends PNumberArray> qIm)
      Calculates C = P*Q, i.e. multiplies each element of the complex multidimensional matrix P to the corresponding element of the complex multidimensional matrix Q and stores result in the corresponding element of the complex multidimensional matrix C. If the complex matrices P and Q are Fourier spectra of some matrices (real or complex) p and q, then the resulting complex matrix C will contain the spectrum of the convolution of p and q matrices. See about the convolution theorem at http://en.wikipedia.org/wiki/Discrete_Fourier_transform and in the comments to this class.

      The complex matrix P is represented as a pair of AlgART matrices (pRe,pIm): the corresponding elements of these 2 matrices contain the real and imaginary parts of the corresponding elements of the complex matrix P. Similarly, the complex matrix Q is represented as a pair of AlgART matrices (qRe,qIm), and the complex matrix C is represented as a pair of AlgART matrices (cRe,cIm).

      All matrices, passed to this method, must have equal dimensions. The element type of the passed matrices can be different, but we recommend using the same float or double element type for all matrices. There are no restrictions for the dimensions of the passed matrices: isLengthAllowed(long) method is not used here.

      This method works correctly, if you pass the same complex matrix as P and Q, or as P and C, or as Q and C, or even as all three matrices. So, you can calculate and return the result in one of the source matrices.

      If you need to calculate the Fourier spectrum of convolution for a case of one-dimensional numeric AlgART arrays, you just need to convert them into one-dimensional AlgART matrices by Matrices.matrix(Array, long...) call, for example: Matrices.matrix(array, array.length()).

      Parameters:
      context - the context that will be used by this algorithm; may be null (see comments to SpectralTransform).
      cRe - the real parts of the elements of the resulting matrix.
      cIm - the imaginary parts of the elements of the resulting matrix.
      pRe - the real parts of the elements of the 1st source matrix.
      pIm - the imaginary parts of the elements of the 1st source matrix.
      qRe - the real parts of the elements of the 2nd source matrix.
      qIm - the imaginary parts of the elements of the 2nd source matrix.
      Throws:
      NullPointerException - if one of cRe, cIm, pRe, pIm, qRe, qIm arguments is null.
      SizeMismatchException - if some of the passed matrices have different dimensions.

    • isLengthAllowed

      public final boolean isLengthAllowed(long length)
      Description copied from interface: SpectralTransform
      Returns true if the specified argument is an allowed dimension for arrays or matrices, transformed by directTransform, inverseTransform, directTransformMatrix or inverseTransformMatrix method.

      More precisely, if this method returns false for the length of a sample array, passed to 1st or 2nd methods, or for some dimension of some matrix, passed to 3rd or 4th method, then those methods throw IllegalArgumentException. In other case, those methods will process that passed data.

      In both implementations of this interface, offered by this package, this method returns true if the passed length is a power of two (2k).

      If the length argument is negative, the result of this method is unspecified. It is not a problem, because lengths of sample arrays and dimensions of AlgART matrices cannot be negative.

      Specified by:
      isLengthAllowed in interface SpectralTransform
      Specified by:
      isLengthAllowed in class AbstractSpectralTransform
      Parameters:
      length - the checked length or matrix dimension.
      Returns:
      whether the specified argument is an allowed dimension for arrays or matrices, trasformed by this transformation.

    • areComplexSamplesRequired

      public boolean areComplexSamplesRequired()
      Description copied from interface: SpectralTransform
      Returns true if the transformation methods of this class (directTransform, inverseTransform, directTransformMatrix, inverseTransformMatrix) can process only complex samples, false if the real samples are also allowed.

      More precisely, if this method returns true, then the methods directTransform / inverseTransform checks, whether SampleArray.isComplex() method returns true for the samples argument, and the methods directTransformMatrix / inverseTransformMatrix checks, whether the matrixIm argument is not null. If this condition is not fulfilled, these methods throw UnsupportedOperationException. In other case, these methods work normally.

      In implementations, offered by this package, this method returns true in FastFourierTransform class and false in SeparableFastHartleyTransform class.

      Specified by:
      areComplexSamplesRequired in interface SpectralTransform
      Specified by:
      areComplexSamplesRequired in class AbstractSpectralTransform
      Returns:
      true if this class can transform complex samples only, false if real samples can be transformed too.

    • unallowedLengthMessage

      protected String unallowedLengthMessage()
      Description copied from class: AbstractSpectralTransform
      Retrurns a message used while throwing IllegalArgumentException by methods of this class in a case, when the length of the samples array or some of the matrix dimensions is not allowed according to AbstractSpectralTransform.isLengthAllowed(long) method. Typical examples of this message (implemented in FastFourierTransform and SeparableFastHartleyTransform classes): "FFT algorithm can process only 2^k elements" or "FHT algorithm can process only 2^k elements".
      Specified by:
      unallowedLengthMessage in class AbstractSpectralTransform
      Returns:
      a message used while thrown exception if AbstractSpectralTransform.isLengthAllowed(long) method returns false.

    • transform

      protected final void transform(ArrayContext context, SampleArray samples, boolean inverse)
      Description copied from class: AbstractSpectralTransform
      Actually performs the 1-dimensional transform of the sample array, direct or inverse.

      It is called from directTransform / inverseTransform methods. In this case, there is a guarantee that: 1) samples!=null; 2) if AbstractSpectralTransform.areComplexSamplesRequired(), then samples.isComplex() returns true; 3) AbstractSpectralTransform.isLengthAllowed(long) returns true for samples.length().

      Specified by:
      transform in class AbstractSpectralTransform
      Parameters:
      context - the context that will be used by this algorithm; may be null (see comments to SpectralTransform).
      samples - the transformed samples.
      inverse - true if this method implements the inverse transform, false if this method implements the direct transform.