algebra icon indicating copy to clipboard operation
algebra copied to clipboard

Allow out-of-order FFT

Open weikengchen opened this issue 3 years ago • 4 comments

The codebase has implementations of the FFT. However, throughout the public interface, one can only use the "II" mode, in-order input, and in-order output. OI and IO are basically not used in the entire system.

This is not suitable for some IFFT that prefers an in-order input, and out-of-order output, and then immediately performs some other operations and then FFT it back.

Proposal: relax the IO/OI interfaces to be "pub" in radix2 so people can use them. Particularly, note that users do not even have access to the enum "fft::FFTOrder"

weikengchen avatar Nov 05 '22 21:11 weikengchen

Let me know if we want to move ahead with it.

weikengchen avatar Nov 05 '22 21:11 weikengchen

ADD: one can also bypass this limitation by preprocessing the data, e.g., perform a bit reversal to cancel the other bit reversal implemented in arkworks-rs.

weikengchen avatar Nov 05 '22 22:11 weikengchen

I think we can accept it, but the issue is that we don't have support for that on the multi-radix FFTs (AFAIK). I think if we have a good solution there then it makes sense.

Pratyush avatar Nov 06 '22 01:11 Pratyush

I think we will leave it for the release after v0.4.0

weikengchen avatar Nov 06 '22 20:11 weikengchen