Testing the Sharpness of Known Error Bounds on the Fast Fourier Transform

Nicolas Brisebarre, Jean-Michel Muller, Joris Picot

TL;DR

This paper investigates the accuracy of error bounds for the Fast Fourier Transform (FFT) algorithm. The authors find that while traditional "global" error bounds are often overly pessimistic, "local" bounds derived from interval arithmetic, though computationally more expensive, provide tighter estimates in practice. This suggests interval arithmetic can be a valuable tool for applications requiring high accuracy in FFT computations.

What Problem Does This Paper Address?

The Fast Fourier Transform (FFT) is a cornerstone algorithm in science and engineering, but its implementation in floating-point arithmetic introduces rounding errors. For certain applications, like large integer multiplication, it's crucial to know how much these errors can affect the final result. Existing methods for bounding these errors fall into two categories: global bounds, which are valid for any input but can be quite loose, and local bounds derived from interval arithmetic, which are specific to a given input but can suffer from overestimation due to the nature of interval arithmetic itself. This paper aims to compare these two approaches to understand which provides a more practical and tighter error estimate for the FFT.

Methods

The authors compare two main approaches for error bounding:

  1. Global Error Bounds: These are theoretical bounds derived a priori and are valid for all possible inputs. The paper references existing work on these bounds for the Cooley-Tukey FFT algorithm.
  2. Local Error Bounds using Interval Arithmetic (IA): This approach computes the FFT using interval arithmetic, where numbers are represented as intervals. This process inherently produces an interval that is guaranteed to contain the exact result. The width of this interval provides a local error bound specific to the input.

The study involves intensive numerical computations using the radix-2 Cooley-Tukey FFT algorithm. They implement the algorithm in both standard floating-point (binary64/double-precision) and interval arithmetic. To obtain "exact" reference values for comparison, they use high-precision arbitrary-precision arithmetic libraries (Arblib). They then compare the computed errors from floating-point arithmetic with both the global theoretical bounds and the local bounds derived from interval arithmetic.

Datasets

Not discussed in the paper. The authors generate random input vectors for their numerical investigations.

Key Insights and Ideas

  • Global bounds are often too pessimistic: The paper's experiments show that the actual errors encountered in floating-point FFT computations are frequently much smaller than what the best-known global error bounds predict. This means that a theoretically "safe" bound might incorrectly flag a computation as inaccurate when it's actually well within acceptable limits.
  • Interval arithmetic provides tighter local bounds: Despite the known tendency of interval arithmetic to overestimate, the local error bounds it produces for the FFT are, in practice, significantly smaller than the global bounds. This is a key finding, as it suggests that for applications needing precise error control, interval arithmetic can offer a more realistic assessment.
  • The "bad case" is indeed exceptional: The paper highlights a specific input vector designed to produce a large error (the "bad case"). Their experiments confirm that this case is indeed exceptionally bad, and typical inputs result in much smaller errors, reinforcing the idea that global bounds are often overly conservative.
  • Trade-off between accuracy and performance: While interval arithmetic offers better error bounds, it comes at a computational cost. The paper shows that for large FFTs, interval arithmetic can be 2 to 10 times slower than standard floating-point arithmetic, with the overhead often dominated by memory transfers for very large problem sizes.

Key Results

  • The maximum errors observed in floating-point FFT computations were consistently smaller than the "bad case" input, indicating that typical inputs are not exceptionally problematic.
  • Computed local error bounds from interval arithmetic were found to be smaller than the global error bounds.
  • The timing analysis revealed that interval arithmetic is slower than floating-point arithmetic, with the performance penalty increasing with the size of the FFT. For very large FFTs, the timing difference is primarily due to memory transfer delays.

Limitations and Future Work

  • Exhaustive testing is impossible: For double-precision floating-point arithmetic, testing all possible inputs is computationally infeasible. The authors rely on a large sample of random inputs, and while Figure 3 suggests that larger errors are still possible with more samples, it's difficult to definitively capture the absolute worst-case scenario for typical inputs.
  • Platform dependency: The performance of interval arithmetic can vary significantly across different hardware and software implementations. The authors used a specific setup (Julia with IntervalArithmetic.jl) and suggest that further tests with various interval libraries could refine the results.
  • Future work could explore:
    • Refining the comparison of interval arithmetic libraries.
  • Investigating the impact of different FFT algorithms and precision levels.
  • Developing more efficient interval arithmetic implementations for FFTs.

Summary updated

Abstract

The computation of Fast Fourier Transforms (FFTs) in floating-point arithmetic is inexact due to roundings, and for some applications it can prove very useful to know a tight bound on the final error. Although it can be almost attained by specifically built input values, the best known error bound for the Cooley-Tukey FFT seems to be much larger than most actually obtained errors. Also, interval arithmetic can be used to compute a bound on the error committed with a given set of input values, but it is in general considered hampered with large overestimation. We report results of intensive computations to test the two approaches, in order to estimate the numerical performance of state-of-the-art bounds. Surprisingly enough, we observe that while interval arithmetic-based bounds are overestimated, they remain, in our computations, tighter than general known bounds.
BibTeX
@inproceedings{brisebarre2023testing,
  author = {Nicolas Brisebarre and Jean-Michel Muller and Joris Picot},
  title = {{Testing the Sharpness of Known Error Bounds on the Fast Fourier Transform}},
  booktitle = {ARITH},
  year = {2023},
  doi = {10.1109/arith58626.2023.00027},
}
Figure