JuliaMath / JuliaMath/FFTA.jl

inaccurate results due to inaccurate trigonometric recurrences

Open
#118 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Julia
Stars
74
Forks
8
Avg merge
13h 43m
Merged PRs (30d)
1

Description

With accurate trigonometric constants, a good FFT algorithm should have $O(\log n)$ error bounds and $O(\sqrt{\log n})$ root-mean-square error, similar to [pairwise summation](https://en.wikipedia.org/wiki/Pairwise_summation). See also the [commentary and references](https://www.fftw.org/accuracy/comments.html) posted with the FFTW accuracy benchmarks.

However, the accuracy of FFTA seems to be much worse, nearly $O(n)$ error growth, presumably because (like many naive textbook presentations) it is constructing the trigonometric constants by a recurrence relation. Here is a plot of the single-precision accuracy on random data (using the double-precision result as the "exact" value for comparison) with both FFTW and FFTA:

Image

via the code:
```jl
using LinearAlgebra
relerr(approx, exact) = norm(approx - exact) / norm(exact)

n = 2 .^ (4:20)
err_fft = Float64[]
for n in n
x = randn(ComplexF32, n)
push!(err_fft, relerr(fft(x), fft(ComplexF64.(x))))
end
@show err_fft;
```

Recommendation: the only reasonably efficient way to get accurate trigonometric constants is to precompute them by calling `cis` (or `cispi`) and storing the table in the "plan" data structure.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the Julia reproduction in the issue, comparing single-precision FFTA output against the double-precision result, and trace how trigonometric constants are generated and stored in the plan data structure. Check whether using cis or cispi for precomputed constants changes the error growth; done means substantially improved accuracy consistent with the stated bounds.

Written by the indexing model from the issue text.

Assessment

Tech stack
julia
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.