"Steven G. Johnson" <stevenj@alum.mit.edu> wrote:> 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. >Hi, Thank you very much to anyone for your collaboration. I explain my situation. I attend electronic engineering faculty. My fft knowledge is good. I am beginning to work om my thesis, where I describe in details, and I write the code, of a type of fft algorithm. I have to experimentally evaluate the accurary of the algorithm I use. But I didn't know how do it (until you helped me). Moreover, my prof asked me to describe the state of art of fft. Steven, are you the author of "a modified split radix algorithm with reduced number of operations"? Well, on my thesys, in the state of art, I describe (but not in details) that algorithm too!!! If so, I am honored to post with you. Could I ask you any questions about this paper? For example, 1)How much memory does your algorithm require? I can't find that on your paper. Split-radix and radix-2 require at least N/4 real trigonometric constants (if 1 complex multiplication is implemented with 2 additions and 4 multiplications). You just say your method requires more constants. Could I ask you how many different precomputed constants, your metod require? 2)You say you cannot use your method if 1 complex multiplication, is implemented with 3 additions and 3 multiplications, in classical split radix. Is it valid for the tangent fft (Bluestein) and for Van Buskirk method too? If it is correct, then these three methods (not only yours) require more multiplications than classical split-radix (if 1 complex multiplication is implemented with 3 additions and 3 multiplications). Is it correct? 3)I cannot download the paper: http://dx.doi.org/10.1145/225058.225167 Could you send them to my email: lorpa1@iazza.it Thank you, Adriano
fft
Started by ●February 17, 2008
Reply by ●February 18, 20082008-02-18
Reply by ●February 18, 20082008-02-18
On Feb 18, 3:26 pm, "adriano meis" <doreciakg...@tin.invalid> wrote:> Steven, are you the author of "a modified split radix algorithm with reduced > number of operations"?Yes (co-author).> 1)How much memory does your algorithm require? I can't find that on your > paper. > Split-radix and radix-2 require at least N/4 real trigonometric constants > (if 1 complex multiplication is implemented with 2 additions and 4 multiplications). You > just say your method requires more constants. Could I ask you how many different > precomputed constants, your method require?I haven't counted the exact number; I sure you could write down a recurrence formula to find it, although one has to be careful to avoid counting the same constant twice, but I haven't done so. I do have a few data points from the FFTW code generator, though, that you can use to check anything you work out. For N=64 our new algorithm requires 19 real constants vs. 15 for ordinary conjugate- pair split-radix. For N=128 it requires 41 vs. 31 for ordinary conjugate-pair split-radix. For N=256 it requires 84 vs. 63 real constants for ordinary conjugate-pair split-radix. (This doesn't count trivial constants like 1 and 0, which can be optimized out, of course.)> 2)You say you cannot use your method if 1 complex multiplication, is > implemented with 3 additions and 3 multiplications, in classical split radix.I didn't exactly say this. What I said is that (as far as we could tell) we couldn't fully exploit this trick in one stage of the algorithm (newfftS4), because of the way the multiplication is factorized. If you exploit this trick elsewhere in the algorithm, you end up with an algorithm with the same (reduced) number of flops, but one in which the savings compared to 3/3-multiply split-radix are in the real additions rather than in the real multiplications (and there are slightly more real multiplies).> Is it valid for the tangent fft (Bluestein)What Bernstein (not Bluestein) calls his "tangent fft" seems relatively similar in structure to the algorithm we described: it uses the same subtransform scale factors in a similar context of a conjugate-pair split-radix FFT algorithm operating on complex data, albeit expressed in the language of polynomial-remainder operations. (e.g. what he calls the "twisted" FFT is essentially a DIF Cooley- Tukey FFT, where the "twisted" coefficients correspond to inputs with twiddle factors, in order to make the sub-transforms ordinary DFTs.) (Technically, as we mentioned in our paper, a DIF algorithm is the network transposition of the DIT one we described.) So, I would expect similar analyses would apply for it; although I should make the disclaimer that it is a long paper and I have not read through it in detail, nor (obviously) can I speak for Bernstein, so you'll have to use your own judgement (and/or ask the author).> and for Van Buskirk method too?Unlike us, Van Buskirk expresses his algorithm entirely in terms of real arithmetic (and the two of us consider our algorithms distinct, as he points out in his Computing paper; they certainly lead to distinct linear networks). (For example, in his original size-64 breakthrough, he first broke down the input data in terms of its real and imaginary parts, and those into their even and odd parts. In his Computing paper, he considers only real data and factorizes the purely real "Fourier matrix" corresponding to a real-input DFT.) Because of this, it's not clear to me how the 3/3 complex-multiply trick would apply there since you don't have complex multiplications, although I expect that there may be some analogous transformation (because the 3/3 complex-multiply trick is actually closely related to Karatsuba's algorithm for convolutions). I'm sure James would be happy to respond if you were to contact him.> If it is correct, then > these three methods (not only yours) require more multiplications than > classical split-radix (if > 1 complex multiplication is implemented with 3 additions and 3 > multiplications). > Is it correct?At least ours does, and if I recall JVB's counts are the same as ours for 4/2 complex multiplies, but you could check his Computing paper to be sure. However, I have to admit we didn't try very hard to optimize the 3/3 multiply case. The reason is, if you want to beat just the number of multiplies rather than the number of flops, you can do far better than split radix---you can use Winograd's method to get O(N) multiplies, nor is trading off multiplies for adds especially beneficial on general-purpose CPUs in this context anymore. However, it's true that there is an interesting intellectual question as to whether you can beat *both* the real-multiply *and* the total real-arithmetic count of traditional split-radix at the same time.> 3)I cannot download the paper: > > http://dx.doi.org/10.1145/225058.225167You can find a free preprint of the same paper on Funda Ergun's home page: http://www.cs.sfu.ca/~funda/PUBLICATIONS/stoc95.ps (These days, googling the author's home page is often a good way to get copies of recent papers that you don't have access to through your library.) Regards, Steven G. Johnson
Reply by ●February 18, 20082008-02-18
On Feb 18, 9:26 am, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:> The problem is that the number of floating-point operations no longer > determines the relative speed of two FFT implementations, and hasn't > for many years now, although it may have been true in 1980.You should specify the system targets for that comment more carefully. Processors where a MAC or flop costs much more than a memory access still sell in massive volumes, and there still do exist applications where these types of processors are used for FFT-based signal processing. For contemporary PC's and HPC systems, I definitely agree with your observation. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Reply by ●February 18, 20082008-02-18
On Feb 18, 7:13 pm, "Ron N." <rhnlo...@yahoo.com> wrote:> You should specify the system targets for that comment more > carefully. Processors where a MAC or flop costs much more than > a memory access still sell in massive volumes, and there still > do exist applications where these types of processors are used > for FFT-based signal processing.Right, thanks for the clarification---I was talking about general- purpose CPUs. If you have a small embedded CPU, e.g. you are trying to do a floating-point FFT on a CPU that lacks floating-point hardware, then matters are different. Steven
Reply by ●February 19, 20082008-02-19
On 18 Feb, 19:27, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:> On Feb 18, 12:46 pm, Gordon Sande <g.sa...@worldnet.att.net> 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.I agree with you that it is dangerous to assume anything from students (or anybody else, for that matter). On the other hand, one can almost never *force* other people to do things in a certain way -- one of very few exceptions is how drill sargeants in army boot camp can force recruits around. In most universities students are not forced around. Teaching staff does (usually) not drill students in 'approved' techniques or terminology, students are expected to think for themselves. The best teachers and tutors can do is to try and level with each particular student (or more practically, a class), and try and make them think through the material under discussion on ther own terms. Accuracy and state of the art are usually not relevant issues in such learning processes; getting a grip on basic principles and 'standard' approaches is. And that includes the method of work. Unless you have direct power over a student (the only way that will happen in practice is that you have to approve and sign off some compulsary exercise [*]) the best you can do is to *suggest* how to proceed and leave it to the student to decide what to actually do. Rune [*] Many years ago I tutored an MSc student who followed up on some of the stuff I worked with for my PhD thesis. The guy did a good job, but he didn't understand how to present his work in writing. I explained to him how to present the material and he did something else. He lost at least a half, maybe a full, grade by doing things 'his way' (in those days the grading system went as 1.0 (best) - 1.25 - 1.5 - ... 6.0 (worst)). I saw the problem coming weeks in advance, but there was nothing I could do to *force* him do things properly.
Reply by ●February 19, 20082008-02-19
On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote:> I agree with you that it is dangerous to assume anything from > students (or anybody else, for that matter). On the other hand, > one can almost never *force* other people to do things in a > certain wayI'm confused. Who is talking about "forcing" someone to do anything? We were just discussing how to answer a certain online question in a clear and useful way. How would it even be possible to "force" someone to do something in an online forum?
Reply by ●February 19, 20082008-02-19
On 19 Feb, 14:54, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:> On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote: > > > I agree with you that it is dangerous to assume anything from > > students (or anybody else, for that matter). On the other hand, > > one can almost never *force* other people to do things in a > > certain way > > I'm confused. �Who is talking about "forcing" someone to do anything? > We were just discussing how to answer a certain online question in a > clear and useful way. �How would it even be possible to "force" > someone to do something in an online forum?Gordon's first post seems to have been based on pedagogical principles similar to those outlined by me. You responded with a very technical reply based on what might be expected from students. The only contexts where such a highly technical reply might be relevant are 1) Where the student is *known* (or at least would be expected) to have relevant competence to handle the reply offered. 2) Where the instructor has the 'power tools' needed to force the student in a particular direction. At the time Gordon wrote his first reply, the technical proficiency of the OP was not known, although subsequent posts by the OP seem to indicate a certain level of both knowledge and skills. But again, at the start of this thread, this was not known. The point I am trying to make is that one starts out in 'gentle' ways on a general basis, and only follows up with the highly technical stuff after one is sees that the oposite party is able to handle it. Starting to feed technical details too soon is not useful unless one can force things to be done in a certain way (and more often than not, it's not very useful for teaching even then). Rune
Reply by ●February 19, 20082008-02-19
On Feb 19, 9:13 am, Rune Allnor <all...@tele.ntnu.no> wrote:> On 19 Feb, 14:54, "Steven G. Johnson" <stev...@alum.mit.edu> wrote: > > > On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > I agree with you that it is dangerous to assume anything from > > > students (or anybody else, for that matter). On the other hand, > > > one can almost never *force* other people to do things in a > > > certain way > > > I'm confused. Who is talking about "forcing" someone to do anything? > > We were just discussing how to answer a certain online question in a > > clear and useful way. How would it even be possible to "force" > > someone to do something in an online forum? > > Gordon's first post seems to have been based on pedagogical > principles similar to those outlined by me. You responded > with a very technical reply based on what might be expected > from students. The only contexts where such a highly technical > reply might be relevant areI responded that Gordon's answer was misleading, because the student asked how to measure X and Gordon gave a suggestion that would actually measure Y, not X. This has nothing to do with "gentle" vs. "forcing" pedagogical approaches or "technical" versus "non-technical". It has to do with not giving trick answers. I gave additional information and references in response to a question, and I clarified a point that was arguably misleading; I'm really baffled regarding how this led to a long lecture about not "forcing" students. Regards, Steven G. Johnson
Reply by ●February 19, 20082008-02-19
Steven G. Johnson wrote:> On Feb 19, 9:13 am, Rune Allnor <all...@tele.ntnu.no> wrote: >> On 19 Feb, 14:54, "Steven G. Johnson" <stev...@alum.mit.edu> wrote: >> >>> On Feb 19, 6:11 am, Rune Allnor <all...@tele.ntnu.no> wrote: >>>> I agree with you that it is dangerous to assume anything from >>>> students (or anybody else, for that matter). On the other hand, >>>> one can almost never *force* other people to do things in a >>>> certain way >>> I'm confused. Who is talking about "forcing" someone to do anything? >>> We were just discussing how to answer a certain online question in a >>> clear and useful way. How would it even be possible to "force" >>> someone to do something in an online forum? >> Gordon's first post seems to have been based on pedagogical >> principles similar to those outlined by me. You responded >> with a very technical reply based on what might be expected >> from students. The only contexts where such a highly technical >> reply might be relevant are > > I responded that Gordon's answer was misleading, because the student > asked how to measure X and Gordon gave a suggestion that would > actually measure Y, not X. > > This has nothing to do with "gentle" vs. "forcing" pedagogical > approaches or "technical" versus "non-technical". It has to do with > not giving trick answers. > > I gave additional information and references in response to a > question, and I clarified a point that was arguably misleading; I'm > really baffled regarding how this led to a long lecture about not > "forcing" students.Steven, These days, Rune spends his time aboard ship, much of it (I'm guessing) with little to stimulate his mind. Why not put it down to sensory deprivation of the intellectual kind and move on? Nobody commented on my suggestion, which was to transform a function for which the result was precisely known, and to compare the computed result to the known one. Is it practical? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●February 19, 20082008-02-19
On Feb 19, 10:52 am, Jerry Avins <j...@ieee.org> wrote:> Nobody commented on my suggestion, which was to transform a function for > which the result was precisely known, and to compare the computed result > to the known one. Is it practical?Certainly that is practical to do as a simple check; Gordon made a similar suggestion. (Of course, the error that many students make in applying that suggestion is that they compare to the analytical Fourier integral that is tabulated in their textbooks, not to the analytical DFT; I can't count how many times someone has posted on Usenet that their FFT routine is not working because the transform of a Gaussian is not a Gaussian, etc.) (Most published accuracy tests seem to prefer random inputs, to give error statistics over a desired distribution, however, as opposed to a handful of special inputs whose DFTs are known. But of course, it all depends on what question you are interested in: accuracy for what inputs?) One interesting problem that occurs to me is to ask what is the "worst" input, i.e. the input that gives the worst errors in some norm. Of course, the precise answer probably depends on the FFT algorithm/implementation, the compiler, and the floating-point hardware, but I wonder if there are certain inputs that are consistently "bad"? (Of course, since there is an O(log N) error bound as proved by Gordon in 1966, it can't get *that* bad.) Also, I wonder if there is a straightforward way, given an FFT routine, of finding such a worst-case input, e.g. by throwing it at an optimization (err, pessimization) algorithm, or if the problem has too many local minima for this to be practical. Probably for the DC element, at least, where the output is just a (cascade) summation, the identification of the worst case inputs has been studied to some extent. Anyway, just pondering aloud. Steven
