Go back to the benchFFT accuracy results page.

This page outlines our accuracy benchmarking methodology. For complete details, you can look at the source code, available from benchFFT home page; see also our speed benchmark methodology page.

To compute the accuracy of an FFT, we compare the transform of
uniform pseudorandom numbers in [-0.5,0.5) with the output of an
arbitrary-precision arithmetic FFT (with > 40 decimal places of
accuracy). This is the *forward error*, defined as
**compare(FFT(x), exactFFT(x))**. We also compute the *backward
error*, by finding the *input* to the arbitrary-precision FFT
that gives the same output; i.e. **compare(exactInverseFFT(FFT(x)),
x)**.

To compare two arrays, we use

where ||x||compare(a, b)= ||a – b||_{n}/ ||b||_{n}

||x||_{n}= (sum |x_{i}|^{n})^{1/n}

We compute the error for the L_{1}, L_{2}, and
L_{∞} [= max(|x_{i}|)] norms.

For random input, the L_{2} forward error of a
well-implemented FFT routine grows as O(√log N), where N is the
size of the transform (see also our commentary). Because the Fourier transform
is a unitary linear transformation, the backward L_{2}
error is equal to the forward L_{2} error (at least for the
complex transform). No such equality exists for the other norms. We
computed the backward errors as an additional consistency check, but
we do not mean to attach any particular significance to them.

On a given platform, the same random inputs are used for all transforms of the same size and type. Our benchmark program can currently measure the accuracy of 1D transforms only (both complex and real).

In our graphs of FFT accuracy, we plot the L_{2} forward
error for each FFT, on a log scale, as a function of size.

In order to keep the graphs readable, however, **we only plot the
"worst" results**. That is, when a particular code has several
variants (different radices, calling options, etcetera), we only plot
the variant that is "on average" the *least accurate* (with a few
exceptions, for codes of particular interest or for variants with
radically different characteristics). We also only plot either the
forward or the backward transform accuracy, whichever is worse "on
average".

To quantify the "average" accuracy of a routine, and also to
reorder the plot legend for improved readability, we define a **plot
rank** for each FFT as follows. First, for each transform size in a
plot, we compute a *rank* = log(error for FFT) / log(error for
best FFT for that size). Then, the *plot rank* of a given FFT is
defined as the median of its ranks for all sizes in the plot. The
plot rank is only a convenient heuristic to produce useful plots, and
it should not be interpreted as an absolute measure of accuracy.

In the raw benchmark data output, the accuracy for all routines, for both forward and backward transforms, is collected in the file

in the space-delimited format:
*host*.accuracy

name-of-code transform-type transform-size forward-L_{1}forward-L_{2}forward-L_{∞}backward-L_{1}backward-L_{2}backward-L_{∞}

where *transform-type* is a
four-character string as described in our speed benchmark methodology
page.

Go back to the benchFFT accuracy results page.