Preprocess the FFT twiddle factors

[ValarDragon]

You can preprocess the twiddle factors on the domain for FFTs. This halves the number of multiplications required for a FFT. You just have to align the twiddle factors with how they get used.

Here is the relevant code in libiop that does these: Creating the cache: https://github.com/scipr-lab/libiop/blob/master/libiop/algebra/field_subset/subgroup.tcc#L118

Using the cache: https://github.com/scipr-lab/libiop/blob/master/libiop/algebra/fft.tcc#L309

[ValarDragon]

The current state of the FFT code is that the twiddle factors are computed once at the beginning of every FFT, and then re-used in every iteration of the FFT. Using preprocessing / if there are multiple FFTs being done over the same domain, then the twiddle factors could be computed just once, and re-used throughout all the FFTs.

This would save N multiplications per FFT. (Bringing the number of multiplications down from N + N (log(N) / 2 to instead N log(N) / 2)

[erwanor]

Hey, I would like to help with this if no one is working on it; is this still wanted?

[Pratyush]

Yes, definitely!

[Pratyush]

Hi @erwanor, did you get a chance to take a stab at this? FWIW, the original code base we adapted the code from (https://crates.io/crates/fffft) has implemented using precomputation; let me know if you'd like more details on this.

[Aphoh]

@Pratyush I'm willing to hop on this if @erwanor is busy.

This would require an API change, right? We could lazily store the twiddle factors on the Radix2EvaluationDomain or make new methods for both precomputing them and doing the fft with them precomputed.

[erwanor]

@Pratyush apologies for the late reply, somehow missed this! @Aphoh yeah I meant to take care of this earlier but got busy, so feel free to take a stab at it :)

[Pratyush]

@Aphoh that would be great. I would prefer not to store the twiddle factors in Domains as it makes them non-copy. Maybe we can work around this with the following two-phase API:

First, we add associated types and methods to EvaluationDomain that use this precomputed material for FFTs/IFFTs:

pub trait EvaluationDomain<F: FftField> {

	// existing stuff

	// new
	
	type FFTPrecomputation;
	type IFFTPrecomputation;
	
	fn precompute_fft(&self) → Self::FFTPrecomputation;
	
	fn precompute_ifft(&self) → Self::IFFTPrecomputation;
	
    /// `domain` must be a subdomain of `self`.
	fn precompute_fft_for_subdomain(&self, domain: &Self) → ...;
	
	/// `domain` must be a subdomain of `self`.
	fn precompute_ifft_for_subdomain(&self, domain: &Self) → ...;
	
    fn fft_with_precomputation(..., precomp: &Self::FFTPrecomputation) {
    }
    
    fn ifft_with_precomputation(..., precomp: &Self::IFFTPrecomputation) {
    }
    
    fn fft_with_precomputation_in_place(..., precomp: &Self::FFTPrecomputation) {
    }
    
    fn ifft_with_precomputation_in_place(..., precomp: &Self::IFFTPrecomputation) {
    }
}

Each implementor of EvaluationDomain can provide their own instantiation of the associated types. For example, to begin with, the Radix2EvaluationDomain can provide the actual twiddle factors:

struct FFTPrecomputation<F: FftField, D: EvaluationDomain<F>> {
	// stuff
}

struct IFFTPrecomputation<F: FftField, D: EvaluationDomain<F>> {
	// stuff
}

While other domains can set these to () initially (and add implementations later on).