From: "Brian Schröder" <ruby@...>
Date: 2004-11-10T18:38:18+09:00
Subject: Re: [ann] symbol solver.. early experiments

On Wed, 10 Nov 2004 09:14:07 +0900
Mauricio Fern�ndez <batsman.geo@yahoo.com> wrote:

> 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/
> 


Thanks for answering this. Now that you explain it, it becomes clear. They should have motivated it in class like that, because I'm shure 90% of my colleges have no idea for how many usefull things you need the FFT.

regards,

Brian

-- 
Brian Schr�der
http://www.brian-schroeder.de/