What's the best way to compute the coefficients of a polynomial from its roots?

Question

The poly function takes the roots of a polynomial as the input and returns the polynomial's coefficients. What is the underlying algorithm?

Is there a better way to compute the coefficients of a polynomial from its roots?

Answer 1

Note that:

• To obtain the polynomial p(x) (with leading coefficient 1) you need to multiply all terms of the form x−r, where r is a root. (Multiple roots should be considered several times according to their multiplicities.)

• Multiplication of polynomials is equivalent to convolution. In fact, the documentation of conv says

  w = conv(u,v) returns the convolution of vectors u and v. If u and v are vectors of polynomial coefficients, convolving them is equivalent to multiplying the two polynomials.

So:

roots = [1 -2 3]; %// input (roots)
result = 1;  %// initiallize
for r = roots
    result = conv(result, [1 -r]);
end

In this example the result is

result =
     1    -2    -5     6

which is the same vector that poly returns.

Alternatively, you can do the convolution manually:

roots = [1 -2 3]; %// input (roots)
result = 1;  %// initiallize
for r = roots
    result = [result 0] + [0 -r*result];
end

This is equivalent to the following code with explicit loops, which should be closer to a C++ implementation:

roots = [1 -2 3]; %// input (roots)
result = nan(1,numel(roots)+1);  %// preallocate. Values will be overwritten
result(1) = 1; %// initiallize
for n = 1:numel(roots)
    result(n+1) = -roots(n)*result(n); %// update from right to left, due to overwriting
    for k = n:-1:2
        result(k) = result(k) - roots(n)*result(k-1);
    end
end

Answer 2

Since you solicited for a c++ answer. A typical implementation would look like.

std::vector<int> poly( std::vector<int> roots )
{
    std::vector<int> result{1};
    for( size_t i = 0 ; i < roots.size() ; ++i)
    {
        std::vector<int> temp{result.begin(),result.end()};

        for(auto & item : temp )
            item *= ( -roots[i] );

        result.push_back(0);
        for( size_t j = 1 ; j < result.size() ; ++j)
        {
            result[j] += temp[j-1];
        }
    }
    return result;
}

Hope that helps