From: "Mauricio Fernández" <batsman.geo@...>
Date: 2004-11-10T09:14:07+09:00
Subject: Re: [ann] symbol solver.. early experiments

On Wed, Nov 10, 2004 at 07:26:44AM +0900, Brian Schr�der wrote:
> Hey, I'm just now preparing for my CS exam and refreshing my
>algorithm-threorie stuff. There we learned, that polynom product should
>be done using fft to get (point, value) representations, multiply these,
>and use fft again to interpolate and get the original results back.
         (inverse)?
> 
> Don't know if this is of any practical relevance, and I always wondered
>why we took this example for usage of the fft. Does anybody know of any
>real world usage of polynom multiplication that has to be that fast? 

If you look at it closely, you'll see that polynomial multiplication is
but a convolution... hence the standard FFT procedure. To the extent
that the polynomial multiplication is a convolution, most of the signal
processing done in the real world is a good example of the above :)

>And is it numerically stable, or would you prefer the method above?

There are many ways to do the FFT *g*
I found the following in a quick google search:
http://www.math.uni-luebeck.de/workers/potts/paper/stabfinal.pdf

Note that the 'obvious' algo will be faster unless the degree of your
polynomials is high enough...

-- 
Hassle-free packages for Ruby?
RPA is available from http://www.rubyarchive.org/