🚀 go-pugleaf

In article <POPAT.92Aug6115014@image.mit.edu> popat@image.mit.edu (Kris Popat) writes:
>
>In article <ALIEN.92Aug6090438@vulcan.essex.ac.uk>, alien@essex.ac.uk
>("Adrian F Clark") writes
>
>> that it can be decomposed into a series of 1-D FFTs.  In other words,
>> you FFT along all the rows, then FFT down all the columns.  (This is
>> not, however a very efficient way to do it!) [...]
>
>Actually, row-column decomposition IS a fairly efficient way to
>compute a 2-D DFT.  Slightly faster methods exist (e.g., vector-radix
>FFTs), but the speed-up over row-column decomposition is usually
>small, and may not be worth the extra difficulty in programming
>(considerable).  Row-column decomposition gets you down to the right
>order of complexity.
>
>The following is a good introductory reference:
>
> AUTHOR:  Lim, Jae S.
> TITLE:   Two-dimensional signal and image processing /
> EDITION: c1990.
> IMPRINT: Englewood Cliffs, N.J. : Prentice Hall,
>

This is a good reference; however, much of its analysis about algorithms
has not been updated for current computer architecture.  In particular, the
analysis of convolution by using two FFTs together reduces only complex
multiplications.  Computers today are more sensitive to memory accesses.
This is of CRITICAL importance when using a workstation without local
swap space.  

What you have to ask yourself is what takes longer on your machine?
a complex multiplication or cache misses.  Page faults are killers but don't
happen as often.

The point is that just because someone says that their algorithm is better
does not mean that it will be better on your machine.

John Liptak
jliptak@lookout.uswest.com