Covert polynomial roots to coefficients

by

 

Converts a list of a polynomials roots to the polynomials coefficients, using FFT.

Roots2Coeff(R)
function Coeff = Roots2Coeff(R)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Coeff = Roots2Coeff(R)

% This function replace the "poly" function of matlab, which fails to
% reconstruct the coefficient when the number of roots is large (more than
% a 100 for example).  In other words: Roots2Coeff(roots(f))=a*f for some
% arbitrary number a.

% Input:
% R    - a row vector of the (possibly complex) roots of a polynomial.
% Output:
% Ceff - the coefficients of the corresponding polynomial. 

% Oren Raz, 2013.
N=length(R) ; %number of roots.
omega = complex(0,2*pi/(N+1) * (0:N)); 
z     = exp(omega); 
Coeff_omega = ones(1,N+1);
for i=1:N+1
    Coeff_omega(i) = Coeff_omega(i) * prod(z(i) - R)*z(i);
end
Coeff = ifft(Coeff_omega); 

% Explanation: note that if we evaluate the polynomial "P(x) = a0*x^0 + a1*x^1 + ... + an*x^n" 
% at x_k=exp(-1i*2*pi*k/n) for k=0...n, we get the coefficients of the DFT of the
% vector  (a0,...an).

Contact us