FPGA Central

Hi all,
I have a rough idea in mind for finding the roots of a polynomial. The
approach is as follows:

1. Any Nth order polynomial can be written as: aN x^N + ... + a0,
where ai belong to set of real numbers

2. Let us introduce R (radius) terms, R^N aN x^N + R^{N-1} a{N-1}
x^{N-1}... + a0

3. Vary R in course steps bw [-A to A] and consider ai to be
coefficients of an FIR filter, pass a 0 mean, 1 variance Gaussian
noise through it.

4. Look at the Spectrum of the filtered noise, find the frequencies
where spectrum has notches.

roots are at R exp{(+/-) j*2*pi*fn/Fs}, where fn is the frequency
where the notch is.

Of course i already see several problems, how to define [-A A], steps
of R, computationally very complex etc. But i thought its interesting
to share, please feel free to criticize, suggest improvements.

~Mobien

On Jul 17, 1:10*pm, mobi <mob...@gmail.com> wrote:
> Hi all,
> I have a rough idea in mind for finding the roots of a polynomial. The
> approach is as follows:
>
> 1. Any Nth order polynomial can be written as: *aN x^N + ... + a0,
> where ai belong to set of real numbers
>
> 2. Let us introduce R (radius) terms, R^N aN x^N + R^{N-1} a{N-1}
> x^{N-1}... + a0
>
> 3. Vary R in course steps bw [-A to A] and consider ai to be
> coefficients of an FIR filter, pass a 0 mean, 1 variance Gaussian
> noise through it.
>
> 4. Look at the Spectrum of the filtered noise, find the frequencies
> where spectrum has notches.
>
> roots are at R exp{(+/-) j*2*pi*fn/Fs}, where fn is the frequency
> where the notch is.
>
> Of course i already see several problems, how to define [-A A], steps
> of R, computationally very complex etc. But i thought its interesting
> to share, please feel free to criticize, suggest improvements.
>
> ~Mobien

Prohibitively expensive computationally.

But... skip the noise, don't filter anything. Treat vector [R^N aN
R^{N-1} a{N-1} ... a0] as the impulse response of the filter and FFT
the zeropadded vector.

Don't use [-A 0) for R. For R>=0, what does -R give you that R
doesn't?


Dirk

> Don't use [-A 0) for R. For R>=0, what does -R give you that R
> doesn't?

You are right, it must be R>=0,where R < 1 are for zeros or roots
outside the unit circle of z-transform, and R >= 1 is for the zeros
inside or on the unit circle.

I know that there are much better methods, like the eigen values
algorithm, was just brain farting :P

~Mobien




On Jul 18, 12:28 am, dbell <bellda2...@cox.net> wrote:
> On Jul 17, 1:10 pm, mobi <mob...@gmail.com> wrote:
>
>
>
> > Hi all,
> > I have a rough idea in mind for finding the roots of a polynomial. The
> > approach is as follows:
>
> > 1. Any Nth order polynomial can be written as: aN x^N + ... + a0,
> > where ai belong to set of real numbers
>
> > 2. Let us introduce R (radius) terms, R^N aN x^N + R^{N-1} a{N-1}
> > x^{N-1}... + a0
>
> > 3. Vary R in course steps bw [-A to A] and consider ai to be
> > coefficients of an FIR filter, pass a 0 mean, 1 variance Gaussian
> > noise through it.
>
> > 4. Look at the Spectrum of the filtered noise, find the frequencies
> > where spectrum has notches.
>
> > roots are at R exp{(+/-) j*2*pi*fn/Fs}, where fn is the frequency
> > where the notch is.
>
> > Of course i already see several problems, how to define [-A A], steps
> > of R, computationally very complex etc. But i thought its interesting
> > to share, please feel free to criticize, suggest improvements.
>
> > ~Mobien
>
> Prohibitively expensive computationally.
>
> But... skip the noise, don't filter anything. Treat vector [R^N aN
> R^{N-1} a{N-1} ... a0] as the impulse response of the filter and FFT
> the zeropadded vector.
>
> Don't use [-A 0) for R. For R>=0, what does -R give you that R
> doesn't?
>
> Dirk