I didn't ask for plan_bfft, but got MethodError: no method matching plan_bfft(::Vector{Number}, ::UnitRange{Int64})

[orswan]

While coding an iterative FFT function, I came upon a strange bug that depends on the arguments to the function in a complicated way. I've managed to reduce the problematic code to the following:

using FFTW
unitize(x::Complex) = x==0 ? 0 : x/abs(x)
function problematic(ys::Tuple,phis::Tuple,nit)
    n = length(ys)
    x = sum(ifft(ys[i]) for i=1:n)/n
    for j=1:nit
        thetas = ((unitize.(fft(x.*phi)) for phi in phis)...,)
        x = sum(ifft(ys[k].*thetas[k]) for k=1:n)/n
    end
    return x
end
x = [exp(-j^2) for j=-10:.1:10]
quad = exp.(im*[-10:.1:10;].^2)
y0 = abs.(fft(x))
y1 = abs.(fft(x.*quad))
x1 = problematic((y0,y1),(ones(length(x)),quad),4);              # This works
x1 = problematic((y0,y1),(ones(length(x)),quad),5);              # But this does not work

The various parameters and the auxiliary function unitize are, unfortunately, necessary for this demonstration, as slight tweaks to the function eliminates the error. The final parameter to problematic determines the number of iterations, and changing it slightly affects whether or not an error is thrown. With slightly different inputs y0, y1, quad, etc. the exact number of iterations at which the error shows up will change also. Under some conditions, I also find that the number of iterations required for an error differs between the REPL and a Jupyter notebook.

I also find it strange that the error mentions plan_bfft, as I do not invoke that at all. Is the compiler automatically planning an FFT when it sees many FFTs in a loop?

I'm using Julia v1.7.2 and FFTW v1.4.6.

[orswan]

I cross posted this to the Julia Discourse, and user DNF identified that the problem has to do with type instability in the unitize function. However, I still don't understand why this is relevant, and why plan_bfft was called. Can someone help me understand this?

[ararslan]

I also find it strange that the error mentions plan_bfft, as I do not invoke that at all.

Ah, but you do! https://github.com/JuliaMath/AbstractFFTs.jl/blob/master/src/definitions.jl#L262-L263

If you look at the full stack trace (topmost frames shown below), you'll see that plan_bfft is being called by plan_ifft, which is in turn being called by ifft. FFTs are always planned; FFT packages that implement the AbstractFFTs interface actually just extend planning functions which get called under the hood when you call a regular FFT function like fft, ifft, etc.

ERROR: MethodError: no method matching plan_bfft(::Vector{Number}, ::UnitRange{Int64})
Closest candidates are:
  plan_bfft(::StridedArray{T, N}, ::Any; flags, timelimit) where {T<:Union{ComplexF32, ComplexF64}, N} at ~/.julia/packages/FFTW/SDUwi/src/fft.jl:685
  plan_bfft(::AbstractArray{<:Real}, ::Any; kws...) at ~/.julia/packages/AbstractFFTs/Ih3rT/src/definitions.jl:199
  plan_bfft(::AbstractArray{<:Complex{<:Union{Integer, Rational}}}, ::Any; kws...) at ~/.julia/packages/AbstractFFTs/Ih3rT/src/definitions.jl:201
  ...
Stacktrace:
  [1] plan_ifft(x::Vector{Number}, region::UnitRange{Int64}; kws::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ AbstractFFTs ~/.julia/packages/AbstractFFTs/Ih3rT/src/definitions.jl:262
  [2] plan_ifft(x::Vector{Number}, region::UnitRange{Int64})
    @ AbstractFFTs ~/.julia/packages/AbstractFFTs/Ih3rT/src/definitions.jl:262
  [3] plan_ifft(x::Vector{Number}; kws::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ AbstractFFTs ~/.julia/packages/AbstractFFTs/Ih3rT/src/definitions.jl:52
  [4] plan_ifft(x::Vector{Number})
    @ AbstractFFTs ~/.julia/packages/AbstractFFTs/Ih3rT/src/definitions.jl:52
  [5] ifft(x::Vector{Number})
    @ AbstractFFTs ~/.julia/packages/AbstractFFTs/Ih3rT/src/definitions.jl:50

[ararslan]

Type stability is relevant because type inference determined that a "good enough" element type for the array would be Number but methods for plan_bfft are only defined when the element type is some subtype of Real or Complex.

[ararslan]

I'm going to close this issue since there doesn't seem to be a problem with FFTW itself and Discourse is the place to ask usage questions.