juliamath / fftw.jl Goto Github PK

View Code? Open in Web Editor NEW

257.0 13.0 53.0 627 KB

Julia bindings to the FFTW library for fast Fourier transforms

Home Page: https://juliamath.github.io/FFTW.jl/stable

License: MIT License

Julia 100.00%

julia fftw bindings fft mkl math

fftw.jl's Introduction

FFTW.jl

This package provides Julia bindings to the FFTW library for fast Fourier transforms (FFTs), as well as functionality useful for signal processing. These functions were formerly a part of Base Julia.

Usage and documentation

]add FFTW
using FFTW
fft([0; 1; 2; 1])

returns

4-element Array{Complex{Float64},1}:
  4.0 + 0.0im
 -2.0 + 0.0im
  0.0 + 0.0im
 -2.0 + 0.0im

The documentation of generic FFT functionality can be found in the AbstractFFTs.jl package. Additional functionalities supported by the FFTW library are documented in the present package.

MKL

Alternatively, the FFTs in Intel's Math Kernel Library (MKL) can be used by running FFTW.set_provider!("mkl"). MKL will be provided through MKL_jll. This change of provider is persistent and has to be done only once, i.e., the package will use MKL when building and updating. Note however that MKL provides only a subset of the functionality provided by FFTW. See Intel's documentation for more information about potential differences or gaps in functionality. In case MKL does not fit the needs (anymore), FFTW.set_provider!("fftw") allows to revert the change of provider.

License

The FFTW library will be downloaded on versions of Julia where it is no longer distributed as part of Julia. Note that FFTW is licensed under GPLv2 or higher (see its license file), but the bindings to the library in this package, FFTW.jl, are licensed under MIT. This means that code using the FFTW library via the FFTW.jl bindings is subject to FFTW's licensing terms. Code using alternative implementations of the FFTW API, such as MKL's FFTW3 interface are instead subject to the alternative's license. If you distribute a derived or combined work, i.e. a program that links to and is distributed with the FFTW library, then that distribution falls under the terms of the GPL. If you just distribute source code that links to FFTW.jl, and users have to download FFTW or MKL to provide the backend, then the GPL probably doesn't have much effect on you.

fftw.jl's People

Contributors

Stargazers

Watchers

Forkers

tkelman appleparan favba halars drdaleks juliadocsforks jhardenberg ssfrr fiatflux fenglb antoine-levitt darwindarak giordano asinghvi17 carstenbauer samusz heitorpb jipolanco ianbutterworth thisrod galenlynch adamslc contextflow charleskawczynski qdet navidcy jkrimmer jakebolewski standardgalactic uzaynagme currymultisci octogonapus ven-k csvaldellon bioturbonick playfloor n5n3 fzhangscorec biomedai mfkiwl mofii zhubonan bradcarman samsartor crazy-rookie jishnub gaurav-arya ranocha jsjie vpuri3 sadish-d songjhaha palday

fftw.jl's Issues

Drop 0.6 support

Since we aren't actually defining a package on 0.6 to avoid the crazy naming issues, any changes made to this package can't be used on 0.6 without a complete restructuring. Now that we have a tag that supports 0.6, I think we should bump the REQUIRE to 0.7.0-DEV.602, when FFTW was removed from Base, and focus on resolving the outstanding issues with the package on 0.7 (of which there are many). This allows us to simplify the package structure back to a normal package without a bunch of conditional includes. It will also cut down on CI time, since we know the tests would pass on 0.6 anyway; they're former Base tests using Base code. Users on 0.6 will still be able to install and require FFTW, Pkg would just choose a different FFTW tag on 0.6 and 0.7.

Building fails on julia 0.6

julia> Pkg.build("FFTW")
INFO: Building FFTW
================================================================[ ERROR: FFTW ]================================================================

LoadError: Provider BinDeps.PackageManager failed to satisfy dependency libfftw3_threads
while loading /astro/faculty/ebf11/.julia/v0.6/FFTW/deps/build.jl, in expression starting on line 73

===============================================================================================================================================

===============================================================[ BUILD ERRORS ]================================================================

WARNING: FFTW had build errors.

packages with build errors remain installed in /astro/faculty/ebf11/.julia/v0.6
build the package(s) and all dependencies with Pkg.build("FFTW")
build a single package by running its deps/build.jl script

===============================================================================================================================================

How can I transform of 2D FFT for image?

Hi, @jiahao @wildart @antoine-levitt @staticfloat @mortenpi

How can I transform of 2D FFT for image using Julia(FFTW)?

I wonder.

Thanks.

Build fails on Windows

There seems to be some issue with BinDeps on Windows such that BinDeps.debug("FFTW") shows no available providers for libfftw and libfftwf on Windows. So this package is effectively unusable on Windows with Julia 0.7.

`lmul!` should be required for in-place application of plans

Overall, I like the overriding of * for planned transforms. But it is a bit odd that * modifies what you multiply in the following:

P = plan_fft!(x); P * x

I would propose deprecating plan_fft!, and instead only have plan_fft with the following usage for the in-place variants:

P = plan_fft(x); lmul!(P, x)

Tag new release

I'm getting deprecation warnings while updating packages for v0.7-beta from FFTW.jl.

split package

The point of the dft.jl stuff is that you can plug in non-FFTW implementations (e.g. a pure-Julia FFT, FFTPACK, whatever) and it will still work with the same interface. So, it really needs to be split into a separate package.

My suggestion would be that there be a separate package (maybe "AbstractFFTs"?) that contains dft.jl. Then any package that provides FFT functionality would use this package.

Similarly the dsp stuff should probably be in a separate package.

both FFTW and Base export "FFTW"

Been trying to get some code running on v0.7 and running into difficulties with getting FFTW to work in my modules. Here is a simplified module that gives me errors.

module Fields

export r𝔽, Flat

using FFTW
import Base: *, \

abstract type Flat{Θpix,nside} end

struct r𝔽{P<:Flat,T<:Real,F}
    Δx::T
    Δk::T
    Ωk::T
    Ωx::T
    period::T
    nyq::T
    k::Vector{Matrix{T}}
    x::Vector{Matrix{T}}
    FFT::F
end

# real FFT generated function constructor
@generated function r𝔽(::Type{P},::Type{T}) where T<:Real where P<:Flat{Θpix, nside}  where {Θpix, nside}
    Δx     = deg2rad(Θpix/60)
    period = Δx*nside
    Δk     = 2π/period
    Ωk     = Δk^2
    Ωx   = Δx^2
    nyq    = 2π / (2Δx)
    k_side = ifftshift(-nside÷2:(nside-1)÷2) * Δk
    x_side = ifftshift(-nside÷2:(nside-1)÷2) * Δx
    k      = [reshape(k_side, 1, nside), reshape(k_side[1:nside÷2+1], nside÷2+1, 1)]
    x      = [reshape(x_side, 1, nside), reshape(x_side, nside, 1)]
    FFT    =  Ωx / (2π) * plan_rfft(rand(T,nside,nside); flags=FFTW.PATIENT, timelimit=4)
    r𝔽{P,T,typeof(FFT)}(Δx, Δk, Ωk, Ωx, period, nyq, k, x, FFT)
end

(*)(g::r𝔽{P,T}, x) where P<:Flat where T = g.FFT * x
(\)(g::r𝔽{P,T}, x) where P<:Flat where T = g.FFT \ x

end

I want the following code block to run ...

using Main.Fields

nside  = 1024
Θpix   = 2.0
Px     = Flat{Θpix,nside}
Tx     = Float32
g      =  r𝔽(Px,Tx)

fx = rand(nside, nside)
fk = g * fx
y = g \ fk

.... but I get the following error in the line:

julia> g      =  r𝔽(Px,Tx)
WARNING: both FFTW and Base export "FFTW"; uses of it in module Fields must be qualified
ERROR: UndefVarError: FFTW not defined
Stacktrace:
 [1] #s1#1(::Any, ::Any, ::Any, ::Any, ::Any, ::Type, ::Any) at ./REPL[1]:34
 [2] (::Core.GeneratedFunctionStub)(::Any, ::Vararg{Any,N} where N) at ./boot.jl:443
 [3] In toplevel scope

Any ideas what is going on?

Here is my version info:

julia> versioninfo()
Julia Version 0.7.0-DEV.2454
Commit 00dafe28c0* (2017-11-07 15:53 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin17.2.0)
  CPU: Intel(R) Core(TM) i7-5557U CPU @ 3.10GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, broadwell)

Package compatibility caps

Ref: https://discourse.julialang.org/t/package-compatibility-caps/15301

Inference failure in brfft on 0.7

From the Travis log (also seeing locally):

ERROR: LoadError: return type Array{Float64,2} does not match inferred return type Any
Stacktrace
 [1] macro expansion at /home/travis/.julia/v0.7/FFTW/test/runtests.jl:335 [inlined]
 [2] anonymous at ./<missing>:?
 [3] include_relative(::Module, ::String) at ./loading.jl:464
 [4] include(::Module, ::String) at ./sysimg.jl:14
 [5] process_options(::Base.JLOptions) at ./client.jl:315
 [6] _start() at ./client.jl:383
while loading /home/travis/.julia/v0.7/FFTW/test/runtests.jl, in expression starting on line 331

The line that's being hit is equivalent to @inferred brfft(randn(10), 18). Oddly enough, running that from the REPL works fine for me.

Wrong results when doing irfft -> rfft

FFTW.jlfailed some FFT test that I made. I wanted to figure out why it is and tested with fortran and FFTW.

I used Julia v0.6.0 and FFTW.jl v0.0.4. All other packages are up-to-date (using Pkg.update())

At first, I generated random complex array even with imaginary part. However, FFTW also failed. I asked stackoverflow and got an answer Therefore, I changed array generation with zero imaginary part. I found FFTW (fortran ver.) works.

Here is my test code.

using Base.Test
using FFTW

nx = 5; ny = 8
a = rand(nx, ny) + im * zeros(nx, ny)
@test norm(FFTW.rfft(FFTW.irfft(a, (nx - 1) * 2)) - a) < 1e-8

It didn't passed because norm is large as 10^-1 order.
I know it's not normal to irfft to rfft, but when I printed results and compared the results I found this seems a bug. However, rfft to irfft from another real array is working well.

@show a
@show FFTW.rfft(FFTW.irfft(a, (nx - 1) * 2))

This shows first row and last row (except first column and last column) are different with original array a.

a = Complex{Float64}[
0.731823+0.0im 0.0914679+0.0im 0.421424+0.0im 0.66566+0.0im 0.676793+0.0im 0.91561+0.0im 0.167977+0.0im 0.81144+0.0im;
0.955786+0.0im 0.988594+0.0im 0.946422+0.0im 0.469863+0.0im 0.567468+0.0im 0.410604+0.0im 0.0876826+0.0im 0.350643+0.0im;
0.675414+0.0im 0.376511+0.0im 0.411776+0.0im 0.634354+0.0im 0.324661+0.0im 0.456795+0.0im 0.648942+0.0im 0.938804+0.0im;
0.879751+0.0im 0.801969+0.0im 0.209773+0.0im 0.229292+0.0im 0.47708+0.0im 0.488061+0.0im 0.553131+0.0im 0.459141+0.0im;
0.0991666+0.0im 0.743879+0.0im 0.751298+0.0im 0.96974+0.0im 0.407805+0.0im 0.726425+0.0im 0.766682+0.0im 0.0755481+0.0im]

FFTW.rfft(FFTW.irfft(a, (nx - 1) * 2)) = Complex{Float64}[
0.731823+0.0im 0.451454+0.0im 0.294701+0.0im 0.790635+0.0im 0.676793+0.0im 0.790635+0.0im 0.294701+0.0im 0.451454+0.0im;
0.955786+0.0im 0.988594+0.0im 0.946422+0.0im 0.469863+0.0im 0.567468+0.0im 0.410604+0.0im 0.0876826+0.0im 0.350643+0.0im;
0.675414+0.0im 0.376511+0.0im 0.411776+0.0im 0.634354+0.0im 0.324661+0.0im 0.456795+0.0im 0.648942+0.0im 0.938804+0.0im;
0.879751+0.0im 0.801969+0.0im 0.209773+0.0im 0.229292+0.0im 0.47708+0.0im 0.488061+0.0im 0.553131+0.0im 0.459141+0.0im;
0.0991666+0.0im 0.409713+0.0im 0.75899+0.0im 0.848083+0.0im 0.407805+0.0im 0.848083+0.0im 0.75899+0.0im 0.409713+0.0im]

I also tested with python 3.6.2 and recent version of numpy . I used same value generated from Julia, but python has passed the test. I also tested randomly generated complex array, this is also passed.

import numpy.fft as fft
import numpy as np
import numpy.linalg as lin
import numpy.random as random

def run():
    nx = 5
    ny = 8

    #a = [[0.0091934+0.0j, 0.887909+0.0j, 0.022417+0.0j, 0.377631+0.0j, 0.57725+0.0j, 0.759539+0.0j, 0.497938+0.0j, 0.50837+0.0j], [0.36253+0.0j, 0.250405+0.0j, 0.335141+0.0j, 0.836328+0.0j, 0.517139+0.0j, 0.976069+0.0j, 0.0158171+0.0j, 0.919675+0.0j], [0.830197+0.0j, 0.731117+0.0j, 0.738942+0.0j, 0.729338+0.0j, 0.00759557+0.0j, 0.159997+0.0j, 0.848967+0.0j, 0.277697+0.0j], [0.536876+0.0j, 0.199403+0.0j, 0.281549+0.0j, 0.136321+0.0j, 0.240842+0.0j, 0.58003+0.0j, 0.294667+0.0j, 0.330748+0.0j], [0.276797+0.0j, 0.0450511+0.0j, 0.990411+0.0j, 0.174055+0.0j, 0.218758+0.0j, 0.940231+0.0j, 0.158844+0.0j, 0.12785+0.0j]]
    a = random.rand(nx, ny) + np.zeros((nx, ny)) * 1j

    print(a)
    b = fft.rfft(fft.irfft(a))
    print(b)

    print(lin.norm(a - b))

if __name__ == '__main__':
    run()

However, 1D case even with not setting imaginary part as zero, irfft -> rfft works.

# 1D real FFT Test
nx = 16

a = rand(nx)
#@test norm(FFTW.irfft(FFTW.rfft(a), nx) - a) < 1e-8
@test norm(FFTW.irfft(FFTW.rfft(a), nx) - a) < 1e-12

a = rand(nx) + im * zeros(nx)
@test norm(FFTW.rfft(FFTW.irfft(a, (length(a) - 1) * 2)) - a) < 1e-12

0.7: plan_fft! broken

julia> v = Array{Complex128}(uninitialized, 10); Main.FFTW.plan_fft!(v)
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
WARNING: Base.Complex128 is deprecated, use ComplexF64 instead.
  likely near no file:0
ERROR: conversion to pointer not defined for Adjoint{Int64,Array{Int64,2}}
Stacktrace:
 [1] error at ./error.jl:33 [inlined]
 [2] unsafe_convert at ./pointer.jl:69 [inlined]
 [3] Type at /Users/solver/.julia/v0.7/FFTW/src/fft.jl:491 [inlined]
 [4] #plan_fft!#6 at /Users/solver/.julia/v0.7/FFTW/src/fft.jl:618 [inlined]
 [5] plan_fft! at /Users/solver/.julia/v0.7/FFTW/src/fft.jl:618 [inlined]
 [6] #plan_fft!#8 at /Users/solver/.julia/v0.7/FFTW/src/fft.jl:622 [inlined]
 [7] plan_fft!(::Array{Complex{Float64},1}) at /Users/solver/.julia/v0.7/FFTW/src/fft.jl:622
 [8] top-level scope

julia> versioninfo()
Julia Version 0.7.0-DEV.3131
Commit 564ecb0fd4 (2017-12-20 11:49 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin17.3.0)
  CPU: Intel(R) Core(TM) i5-7600K CPU @ 3.80GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, skylake)
Environment:
  JULIA_VERSION = 0.6

Segmentation fault on Mac

My Travis build on Mac is failing consistently, apparently due to FFTW. Could you please share some thoughts on what might be happening and how I can fix it? https://travis-ci.org/juliohm/ImageQuilting.jl/jobs/346038516#L595-L614

Reexport AbstractFFTs symbols?

It's kind of unfortunate to have to do using FFTW, AbstractFFTs to be able to get all of the FFT functionality you need, and it's less discoverable for users. It seems like it would be more convenient from a usability perspective to just do @reexport using AbstractFFTs here. Thoughts, @stevengj?

FFTW.r2r slow

I was trying to use discrete sine transform which is not in the standard Base library (why is cosine transform there~?) so I turned to use fftw.r2r with FFTW.RODFT00 flag. It turned out to be 2x slower the Matlab dst somehow. Does anyone have the same issue?

This is the result for 2D transform
Julia:
@time ainv(rand(1000,1000))
0.612343 seconds (204 allocations: 30.528 MiB, 0.86% gc time)

Matlab:
Elapsed time is 0.140380 seconds.

PS I turned the multithreading on in Julia already.

Thanks!

FFTW doesn't work on `arm`: `libm.so: cannot open shared object file: No such file or directory`

See https://cloud.drone.io/giordano/FFTW.jl/3/1/2. @ararslan today told me that probably the builder needs to depend on https://github.com/JuliaMath/OpenlibmBuilder to make sure that OpenLibm is used, instead of looking for system libm.

0.7: using FFTW broken

julia> using FFTW
[ Info: Precompiling module FFTW @ Base loading.jl:622
ERROR: LoadError: syntax: malformed expression
Stacktrace:
 [1] include at ./boot.jl:295 [inlined]
 [2] include_relative(::Module, ::String) at ./loading.jl:503
 [3] include(::Module, ::String) at ./sysimg.jl:26
 [4] top-level scope
 [5] eval at ./boot.jl:298 [inlined]
 [6] top-level scope at ./<missing>:2
in expression starting at /Users/solver/.julia/v0.7/FFTW/src/FFTW.jl:7
vERROR: Failed to precompile FFTW to /Users/solver/.julia/lib/v0.7/FFTW.ji.e
Stacktrace:
 [1] error at ./error.jl:33 [inlined]
 [2] compilecache(::String) at ./loading.jl:630
 [3] compilecache at ./loading.jl:587 [inlined]
 [4] _require(::Symbol) at ./loading.jl:442
 [5] require(::Symbol) at ./loading.jl:315

julia> versioninfo()
Julia Version 0.7.0-DEV.3199
Commit 1238bad60f (2017-12-27 20:40 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin17.3.0)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, skylake)
Environment:
  JULIA_VERSION = 0.6

Pkg.add("FFTW") fails in Windows Julia 1.0.3

It can't download something and fails. All my package adds are terribly slow on Windows. It's pretty much unusable.

julia> Pkg.add("FFTW")
 Resolving package versions...
 Installed AbstractFFTs ─ v0.3.2
 Installed FFTW ───────── v0.2.4
  Updating `C:\Users\matt\.julia\environments\v1.0\Project.toml`
  [7a1cc6ca] + FFTW v0.2.4
  Updating `C:\Users\matt\.julia\environments\v1.0\Manifest.toml`
  [621f4979] + AbstractFFTs v0.3.2
  [7a1cc6ca] + FFTW v0.2.4
  Building FFTW → `C:\Users\matt\.julia\packages\FFTW\p7sLQ\deps\build.log`
┌ Error: Error building `FFTW`:
│ ┌ Warning: On Windows, creating file symlinks requires Administrator privileges
│ └ @ Base.Filesystem file.jl:789
│ ┌ Warning: platform_key() is deprecated, use platform_key_abi() from now on
│ │   caller = ip:0x0
│ └ @ Core :-1
│ ┌ Warning: Could not extract the platform key of https://github.com/JuliaMath/FFTWBuilder/releases/download/v3.3.8+1/FFTW.x86_64-w64-mingw32.tar.gz; continuing...
│ └ @ BinaryProvider C:\Users\matt\.julia\packages\BinaryProvider\4F5Hq\src\Prefix.jl:185
│ [ Info: Downloading https://github.com/JuliaMath/FFTWBuilder/releases/download/v3.3.8+1/FFTW.x86_64-w64-mingw32.tar.gz to C:\Users\matt\.julia\packages\FFTW\p7sLQ\deps\usr\downloads\FFTW.x86_64-w64-mingw32.tar.gz...
│ ERROR: LoadError: LoadError: Could not download https://github.com/JuliaMath/FFTWBuilder/releases/download/v3.3.8+1/FFTW.x86_64-w64-mingw32.tar.gz to C:\Users\matt\.julia\packages\FFTW\p7sLQ\deps\usr\downloads\FFTW.x86_64-w64-mingw32.tar.gz:
│ ErrorException("")
│ Stacktrace:
│  [1] error(::String) at .\error.jl:33
│  [2] #download#93(::Bool, ::Function, ::String, ::String) at C:\Users\matt\.julia\packages\BinaryProvider\4F5Hq\src\PlatformEngines.jl:498
│  [3] #download at .\none:0 [inlined]
│  [4] #download_verify#94(::Bool, ::Bool, ::Bool, ::Function, ::String, ::String, ::String) at C:\Users\matt\.julia\packages\BinaryProvider\4F5Hq\src\PlatformEngines.jl:567
│  [5] #download_verify at .\none:0 [inlined]
│  [6] #install#133(::Prefix, ::String, ::Bool, ::Bool, ::Bool, ::Function, ::String, ::String) at C:\Users\matt\.julia\packages\BinaryProvider\4F5Hq\src\Prefix.jl:314
│  [7] (::getfield(BinaryProvider, Symbol("#kw##install")))(::NamedTuple{(:prefix, :force, :verbose),Tuple{Prefix,Bool,Bool}}, ::typeof(install), ::String, ::String) at .\none:0
│  [8] top-level scope at C:\Users\matt\.julia\packages\FFTW\p7sLQ\deps\build_fftw.jl:37
│  [9] include at .\boot.jl:317 [inlined]
│  [10] include_relative(::Module, ::String) at .\loading.jl:1044
│  [11] include(::Module, ::String) at .\sysimg.jl:29
│  [12] include(::String) at .\client.jl:392
│  [13] top-level scope at C:\Users\matt\.julia\packages\FFTW\p7sLQ\deps\build.jl:48
│  [14] include at .\boot.jl:317 [inlined]
│  [15] include_relative(::Module, ::String) at .\loading.jl:1044
│  [16] include(::Module, ::String) at .\sysimg.jl:29
│  [17] include(::String) at .\client.jl:392
│  [18] top-level scope at none:0
│ in expression starting at C:\Users\matt\.julia\packages\FFTW\p7sLQ\deps\build_fftw.jl:33
│ in expression starting at C:\Users\matt\.julia\packages\FFTW\p7sLQ\deps\build.jl:19
│ Exception calling "DownloadFile" with "2" argument(s): "The operation has timed out."
│ At line:5 char:1
│ + $webclient.DownloadFile("https://github.com/JuliaMath/FFTWBuilder/rel ...
│ + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
│     + CategoryInfo          : NotSpecified: (:) [], MethodInvocationException
│     + FullyQualifiedErrorId : WebException
│
└ @ Pkg.Operations C:\cygwin\home\Administrator\buildbot\worker\package_win64\build\usr\share\julia\stdlib\v1.0\Pkg\src\Operations.jl:1097

Expose full guru interface API

The current plan_* API does not expose the full functionality that the C FFTW API has, namely the ability to specify a custom stride pattern and the number of transforms to perform.

In my use case I have dense arrays of a custom number type VarNum{T}, wrapping two Ts, and need to perform transforms on the x and y components separately. For instance, consider:

struct VarNum{T<:Number} <: Number
    x::T
    y::T
end

# arrays
u = Matrix{VarNum{Float64}}(10, 10)
U = Matrix{VarNum{Complex{Float64}}}(10, 6)

# create and apply plan
p = plan_rftt(u, [2, 1])
A_mul_B!(U, p, U)

I have somehow hacked into FFTW.jl code as much as needed to achieve what I want. This required doubling the strides of VarNum arrays, doubling the howmany parameter, and defining appropriate methods for VarNum arrays. I feel, though, that such functionality might be useful to many other people and it would be good to have it in the package.

FFT of transposed complex matrix

julia> fft(transpose(rand(ComplexF64,2,2)))
ERROR: MethodError: no method matching plan_fft(::Transpose{Complex{Float64},Array{Complex{Float64},2}}, ::UnitRange{Int64})
Closest candidates are:
  plan_fft(::Union{DenseArray{T<:Union{Complex{Float32}, Complex{Float64}},N}, ReinterpretArray{T<:Union{Complex{Float32}, Complex{Float64}},N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Tuple{AbstractUnitRange,Vararg{Any,N} where N} where A<:DenseArray where N where T, DenseArray}, ReshapedArray{T<:Union{Complex{Float32}, Complex{Float64}},N,A,MI} where MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Tuple{AbstractUnitRange,Vararg{Any,N} where N} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Tuple{AbstractUnitRange,Vararg{Any,N} where N} where A<:DenseArray where N where T, DenseArray}, SubArray{T<:Union{Complex{Float32}, Complex{Float64}},N,A,I,L} where L where I<:Tuple{Vararg{Union{Int64, AbstractRange{Int64}, AbstractCartesianIndex},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Tuple{AbstractUnitRange,Vararg{Any,N} where N} where A<:DenseArray where N where T, DenseArray} where N where T, ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Tuple{AbstractUnitRange,Vararg{Any,N} where N} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Tuple{AbstractUnitRange,Vararg{Any,N} where N} where A<:DenseArray where N where T, DenseArray} where N where T, DenseArray}}, ::Any; flags, timelimit) where {T<:Union{Complex{Float32}, Complex{Float64}}, N} at /home/ettersi/.julia/packages/FFTW/p7sLQ/src/fft.jl:619
  plan_fft(::AbstractArray{#s16,N} where N where #s16<:Real, ::Any; kws...) at /home/ettersi/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:199
  plan_fft(::AbstractArray{#s25,N} where N where #s25<:(Complex{#s26} where #s26<:Union{Integer, Rational}), ::Any; kws...) at /home/ettersi/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:201
  ...
Stacktrace:
 [1] #plan_fft#1(::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::Function, ::Transpose{Complex{Float64},Array{Complex{Float64},2}}) at /home/ettersi/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:52
 [2] plan_fft(::Transpose{Complex{Float64},Array{Complex{Float64},2}}) at /home/ettersi/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:52
 [3] fft(::Transpose{Complex{Float64},Array{Complex{Float64},2}}) at /home/ettersi/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:50
 [4] top-level scope at none:0

Note that the real case works:

julia> fft(transpose(rand(Float64,2,2)))
2×2 Array{Complex{Float64},2}:
   1.70938+0.0im   0.333911+0.0im
 -0.734234+0.0im  -0.246447+0.0im

Rename the package?

As we've been finding recently with Iterators.jl vs Base.Iterators and now FFTW.jl vs Base.FFTW, it causes a lot of weird, annoying issues when packages have the same name as a Base module. See for example #13 and JuliaStats/Distributions.jl#631. Thus we should probably just follow suit with Iterators and rename the package. While it's unfortunate to lose the name FFTW, I'm not sure it can be helped in this case. Name proposals? cc @stevengj and @tkelman

Build fails on CentOS7


INFO: Building FFTW
sudo: no tty present and no askpass program specified
================================[ ERROR: FFTW ]=================================

LoadError: failed process: Process(`sudo yum install fftw`, ProcessExited(1)) [1]
while loading /home/crackauc/.julia/v0.6/FFTW/deps/build.jl, in expression starting on line 73

================================================================================

================================[ BUILD ERRORS ]================================

WARNING: FFTW had build errors.

 - packages with build errors remain installed in /home/crackauc/.julia/v0.6
 - build the package(s) and all dependencies with `Pkg.build("FFTW")`
 - build a single package by running its `deps/build.jl` script

================================================================================

But:

[crackauc@crackauc2 v0.5]$ sudo yum install FFTW
[sudo] password for crackauc: 
Loaded plugins: fastestmirror, langpacks
base                                                                                                                                     | 3.6 kB  00:00:00     
cuda                                                                                                                                     | 2.5 kB  00:00:00     
epel/x86_64/metalink                                                                                                                     |  15 kB  00:00:00     
extras                                                                                                                                   | 3.4 kB  00:00:00     
google-chrome                                                                                                                            |  951 B  00:00:00     
nalimilan-julia                                                                                                                          | 3.0 kB  00:00:00     
updates                                                                                                                                  | 3.4 kB  00:00:00     
(1/2): updates/7/x86_64/primary_db                                                                                                       | 7.7 MB  00:00:00     
(2/2): extras/7/x86_64/primary_db                                                                                                        | 188 kB  00:00:01     
Loading mirror speeds from cached hostfile
 * base: mirror.san.fastserv.com
 * epel: mirrors.kernel.org
 * extras: mirror.keystealth.org
 * updates: repos-lax.psychz.net
No package FFTW available.
  * Maybe you meant: fftw
Error: Nothing to do

How can I transform of 2D FFTW fro image?

FFTW broken with latest adjoint() changes

julia> using FFTW

julia> fft(rand(10))
ERROR: conversion to pointer not defined for Adjoint{Int64,Array{Int64,2}}
Stacktrace:
 [1] error at ./error.jl:33 [inlined]
 [2] unsafe_convert at ./pointer.jl:67 [inlined]
 [3] FFTW.cFFTWPlan{Complex{Float64},-1,false,1}(::Array{Complex{Float64},1}, ::FFTW.FakeArray{Complex{Float64},1}, ::UnitRange{Int64}, ::UInt32, ::Float64) at /Users/felipeavba/.julia/v0.7/FFTW/src/fft.jl:491
 [4] #plan_fft#5(::UInt32, ::Float64, ::Function, ::Array{Complex{Float64},1}, ::UnitRange{Int64}) at /Users/felipeavba/.julia/v0.7/FFTW/src/fft.jl:611
 [5] plan_fft at /Users/felipeavba/.julia/v0.7/FFTW/src/fft.jl:611 [inlined]
 [6] fft at /Users/felipeavba/.julia/v0.7/AbstractFFTs/src/definitions.jl:50 [inlined]
 [7] fft at /Users/felipeavba/.julia/v0.7/AbstractFFTs/src/definitions.jl:197 [inlined] (repeats 2 times)
 [8] top-level scope

julia> versioninfo()
Julia Version 0.7.0-DEV.3351
Commit 09f7213c94* (2018-01-09 01:31 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin17.3.0)
  CPU: Intel(R) Core(TM) i5-5287U CPU @ 2.90GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, broadwell)
Environment:
  JULIA_NUM_THREADS = 2

Adding this method solves the issue:

Base.unsafe_convert(::Type{Ptr{T}},a::Adjoint{T,Array{T,N}}) where {T,N} = pointer(a.parent)

But, then should this be an issue to Julia or to FFTW.jl?

Package name conflict

I fear this package may have the same problem that the Iterators package has been experiencing:

julia> module Mine
       using FFTW

       struct Foo end

       FFTW.fft(::Foo) = 1

       end
WARNING: both FFTW and Base export "FFTW"; uses of it in module Mine must be qualified
ERROR: UndefVarError: FFTW not defined

julia> versioninfo()
Julia Version 0.7.0-DEV.616
Commit d49469d* (2017-06-16 15:45 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, broadwell)
Environment:
  JULIAHOME = /home/tim/src/julia
  JULIAFUNCDIR = /home/tim/juliafunc
  JULIA_CPU_CORES = 2

Migrate the build to BinaryBuilder

Is there any effort to migrating the build to BinaryBuilder?

Windows and Mac binaries

For Windows and Mac users, we need to provide precompiled binaries.

Regression in type inference for ScaledPlans on 0.7

Observed in #56:

ERROR: LoadError: return type AbstractFFTs.ScaledPlan{Complex{Float64},FFTW.cFFTWPlan{Complex{Float64},-1,true,1},Float64} does not match inferred return type AbstractFFTs.ScaledPlan{Complex{Float64},FFTW.cFFTWPlan{Complex{Float64},-1,true,1},_1} where _1
Stacktrace:
 [1] error at ./error.jl:33 [inlined]
 [2] top-level scope at ./<missing>:346
 [3] include at ./boot.jl:293 [inlined]
 [4] include_relative(::Module, ::String) at ./loading.jl:521
 [5] include(::Module, ::String) at ./sysimg.jl:26
 [6] process_options(::Base.JLOptions) at ./client.jl:324
 [7] _start() at ./client.jl:375
in expression starting at /home/travis/.julia/v0.7/FFTW/test/runtests.jl:330

The result is being inferred as a UnionAll (note the _1 where _1), which is incorrect, causing a test failure from @inferred (though it's not clear which invocation of @inferred is triggering it).

The Travis version info:

$ julia -e 'versioninfo()'
Julia Version 0.7.0-DEV.3354
Commit 9b5eed2b6c (2018-01-09 08:03 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, ivybridge)
Environment:
  TRAVIS_JULIA_VERSION = nightly

Tests fail on aarch64

See https://cloud.drone.io/giordano/FFTW.jl/1/2/2

Test Failed at /drone/src/test/runtests.jl:511
Expression: plan_rfft(Array{Float32}(undef, 32)) * view(A, 2:33)
Expected: ArgumentError
No exception thrown
ERROR: LoadError: There was an error during testing
in expression starting at /drone/src/test/runtests.jl:489
ERROR: Package FFTW errored during testing
Stacktrace:
[1] pkgerror(::String, ::Vararg{String,N} where N) at /buildworker/worker/package_linuxaarch64/build/usr/share/julia/stdlib/v1.1/Pkg/src/Types.jl:120
[2] #test#66(::Bool, ::Function, ::Pkg.Types.Context, ::Array{Pkg.Types.PackageSpec,1}) at /buildworker/worker/package_linuxaarch64/build/usr/share/julia/stdlib/v1.1/Pkg/src/Operations.jl:1329
[3] #test at ./none:0 [inlined]
[4] #test#46(::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::Function, ::Pkg.Types.Context, ::Array{Pkg.Types.PackageSpec,1}) at /buildworker/worker/package_linuxaarch64/build/usr/share/julia/stdlib/v1.1/Pkg/src/API.jl:198
[5] #test at ./none:0 [inlined]
[6] #test#45 at /buildworker/worker/package_linuxaarch64/build/usr/share/julia/stdlib/v1.1/Pkg/src/API.jl:180 [inlined]
[7] #test at ./none:0 [inlined]
[8] #test#42 at /buildworker/worker/package_linuxaarch64/build/usr/share/julia/stdlib/v1.1/Pkg/src/API.jl:177 [inlined]
[9] (::getfield(Pkg.API, Symbol("#kw##test")))(::NamedTuple{(:coverage,),Tuple{Bool}}, ::typeof(Pkg.API.test)) at ./none:0
[10] top-level scope at none:0

precompilation error

Hi I am getting this

WARNING: --output requested, but no modules defined during run
WARNING: The call to compilecache failed to create a usable precompiled cache file for module FFTW. Got:
WARNING: Cache file "/home/febbo/.julia/lib/v0.6/FFTW.ji" not found.
WARNING: eval from module Main to FFTViews:    
Expr(:call, Expr(:., :Base, :include_from_node1)::Any, "/home/febbo/.julia/v0.6/FFTW/src/FFTW.jl")::Any
  ** incremental compilation may be broken for this module **

Any ideas on how to fix this?

Thanks!

Failled to create a usable precompiled cache file

Today when I loaded Images.jl, I got the following warning regarding FFTW.jl:

INFO: Recompiling stale cache file /home/juliohm/.julia/lib/v0.6/Images.ji for module Images.
WARNING: --output requested, but no modules defined during run
WARNING: The call to compilecache failed to create a usable precompiled cache file for module FFTW. Got:
WARNING: Cache file "/home/juliohm/.julia/lib/v0.6/FFTW.ji" not found.
WARNING: eval from module Main to FFTViews:    
Expr(:call, Expr(:., :Base, :include_from_node1)::Any, "/home/juliohm/.julia/v0.6/FFTW/src/FFTW.jl")::Any
  ** incremental compilation may be broken for this module **

I tried testing the package, and all tests are passing. What this warning is referring to? Is it still related to that issue of naming conflict in Base?

using FFTW gives error depending on previous module

Any idea why this happens.

If I load OhMyREPL before FFTW I get this error.

              _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: https://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.7.0-DEV.1673 (2017-09-06 03:45 UTC)
 _/ |\__'_|_|_|\__'_|  |  Commit f32499fa7e (0 days old master)
|__/                   |  x86_64-apple-darwin17.0.0

              _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: https://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.7.0-DEV.1673 (2017-09-06 03:45 UTC)
 _/ |\__'_|_|_|\__'_|  |  Commit f32499fa7e (0 days old master)
|__/                   |  x86_64-apple-darwin17.0.0

julia> using OhMyREPL

julia> using FFTW
WARNING: error while reinitializing value FFTW:
ErrorException("cannot assign variable DFT.FFTW from module Main")
WARNING: requiring "FFTW" in module "Main" did not define a corresponding module.

... but everything seems to work fine if I load FFTW first.

                _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: https://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.7.0-DEV.1673 (2017-09-06 03:45 UTC)
 _/ |\__'_|_|_|\__'_|  |  Commit f32499fa7e (0 days old master)
|__/                   |  x86_64-apple-darwin17.0.0

julia> using FFTW

julia> using OhMyREPL

ComplexF16 doesn't have a method for plan_fft, plan_bfft

trying fft(randn(ComplexF16,10)) gives the error

ERROR: MethodError: no method matching plan_fft(::Array{Complex{Float16},1}, ::UnitRange{Int64})
Closest candidates are:
  plan_fft(::Union{DenseArray{T<:Union{Complex{Float32}, Complex{Float64}},N}, ReinterpretArray{T<:Union{Complex{Float32}, Complex{Float64}},N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray}, ReshapedArray{T<:Union{Complex{Float32}, Complex{Float64}},N,A,MI} where MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray}, SubArray{T<:Union{Complex{Float32}, Complex{Float64}},N,A,I,L} where L where I<:Tuple{Vararg{Union{Int64, AbstractRange{Int64}, AbstractCartesianIndex},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, DenseArray}}, ::Any; flags, timelimit) where {T<:Union{Complex{Float32}, Complex{Float64}}, N} at /home/dsweber/.julia/dev/FFTW/src/fft.jl:619
  plan_fft(::AbstractArray{#s16,N} where N where #s16<:Real, ::Any; kws...) at /home/dsweber/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:199
  plan_fft(::AbstractArray{#s25,N} where N where #s25<:(Complex{#s26} where #s26<:Union{Integer, Rational}), ::Any; kws...) at /home/dsweber/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:201
  ...
Stacktrace:
 [1] #plan_fft#1(::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::Function, ::Array{Complex{Float16},1}) at /home/dsweber/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:52
 [2] plan_fft(::Array{Complex{Float16},1}) at /home/dsweber/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:52
 [3] fft(::Array{Complex{Float16},1}) at /home/dsweber/.julia/packages/AbstractFFTs/7WCaR/src/definitions.jl:50
 [4] top-level scope at none:0

this is somewhat surprising given that a real version fft(randn(Float16,10)) works just fine

Type instability fftshift

It appears that fftshift and ifftshift are type unstable:

julia> @code_warntype fftshift(rand(ComplexF64,64,64))
Body::Any
...
55 ─ %140 = invoke AbstractFFTs.circshift(_2::Array{Complex{Float64},2}, %30::Array{Int64,1})::Any
└───        return %140

Or am I doing something wrong?

I'm running Julia v1.1.0 with FFTW v0.2.4.

Typo in a `plan_inv` method

Reported by @appleparan in JuliaLang/julia#25598:

FFTW.jl/src/fft.jl

Line 700 in 6e26a1e

X = Arra{$Tc}(p.sz)

error combining plan_rfft and views

I seem to be setting a strange error when combining plan_rfft and views for arrays of odd length.

Note: I'm not exactly sure I'm submitting this in the right repo.
I'm on v0.6.2 so technically I should probably file an issue at julialang, but
since I don't think they are looking at 0.6 bug fixes I figured FFTW.jl was the best place to file it.
I tried testing this out on v0.7 but FFTW.jl isn't loading for me.

Anyway, here is a summary of what produces the error.

T = Float64
nside = 129 # no errors when nside = 128

rFFT  = plan_rfft(Array{T,2}(nside, nside))
FFT   = plan_fft(Array{T,2}(nside, nside))
fx    = rand(T, nside, nside, 2)

@views FFT * fx[:,:,1] # works
@views FFT * fx[:,:,2] # works

@views fft(fx[:,:,1])  # works
@views fft(fx[:,:,2])  # works

@views rfft(fx[:,:,1]) # works
@views rfft(fx[:,:,2]) # works

@views rFFT * fx[:,:,1] # works
@views rFFT * fx[:,:,2] # <--- error

Where the last line gives the following error.

ERROR: ArgumentError: FFTW plan applied to array with wrong memory alignment
Stacktrace:
 [1] assert_applicable(::Base.DFT.FFTW.rFFTWPlan{Float64,-1,false,2}, ::SubArray{Float64,2,Array{Float64,3},Tuple{Base.Slice{Base.OneTo{Int64}},Base.Slice{Base.OneTo{Int64}},Int64},true}) at ./fft/FFTW.jl:341
 [2] *(::Base.DFT.FFTW.rFFTWPlan{Float64,-1,false,2}, ::SubArray{Float64,2,Array{Float64,3},Tuple{Base.Slice{Base.OneTo{Int64}},Base.Slice{Base.OneTo{Int64}},Int64},true}) at ./fft/FFTW.jl:704

Note: Everything works if I remove @views or set nside to an even number.

julia> versioninfo()
Julia Version 0.6.2
Commit d386e40 (2017-12-13 18:08 UTC)
Platform Info:
  OS: Linux (x86_64-redhat-linux)
  CPU: Intel(R) Xeon(R) CPU E5-2699 v3 @ 2.30GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, haswell)

Do not import deprecated bindings

Recent CI logs on nightlies show hundreds of spurious warnings because the package imports deprecated bindings, see, e.g., https://travis-ci.org/JuliaMath/FFTW.jl/jobs/254462935#L785 While these messages are going to cleared, they are an indication that after JuliaLang/julia#22763 deprecated bindings shouldn't be imported at all. An example of fix for SpecialFunctions.jl is at JuliaMath/SpecialFunctions.jl#36

Remove 0.6 Versions?

This package should not not be installable in Julia 0.6, see JuliaImages/ImageCore.jl#56

Is there a way to remove the old versions that allows installation under 0.6? If not please close. But in the future, code that is split of base should not be installable in a stable version of Julia.

FFTW is GPL. Mention in licence file?!

and probably also README?

I think "GPL applies to dependency" should be prominently added to license file. Before MIT.

Only seeing "MIT license" is misleading, and users may want to know about GPL or get in legal trouble otherwise(?).

I think this also applies to DSP.jl (but not AbstractFFTs.jl).

Support FFT of split complex representation

Moved from JuliaLang/julia#12398

As shown by @simonster (https://github.com/simonster/StructsOfArrays.jl), Structure of Array is much easier to vectorize. Using StructOfArrays(Complex64) and @simd I can see a speed up of >2x. However, it seems that this is not very well supported by our fft API.

As @simonster suggested, I tried to implement FFT on StructOfArrays using fftw_plan_gure64_split_dft. The non-plan version works greet. However, I get SegFault when trying to use the plan interface. It seems that fftw assumes that the relative address between the real and complex part is fixed and therefore is not accessing the right address when I pass in a different array.

Is there a fftw interface that can be used to implement this?

@stevengj

Provide `rfft!` and `irfft!` through a submodule

Is it desirable to have a submodule living in FFTW.jl to provide the inplace real-to-complex and complex-to-real transformations?

The functionality is already coded in InpalceRealFFT.jl and could remain living as a separate package. Some people expressed the desire to have it in FFTW.jl
Basically, a PaddedArray type is created to deal with proper padding of the real data, and methods rfft!,irff!,brfft!,plan_rfft!,plan_irfft! and plan_brfft! are created to work with AbstractPaddedArrays, an interface to provide custom PaddedArray types.

I could make a PR if this is desirable.

speed regression compared to v0.6

I'm seeing a significant slowdown with FFTW in v0.7 as compared to v0.6. Any idea what is going on? Note: I'm using MKL for my ffts.

Here are the timings for v0.7 .... (I would normally use BenchmarkTools to do the timings but it currently throws an error on v0.7)

julia> using FFTW

julia> FFTW.set_num_threads(8);

julia> m = rand(Float32,16384,16384);

julia> rfft(m); # warmup

julia> @time rfft(m)
  4.607740 seconds (456 allocations: 1.000 GiB, 0.92% gc time)

Here are the timings for v0.6 ....

julia> using FFTW

julia> FFTW.set_num_threads(8);

julia> m = rand(Float32,16384,16384);

julia> rfft(m); # warmup

julia> @time rfft(m)
  1.473979 seconds (426 allocations: 1.000 GiB, 4.71% gc time)

Version info for v0.7

julia> versioninfo()
Julia Version 0.7.0-DEV.1957
Commit c3a3a1c89f* (2017-09-25 23:52 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin17.0.0)
  CPU: Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz
  WORD_SIZE: 64
  BLAS: libmkl_rt
  LAPACK: libmkl_rt
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, broadwell)
Environment:
  JULIA_NUM_THREADS = 8

Version info for v0.6

Julia Version 0.6.1-pre.3
Commit 4aa661a0c1* (2017-09-14 17:43 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin17.0.0)
  CPU: Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz
  WORD_SIZE: 64
  BLAS: libmkl_rt
  LAPACK: libmkl_rt
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, broadwell)

FFTW build fail on ARMv7

Hello,

I have currently an issue when building FFTW module in Julia on a ARMv7 (with Yocto embedded linux).
I get the following output:

(v1.0) pkg> build FFTW
  Building Conda → `~/.julia/packages/Conda/CpuvI/deps/build.log`
  Building FFTW ─→ `~/.julia/packages/FFTW/p7sLQ/deps/build.log`
┌ Error: Error building `FFTW`: 
│ ┌ Warning: platform_key() is deprecated, use platform_key_abi() from now on
│ │   caller = ip:0x0
│ └ @ Core :-1
│ ┌ Warning: Could not extract the platform key of https://github.com/JuliaMath/FFTWBuilder/releases/download/v3.3.8+1/FFTW.arm-linux-gnueabihf.tar.gz; continuing...
│ └ @ BinaryProvider ~/.julia/packages/BinaryProvider/4F5Hq/src/Prefix.jl:185
│ ERROR: LoadError: LoadError: Could not unpack /home/root/.julia/packages/FFTW/p7sLQ/deps/usr/downloads/FFTW.arm-linux-gnueabihf.tar.gz into /home/root/.julia/packages/FFTW/p7sLQ/deps/usr
│ Stacktrace:
│  [1] error(::String) at ./error.jl:33
│  [2] #unpack#94(::Bool, ::Function, ::String, ::String) at /home/root/.julia/packages/BinaryProvider/4F5Hq/src/PlatformEngines.jl:660
│  [3] #unpack at ./tuple.jl:0 [inlined]
│  [4] #install#129(::Prefix, ::String, ::Bool, ::Bool, ::Bool, ::Function, ::String, ::String) at /home/root/.julia/packages/BinaryProvider/4F5Hq/src/Prefix.jl:347
│  [5] (::getfield(BinaryProvider, Symbol("#kw##install")))(::NamedTuple{(:prefix, :force, :verbose),Tuple{Prefix,Bool,Bool}}, ::typeof(install), ::String, ::String) at ./tuple.jl:0
│  [6] top-level scope at /home/root/.julia/packages/FFTW/p7sLQ/deps/build_fftw.jl:37
│  [7] include at ./boot.jl:317 [inlined]
│  [8] include_relative(::Module, ::String) at ./loading.jl:1044
│  [9] include(::Module, ::String) at ./sysimg.jl:29
│  [10] include(::String) at ./client.jl:392
│  [11] top-level scope at /home/root/.julia/packages/FFTW/p7sLQ/deps/build.jl:48
│  [12] include at ./boot.jl:317 [inlined]
│  [13] include_relative(::Module, ::String) at ./loading.jl:1044
│  [14] include(::Module, ::String) at ./sysimg.jl:29
│  [15] include(::String) at ./client.jl:392
│  [16] top-level scope at none:0
│ in expression starting at /home/root/.julia/packages/FFTW/p7sLQ/deps/build_fftw.jl:33
│ in expression starting at /home/root/.julia/packages/FFTW/p7sLQ/deps/build.jl:19
│ tar: unrecognized option '--directory=/home/root/.julia/packages/FFTW/p7sLQ/deps/usr'
│ BusyBox v1.23.1 (2016-01-07 07:47:07 PST) multi-call binary.
│ 
│ Usage: tar -[cxtZzJjahmvO] [-X FILE] [-T FILE] [-f TARFILE] [-C DIR] [FILE]...
└ @ Pkg.Operations /buildworker/worker/package_linuxarmv7l/build/usr/share/julia/stdlib/v1.0/Pkg/src/Operations.jl:1097

Any clue to address this ?
Thank you in advance,
BR

FFTW planner is not thread safe.

Moved from JuliaLang/julia#17972

Having fft/bfft/ifft/etc. calls in a threaded region exposes the fact that the planning portion of the fft call is not thread-safe in fftw. Below is a potential patch to dft.jl if you just want to lock the planner.

global planner_mutex = nothing

function __init__()
    global planner_mutex = Base.Threads.Mutex()
end

# implementations only need to provide plan_X(x, region)
# for X in (:fft, :bfft, ...):
for f in (:fft, :bfft, :ifft, :fft!, :bfft!, :ifft!, :rfft)
    pf = Symbol("plan_", f)
    @eval begin
        function $f(x::AbstractArray)
            Base.Threads.lock!(planner_mutex)
            the_plan = $pf(x)
            Base.Threads.unlock!(planner_mutex)
            the_plan * x
        end
        function $f(x::AbstractArray, region)
            Base.Threads.lock!(planner_mutex)
            the_plan = $pf(x, region)
            Base.Threads.unlock!(planner_mutex)
            the_plan * x
        end
        function $pf(x::AbstractArray; kws...)
            Base.Threads.lock!(planner_mutex)
            the_plan = $pf(x, 1:ndims(x); kws...)
            Base.Threads.unlock!(planner_mutex)
            the_plan
        end
    end
end

improve error message for plan_ifft!(v::Vector{T<:Real})

From JuliaLang/julia#19087

This confused me for a second:

julia> plan_ifft!(rand(10))
ERROR: MethodError: `plan_bfft!` has no method matching plan_bfft!(::Array{Float64,1}, ::UnitRange{Int64})
Closest candidates are:
  plan_bfft!(::Any, ::Any, ::Any)
  plan_bfft!(::Any, ::Any, ::Any, ::Any)
  plan_bfft!{T<:Union{Complex{Float32},Complex{Float64}},N}(::Union{DenseArray{T<:Union{Complex{Float32},Complex{Float64}},N},SubArray{T<:Union{Complex{Float32},Complex{Float64}},N,A<:DenseArray{T,N},I<:Tuple{Vararg{Union{Colon,Int64,Range{Int64}}}},LD}}, ::Any)
  ...
 in plan_ifft! at dft.jl:277
 in plan_ifft! at dft.jl:38

I think plan_ifft!(v::Vector{T<:Real}) should be overriden to give an error message saying that the input has to be complex.

Broken link to the documentation of AbstractFFTs in docs

Currently the link in docs/src/fft.md points to https://juliamath.github.io/AbstractFFTs.jl/stable/api.html, however the link appears to have moved to https://juliamath.github.io/AbstractFFTs.jl/stable/api/

0.7 master: LoadError: LoadError: ArgumentError: libfftw_threads is not a valid key for type Symbol

I'm getting the following error when trying to a Pkg.update() in the lastest Julia

INFO: Upgrading FFTW: v0.1.0 => v0.1.1
INFO: Upgrading LowRankApprox: v0.0.2 => v0.1.0
INFO: Upgrading NaNMath: v0.2.6 => v0.3.0
INFO: Upgrading ProgressMeter: v0.4.0 => v0.5.2
INFO: Upgrading RecipesBase: v0.2.2 => v0.2.3
INFO: Upgrading SHA: v0.5.1 => v0.5.2
INFO: Upgrading StaticArrays: v0.6.2 => v0.6.6
INFO: Upgrading StatsBase: v0.19.0 => v0.19.2
INFO: Building FFTW

================================[ ERROR: FFTW ]=================================

LoadError: LoadError: ArgumentError: libfftw_threads is not a valid key for type Symbol
in expression starting at /Users/solver/.julia/v0.7/FFTW/deps/build_fftw.jl:36
in expression starting at /Users/solver/.julia/v0.7/FFTW/deps/build.jl:20

julia> versioninfo()
Julia Version 0.7.0-DEV.2784
Commit 1046736ab0 (2017-12-07 07:47 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin17.2.0)
  CPU: Intel(R) Core(TM) i5-7600K CPU @ 3.80GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, skylake)
Environment:
  JULIA_VERSION = 0.6

`plan.pinv` undefined reference

Feel free to close this if this is expected/tolerated. I just happened across this error when trying to serialize an object that contained an FFTPlan, and the serializer (BSON) trips the undefined reference error. It'd be nice if it didn't error out, but I also understand it's a weird case.

using FFTW

plan = plan_fft(rand(20,20))
plan.pinv

ERROR: UndefRefError: access to undefined reference

`irfft` not supported for `PaddedView` but `rfft` is

PaddedView arrays are partly supported

using AbstractFFTs
using PaddedViews

shortsamp = cos.(0:256 * pi / 16);
paddedsamp = PaddedView(0.0f0, shortsamp, (512,)) 
fftshortsamp = rfft(shortsamp);
fftpaddedsamp = rfft(paddedsamp);  # RFFT of padded array OK
paddedfftshortsamp = PaddedView(0.0f0, fftshortsamp, (257,)) ;
irfft(fftpaddedsamp, 512);
irfft(paddedfftshortsamp, 512);  ## IRFFT of padded array not OK

results in an error at the last line

MethodError: no method matching plan_brfft(::PaddedView{Complex{Float64},1,Tuple{Base.OneTo{Int64}},Array{Complex{Float64},1}}, ::Int64, ::UnitRange{Int64})
Closest candidates are:
  plan_brfft(!Matched::Union{DenseArray{Complex{Float32},N}, ReinterpretArray{Complex{Float32},N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray}, ReshapedArray{Complex{Float32},N,A,MI} where MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray}, SubArray{Complex{Float32},N,A,I,L} where L where I<:Tuple{Vararg{Union{Int64, AbstractRange{Int64}, AbstractCartesianIndex},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, DenseArray}}, ::Integer, ::Any; flags, timelimit) where N at /home/dan/.julia/packages/FFTW/2okGQ/src/fft.jl:678
  plan_brfft(!Matched::Union{DenseArray{Complex{Float64},N}, ReinterpretArray{Complex{Float64},N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray}, ReshapedArray{Complex{Float64},N,A,MI} where MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray}, SubArray{Complex{Float64},N,A,I,L} where L where I<:Tuple{Vararg{Union{Int64, AbstractRange{Int64}, AbstractCartesianIndex},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, ReshapedArray{T,N,A,MI} where MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int64},N} where N} where A<:Union{ReinterpretArray{T,N,S,A} where S where A<:Union{SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, SubArray{T,N,A,I,true} where I<:Union{Tuple{Vararg{Real,N} where N}, Tuple{AbstractUnitRange,Vararg{Any,N} where N}} where A<:DenseArray where N where T, DenseArray} where N where T, DenseArray}}, ::Integer, ::Any; flags, timelimit) where N at /home/dan/.julia/packages/FFTW/2okGQ/src/fft.jl:678
  plan_brfft(::AbstractArray, ::Integer; kws...) at /home/dan/.julia/packages/AbstractFFTs/PUqOK/src/definitions.jl:285

Stacktrace:
 [1] #plan_irfft#19(::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::Function, ::PaddedView{Complex{Float64},1,Tuple{Base.OneTo{Int64}},Array{Complex{Float64},1}}, ::Int64, ::UnitRange{Int64}) at /home/dan/.julia/packages/AbstractFFTs/PUqOK/src/definitions.jl:334
 [2] plan_irfft(::PaddedView{Complex{Float64},1,Tuple{Base.OneTo{Int64}},Array{Complex{Float64},1}}, ::Int64, ::UnitRange{Int64}) at /home/dan/.julia/packages/AbstractFFTs/PUqOK/src/definitions.jl:334
 [3] #plan_irfft#18(::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::Function, ::PaddedView{Complex{Float64},1,Tuple{Base.OneTo{Int64}},Array{Complex{Float64},1}}, ::Int64) at /home/dan/.julia/packages/AbstractFFTs/PUqOK/src/definitions.jl:285
 [4] plan_irfft(::PaddedView{Complex{Float64},1,Tuple{Base.OneTo{Int64}},Array{Complex{Float64},1}}, ::Int64) at /home/dan/.julia/packages/AbstractFFTs/PUqOK/src/definitions.jl:285
 [5] irfft(::PaddedView{Complex{Float64},1,Tuple{Base.OneTo{Int64}},Array{Complex{Float64},1}}, ::Int64) at /home/dan/.julia/packages/AbstractFFTs/PUqOK/src/definitions.jl:283
 [6] top-level scope at In[62]:10

It seems like if we do the RFFT we should also also be able to invert it. Perhaps it's as simple as extending that union type. I can prepare a patch for this but want to check in whether that is sane first.

Spurious incremental compilation may be broken messages on Julia 0.6

I noticed it on this page of some docs.

I think this is probably only a problem on Travis (can’t get it locally) but I’m just curious...