Concrete-FFT is a pure Rust high performance fast Fourier transform library
that processes vectors of sizes that are powers of two. It was made to be used
as a backend in Zama's concrete library.
This library provides two FFT modules: - The ordered module FFT applies a forward/inverse FFT that takes its input in standard order, and outputs the result in standard order. For more detail on what the FFT computes, check the ordered module-level documentation. - The unordered module FFT applies a forward FFT that takes its input in standard order, and outputs the result in a certain permuted order that may depend on the FFT plan. On the other hand, the inverse FFT takes its input in that same permuted order and outputs its result in standard order. This is useful for cases where the order of the coefficients in the Fourier domain is not important. An example is using the Fourier transform for vector convolution. The only operations that are performed in the Fourier domain are elementwise, and so the order of the coefficients does not affect the results.
std (default): This enables runtime arch detection for accelerated SIMD
instructions, and an FFT plan that measures the various implementations to
choose the fastest one at runtime.nightly: This enables unstable Rust features to further speed up the FFT,
by enabling AVX512F instructions on CPUs that support them. This feature
requires a nightly Rust
toolchain.serde: This enables serialization and deserialization functions for the
unordered plan. These allow for data in the Fourier domain to be serialized
from the permuted order to the standard order, and deserialized from the
standard order to the permuted order. This is needed since the inverse
transform must be used with the same plan that computed/deserialized the
forward transform (or more specifically, a plan with the same internal base
FFT size).```rust use concretefft::c64; use concretefft::ordered::{Plan, Method}; use dynstack::{DynStack, GlobalMemBuffer, ReborrowMut}; use numcomplex::ComplexFloat; use std::time::Duration;
const N: usize = 4; let plan = Plan::new(4, Method::Measure(Duration::frommillis(10))); let mut scratchmemory = GlobalMemBuffer::new(plan.fftscratch().unwrap()); let mut stack = DynStack::new(&mut scratchmemory);
let data = [ c64::new(1.0, 0.0), c64::new(2.0, 0.0), c64::new(3.0, 0.0), c64::new(4.0, 0.0), ];
let mut transformedfwd = data; plan.fwd(&mut transformedfwd, stack.rb_mut());
let mut transformedinv = transformedfwd; plan.inv(&mut transformedinv, stack.rbmut());
for (actual, expected) in transformed_inv.iter().map(|z| z / N as f64).zip(data) { assert!((expected - actual).abs() < 1e-9); } ```
This software is distributed under the BSD-3-Clause-Clear license with an exemption that gives rights to use our patents for research, evaluation and prototyping purposes, as well as for your personal projects.
If you want to use Concrete in a commercial product however, you will need to purchase a separate commercial licence.
If you have any questions, please contact us at hello@zama.ai.