[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Roots() and factorizing large polynomials

From: Børge Strand-Bergesen
Subject: Re: Roots() and factorizing large polynomials
Date: Fri, 12 Feb 2010 15:11:27 +0100

Thanks Pascal,

multroot() does not produce some of the stranger numbers that roots()
does. So that is a very good start. Do you know of a way to
re-assemble the function? I.e. multiply the roots back together after
they have been individually manipulated.

roots_x = multroot(x); % x is impulse response of digital FIR filter
manipulate(roots_x); % Invert roots with ||>1 to obtain minimum-phase roots

% Reassemble new impulse response from roots:
asm_x = [1];
for n=1:length(roots_x)
        for m=1:roots_x(n,2)
            asm_x = conv(asm_x, [1 -roots_x(n,1)]);

This reassembly method is very crude, since it requires as many
convolutions as there are roots. The output grows to a very large
number, and it is not real. So numerical precision must play a large
role here. I can reduce the number by using iterative, branched
convolutions. Or would you suggest an alternative method?


On Tue, Feb 9, 2010 at 12:34, Dupuis <address@hidden> wrote:
> Borge wrote:
>> Hi,
>> Im using roots() to factorize a long filter impulse responce
>> (polynomial in z). Reassembling the filter from the roots works for
>> short impulse responses (see below) but fails for longer ones. Any
>> suggestions for better factorization of polynomials?
>> The reason I'm doing this is that I want to take a generic FIR filter
>> and convert it to a minimum-phase filter. (By finding the roots,
>> inverting those with abs()>1, and assembling them to an impulse
>> response again.)
> Standard roots() algorithm works on a matrix constructed from the polynomial
> coefficient. In case some of the roots has a multiplicity greater than one,
> the matrix becomes singular. In the case where the distance between two
> distinct roots become very small, the matrix becomes quasi-singular, and
> roots accuracy is deteriorated.
> I use an algorithm written by Prof.  Zhonggang Zeng, where the common
> divisor between the polynomial and its first derivative is computed. At this
> stage, the number of roots and their multiplicity is computed. Afterwards,
> the root finding algorithm is applied on a reduced polynomial containing
> only isolated roots with multiplicity one. Accuracy improvement can reach
> several orders of magnitude. This material is available at
> The license is very restrictive :
> % This code is freely released for research exchange only. The author
> % is not responsible for any demage caused by using this code.
> See if you can cope with it.
> Regards
> Pascal
> --
> View this message in context: 
> Sent from the Octave - General mailing list archive at
> _______________________________________________
> Help-octave mailing list
> address@hidden

reply via email to

[Prev in Thread] Current Thread [Next in Thread]