Filtering

module FFT

Optimized FFT operations exploiting conjugate symmetry for real-valued arrays.

This module provides wrapper types and optimized methods for Fast Fourier Transform operations that take advantage of the conjugate symmetry property of real arrays under the Fourier transform. For real-valued input arrays, the FFT output exhibits conjugate symmetry, allowing storage and computation optimizations by only storing roughly half the frequency domain data.

Key Features

• Memory Optimization: Uses rfft (real FFT) for real arrays to reduce memory usage by ~50%
• Conjugate Symmetry Exploitation: Automatically handles the symmetric properties of real FFTs
• Seamless Integration: Wrapper types behave like regular arrays with transparent optimizations
• Mixed Operations: Supports element-wise operations between optimized and standard FFT outputs

Types

• RFFTOut: Wrapper for real FFT output with conjugate symmetry optimization
• FFTOut: Wrapper for complex FFT output compatible with RFFTOut operations

Usage

The module automatically selects the appropriate optimization based on input type.

If you use it on a complex array, then the wrapper FFTOut is used and no optimizations are applied.

A_complex = rand(ComplexF64, 64, 64)     # Array{ComplexF64} of size 64×64
FA_complex = TF.FFT.fft(A_complex)       # FFTOut of size 64×64
A_complex_ifft = TF.FFT.ifft(FA_complex) # Array{ComplexF64} of size 64×64
@assert A_complex_ifft ≈ A_complex

On real arrays, conjugate symmetry is exploited and the wrapper RFFTOut of half the size is returned.

A_real = rand(64, 64)                 # Array{Float64} of size 64×64
FA_real = TF.FFT.fft(A_real)          # RFFTOut of size 33×64
A_real_ifft = TF.FFT.ifft(FA_real)    # Array{Float64} of size 64×64
@assert A_real_ifft ≈ A_real          # size of the array is restored

So half of the computations are shaved off.

julia> @btime TF.FFT.fft(A_real);
  13.225 μs (13 allocations: 33.60 KiB)

julia> @btime FFTW.fft(A_real);
  26.380 μs (11 allocations: 128.50 KiB)

These two types play together nicely though. Broadcasting works on the full array sizes if necessary (i.e. FFTOut and RFFTOut are interacting).

@assert size(FA_real .* FA_complex) == (64, 64) # FFTOut of size 64×64

# output

FFTOut{T,N,AA<:AbstractArray{T,N}}  <: AbstractArray{T,N}

A trivial wrapper that allows to specify for ifft and mul! and exploit the conjugate symmetry of the Fourier transform in the other argument to mul! when it is real.

See also RFFTOut

RFFTOut{T,N,AA<:AbstractArray{T,N}}  <: AbstractArray{T,N}

An abstract array wrapper for the output of rfft which is created when calling fft on a real array.

It allows to handle the array as if it were the full size but exploits conjugate symmetry of the Fourier transform by running AbstractFFTs.rfft instead of AbstractFFTs.fft on real arrays.

See also FFTOut

fft(A::AbstractArray)

Compute the FFT while exploiting the conjugate symmetry of real arrays and using the usual FFT for complex arrays.

Returns either an RFFTOut or a FFTOut depending on the eltype of the array. These types are smart when broadcasted, i.e. if possible RFFTOut preserves its symmetry and if not possible, it materializes into the full FFTOut.

ifft(A::RFFTOut)
ifft(A::FFTOut)

Computes the iFFT while using the conjugate symmetry that was exploited during the fft operation.