{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/6193","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/6193/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/6193/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/6193/events","html_url":"https://github.com/JuliaLang/julia/pull/6193","id":29615258,"number":6193,"title":"WIP: new DFT api","user":{"login":"stevengj","id":2913679,"avatar_url":"https://avatars.githubusercontent.com/u/2913679?v=3","gravatar_id":"","url":"https://api.github.com/users/stevengj","html_url":"https://github.com/stevengj","followers_url":"https://api.github.com/users/stevengj/followers","following_url":"https://api.github.com/users/stevengj/following{/other_user}","gists_url":"https://api.github.com/users/stevengj/gists{/gist_id}","starred_url":"https://api.github.com/users/stevengj/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stevengj/subscriptions","organizations_url":"https://api.github.com/users/stevengj/orgs","repos_url":"https://api.github.com/users/stevengj/repos","events_url":"https://api.github.com/users/stevengj/events{/privacy}","received_events_url":"https://api.github.com/users/stevengj/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/JuliaLang/julia/labels/decision","name":"decision","color":"F08000"},{"url":"https://api.github.com/repos/JuliaLang/julia/labels/feature","name":"feature","color":"02e10c"}],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/JuliaLang/julia/milestones/8","labels_url":"https://api.github.com/repos/JuliaLang/julia/milestones/8/labels","id":303801,"number":8,"title":"0.4","description":"","creator":{"login":"vtjnash","id":330950,"avatar_url":"https://avatars.githubusercontent.com/u/330950?v=3","gravatar_id":"","url":"https://api.github.com/users/vtjnash","html_url":"https://github.com/vtjnash","followers_url":"https://api.github.com/users/vtjnash/followers","following_url":"https://api.github.com/users/vtjnash/following{/other_user}","gists_url":"https://api.github.com/users/vtjnash/gists{/gist_id}","starred_url":"https://api.github.com/users/vtjnash/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vtjnash/subscriptions","organizations_url":"https://api.github.com/users/vtjnash/orgs","repos_url":"https://api.github.com/users/vtjnash/repos","events_url":"https://api.github.com/users/vtjnash/events{/privacy}","received_events_url":"https://api.github.com/users/vtjnash/received_events","type":"User","site_admin":false},"open_issues":102,"closed_issues":60,"state":"open","created_at":"2013-04-05T16:15:28Z","updated_at":"2015-01-13T04:00:35Z","due_on":"2015-02-10T08:00:00Z","closed_at":null},"comments":68,"created_at":"2014-03-18T02:09:53Z","updated_at":"2015-01-14T19:48:51Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/JuliaLang/julia/pulls/6193","html_url":"https://github.com/JuliaLang/julia/pull/6193","diff_url":"https://github.com/JuliaLang/julia/pull/6193.diff","patch_url":"https://github.com/JuliaLang/julia/pull/6193.patch"},"body":"This is not quite ready to merge yet, but I wanted to bring it to your attention to see what you think.  It is a rewritten DFT API that provides:\r\n\r\n* `p = plan_fft(x)` (and similar) now returns a subtype of `Base.DFT.Plan`.  It acts like a linear operator: you can apply it to an existing array with `p * x`, and apply it to a preallocated output array with `A_mul_B!(y, p, x)`.  You can apply the inverse plan with `p \\ x` or `inv(p) * x`.\r\n* It is easy to add new FFT algorithm implementations for specific numeric and array types...\r\n\r\nPartly since we have discussed moving FFTW to a module at some point for licensing reasons, and partly to support numeric types like `BigFloat`, the patch also includes a pure-Julia FFT implementation, with the following features.\r\n\r\n* One-dimensional transforms of arbitrary `AbstractVector`s of arbitrary `Complex` types (including `BigFloat`), with fast algorithms for all sizes (including prime sizes).  Multidimensional transforms of arbitrary `StridedArray` subtypes.\r\n* Uses code generation (a baby version of the FFTW code generator) in Julia to generate kernels for use as base cases of the transforms; algorithms in general are FFTW1-like.\r\n* Performance is reasonable. For moderate-power-of-two sizes, it is within a factor of 2 or so of FFTW, with the difference mainly due to the lack of SIMD.   ~~For non-power-of-two sizes, the performance is several times worse, but I suspect that there may be some fixable compiler problem there (a good stress test for the compiler).~~ (Non-power-of-two sizes seem fine with latest Julia).\r\n* `import FFTW` is enough to automatically switch over to the FFTW algorithms for supported types.\r\n\r\nMajor to-do items:\r\n- [x] Documentation\r\n- [x] More test cases (implemented a self-test algorithm by Funda Ergün)\r\n- [ ] Native Julia `rfft` support.\r\n- [ ] Native Julia in-place transforms. (The 1d FFT algorithm here is out-of-place, but it could act \"in-place\" via a buffer.  The multi-dim FFTs only need a buffer of length `maximum(size(x))`.)\r\n\r\ncc: @JeffBezanson, @timholy"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/69979076","html_url":"https://github.com/JuliaLang/julia/pull/6193#issuecomment-69979076","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/6193","id":69979076,"user":{"login":"stevengj","id":2913679,"avatar_url":"https://avatars.githubusercontent.com/u/2913679?v=3","gravatar_id":"","url":"https://api.github.com/users/stevengj","html_url":"https://github.com/stevengj","followers_url":"https://api.github.com/users/stevengj/followers","following_url":"https://api.github.com/users/stevengj/following{/other_user}","gists_url":"https://api.github.com/users/stevengj/gists{/gist_id}","starred_url":"https://api.github.com/users/stevengj/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stevengj/subscriptions","organizations_url":"https://api.github.com/users/stevengj/orgs","repos_url":"https://api.github.com/users/stevengj/repos","events_url":"https://api.github.com/users/stevengj/events{/privacy}","received_events_url":"https://api.github.com/users/stevengj/received_events","type":"User","site_admin":false},"created_at":"2015-01-14T19:48:51Z","updated_at":"2015-01-14T19:48:51Z","body":"Hmm, I'm seeing some further type-inference problems, analogous to those in #9772.  Julia is having a hard time figuring out the FFT return types for some reason."}}