Re: fft
- From: "Steven G. Johnson" <stevenj@xxxxxxxxxxxx>
- Date: Mon, 18 Feb 2008 10:27:41 -0800 (PST)
On Feb 18, 12:46 pm, Gordon Sande <g.sa...@xxxxxxxxxxxxxxxx> wrote:
The OP wanted to evaluate the numerical accurracy of an FFT. One thing
that would be instructive is to see that it is more accurate than the
naive definition. A nice easy way is to do it forward and back as he
proposed for the FFT. I assumed that if he had the sense to ask for
comments he was likely to try his proposed forward and back method
on the other ways.
In my experience, it's unreliable to assume that students will check
their answers in multiple redundant ways. They find one way that
seems to work, and stop there. So if you tell students to compare to
the O(N^2) algorithm, without warning them that the latter is less
accurate, it's quite likely they will just compare the two algorithms
for random inputs and stop there.
Since the OP stated that he is a student. One might have thought that
suggesting a student to do other things to illustrate the background
might have helped the student's general education.
The problem is, if a student asks how to measure the "numerical
accuracy of an fft" and you tell him to compare to the O(N^2)
algorithm, it is a bit deceptive, because that comparison is measuring
the accuracy of the O(N^2) algorithm rather than the fft.
Of course, given enough time, hints, and prodding, the student may
figure out for himself that your answer didn't mean what it seemed,
but posting trick answers on internet forum is a bit dubious from a
pedagogical perspective, in my opinion.
It is not really necessary for the student's first step towards
understanding to be at the frontiers of the state of the art.
I agree, but an forum like this has wide readership; it's nice to give
a pointer or two to more advanced/rigorous approaches in addition to
the simplest answers (and often students appreciate seeing a broader
context as well). Also, this student *explicitly* asked for "papers"
describing methods to check accuracy, which indicates an attempt to go
beyond the level of the traditional homework problem.
Probaby the simplest and most general thing one can do, for numerical
accuracy, is to perform an FFT in single precision and compare it to
the result in double precision (or compare double precision to an
arbitrary-precision arithmetic FFT, which is how we perform our
accuracy benchmarks in FFTW, fftw.org/accuracy/).
Fine if you have all that infrastructure. What should a under-resourced
student, and probably without a lot of supervision, away from a major
research university do?
s/double/float/ is pretty easy even for a student.
(Also, our accuracy benchmark code is available to download.)
Regards,
Steven G. Johnson
.
- References:
- Prev by Date: key difference between CTC and CC schemes
- Next by Date: Re: key difference between CTC and CC schemes
- Previous by thread: Re: fft
- Next by thread: Re: fft
- Index(es):
Relevant Pages
|
