Lossless FFTs Using Posit Arithmetic

The Fast Fourier Transform (FFT) is required for chemistry, weather, defense, and signal processing for seismic exploration and radio astronomy. It is communication-bound, making supercomputers thousands of times slower at FFTs then at dense linear algebra. The key to accelerating FFTs is to minimize bits per datum without sacrificing accuracy. The 16-bit fixed point and IEEE float type lack sufficient accuracy for 1024- and 4096-point FFTs of data from analog-to-digital converters. We show that the 16-bit posit, with higher accuracy and larger dynamic range, can perform FFTs so accurately that a forward-inverse FFT restores the original signal perfectly. “Reversible” FFTs with posits are lossless, eliminating the need for 32-bit or higher precision. Similarly, 32-bit posit FFTs can replace 64-bit float FFTs for many HPC tasks. Speed, energy efficiency, and storage costs can thus be improved by 2 $$\times $$ for a broad range of HPC workloads.