befft is C library for radix 2 Fast Fourier Transform (FFT) of vectors in double precision floating points with bounded error. It implements the Cooley-Tukey FFT (see references below) for vectors of length 2^n (where n>=1 is an integer).

befft has no internal engine for computing the 2^n-th order roots of units for arbitrary n. For n<=12 roots of units are pre-computed and stored in a table. For n>=13, the 2^n-th order roots of units have to be provided to befft.

Optionally, befft can be linked with the ball arithmetic library arb (https://arblib.org/) in which cases it uses arb to compute the 2^n*-th order roots of units for n>=13.

Dependencies

By default, befft has no dependencies, but can be linked with arb to use its engine for getting roots of units.

Compilation

The library can be compiled with:

make

or

make withArb

to be linked with Arb (in which case the latter library together with its dependencies have to be installed on the system).

Source organisation

src contains the source code. The main header file is befft.h.

examples contains simple examples of use in C.

Licence

befft is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. See http://www.gnu.org/licenses/.

References

befft library is based on

@article{brisebarre2020error, title={Error analysis of some operations involved in the Cooley-Tukey Fast Fourier Transform}, author={Brisebarre, Nicolas and Jolde{\c{s}}, Mioara and Muller, Jean-Michel and Nane{\c{s}}, Ana-Maria and Picot, Joris}, journal={ACM Transactions on Mathematical Software (TOMS)}, volume={46}, number={2}, pages={1--27}, year={2020}, publisher={ACM New York, NY, USA} }

and

@book{muller2018handbook, title={Handbook of floating-point arithmetic}, author={Muller, Jean-Michel and Brisebarre, Nicolas and De Dinechin, Florent and Jeannerod, Claude-Pierre and Lefevre, Vincent and Melquiond, Guillaume and Revol, Nathalie and Stehl{'e}, Damien and Torres, Serge and others}, volume={1}, year={2018}, publisher={Springer} }

Other usefull references:

@article{jeannerod2018relative, title={On relative errors of floating-point operations: optimal bounds and applications}, author={Jeannerod, Claude-Pierre and Rump, Siegfried M}, journal={Mathematics of Computation}, volume={87}, number={310}, pages={803--819}, year={2018} } (HAL link: https://hal.inria.fr/hal-00934443v2 )