Re: Roots() and factorizing large polynomials

[Børge Strand-Bergesen]

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)]);
        end;
end

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?

Thanks,
Borge

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
> http://orion.neiu.edu/~zzeng/multroot.zip
> 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: 
> http://old.nabble.com/Roots%28%29-and-factorizing-large-polynomials-tp27502322p27513916.html
> Sent from the Octave - General mailing list archive at Nabble.com.
>
> _______________________________________________
> Help-octave mailing list
> address@hidden
> https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
>