Support 2D and 3D FFT?

[davidssmith]

Does this crate support 2D and 3D FFTs?

[ejmahler]

Not directly. But you can compute a Nd FFT by computing FFTs for the rows, transposing, doing FFTs for the columns, transposing again, etc. check out the “transpose” crate for a convenient transpose routine

…

On Sun, Oct 13, 2019 at 10:34 AM David Smith ***@***.***> wrote: Does this crate support 2D and 3D FFTs? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#49?email_source=notifications&email_token=AAI2M6XE4H4B3VWS6RM4O2TQONL4FA5CNFSM4JAH352KYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HROLU3A>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAI2M6V3UKVHF5UWUQM4PDTQONL4FANCNFSM4JAH352A> .

[davidssmith]

Is there a speed penalty for doing it this way, or is this how libraries like FFTW do 2D transforms under the hood?

[ejmahler]

I’ll have to look into it but my understanding is that aside from incremental optimizations, you aren’t going to get any crazy improvements by using a specialized algorithm

…

On Sun, Oct 13, 2019 at 12:51 PM David Smith ***@***.***> wrote: Is there a speed penalty for doing it this way, or is this how libraries like FFTW do 2D transforms under the hood? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#49?email_source=notifications&email_token=AAI2M6QSBNUTZG4QIHWYPHLQON32ZA5CNFSM4JAH352KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEBC6P3A#issuecomment-541452268>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAI2M6QDQKRXX3YHL33VLSDQON32ZANCNFSM4JAH352A> .

[Boscop]

Btw, FFTS supports N-dimensional FFT: https://github.com/anthonix/ffts

[alvarozamora]

Bumping this. Is there a better crate for doing N-dimensional FFTs in Rust. Is there an example of using this + transpose crate?

[cavemanloverboy]

Not directly. But you can compute a Nd FFT by computing FFTs for the rows, transposing, doing FFTs for the columns, transposing again, etc. check out the “transpose” crate for a convenient transpose routine
…
On Sun, Oct 13, 2019 at 10:34 AM David Smith @.***> wrote: Does this crate support 2D and 3D FFTs? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#49?email_source=notifications&email_token=AAI2M6XE4H4B3VWS6RM4O2TQONL4FA5CNFSM4JAH352KYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HROLU3A>, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAI2M6V3UKVHF5UWUQM4PDTQONL4FANCNFSM4JAH352A .

I tried doing this but it's kind of slow. I spend 10x time on transposes vs the FFTs.

[ejmahler]

One approach that could take less time is:

For each dimension, copy strided elements into a contiguous scratch buffer, then compute the FFT, then copy them back into their original strided location.

That would let you do the FFT without any transposes, and it's highly parallelizable.

Once you do that, an obvious next step to improve cache friendliness would be "loop tiling" IE instead of copying a single column into a single scratch buffer, copy 8 columns into 8 scratch buffers, and then compute 8 FFTs. By doing 8 columns at once, you can copy 8 contiguous elements from each row, making your code more cache friendly.

If you try this and it works well, let me know, I'd be happy to include it! BTW, this repository is obsolete, rustFFT now happens in https://github.com/ejmahler/RustFFT