Calculate roots of multiple polynomials

Question

Given a matrix A that represents polynomials in each column. How can the roots of each polynomial be calculated efficiently without loops?

Answer 1

Here's a comparison between 3 methods:

1. A simple loop through all the rows, using roots on each row.
2. A completely loopless approach, based on YBE's idea of using a block-diagonal matrix, using sparse as an intermediate
3. A simple loop through all the rows, but this time using "inlined" code from roots.

The code:

%// The polynomials
m = 15;
n = 8;
N = 1e3;

X = rand(m,n);


%// Simplest approach
tic
for mm = 1:N

    R = zeros(n-1,m);
    for ii = 1:m
        R(:,ii) = roots(X(ii,:));
    end

end
toc


%// Completely loopless approach
tic
for mm = 1:N

    %// Indices for the scaled coefficients
    ii = repmat(1:n-1:m*(n-1), n-1,1);
    jj = 1:m*(n-1);

    %// Indices for the ones
    kk = bsxfun(@plus, repmat(2:n-1, m,1), (n-1)*(0:m-1).');  %'
    ll = kk-1;

    %// The block diagonal matrix
    coefs = -bsxfun(@rdivide, X(:,2:end), X(:,1)).';  %'
    one   = ones(n-2,m);
    C = full(sparse([ii(:); kk(:)], [jj(:); ll(:)],...
        [coefs(:); one(:)]));

    %// The roots
    R = reshape(eig(C), n-1,m);

end
toc


%// Simple loop, roots() "inlined"
tic    
R = zeros(n-1,m);
for mm = 1:N

    for ii = 1:m            
        A = zeros(n-1);
        A(1,:) = -X(ii,2:end)/X(ii,1);
        A(2:n:end) = 1;
        R(:,ii) = eig(A);            
    end

end
toc

The results:

%// m=15, n=8, N=1e3:
Elapsed time is 0.780930 seconds. %// loop using roots()
Elapsed time is 1.959419 seconds. %// Loopless
Elapsed time is 0.326140 seconds. %// loop over inlined roots()

%// m=150, n=18, N=1e2:
Elapsed time is 1.785438 seconds. %// loop using roots()
Elapsed time is 110.1645 seconds. %// Loopless
Elapsed time is 1.326355 seconds. %// loop over inlined roots()

Of course, your mileage may vary, but the general message should be clear: The old advice of avoiding loops in MATLAB is just that: OLD. It just no longer applies to MATLAB versions R2009 and up.

Vectorization can still be a good thing though, but certainly not always. As in this case: profiling will tell you that most time is spent on computing the eigenvalues for the block-diagonal matrix. The algorithm underlying eig scales as N³ (yes, that is a three), plus it cannot take advantage of sparse matrices in any way (like this block-diagonal one), making the approach a poor choice in this particular context.

Loops are your friend here ^_^

Now, this is of course based on eig() of the companion matrix, which is a nice and simple method to compute all roots in one go. There are of course many more methods to compute roots of polynomials, each with their own advantages/disadvantages. Some are a lot faster, but aren't so good when a few of the roots are complex. Others are a lot faster, but need a fairly good initial estimate for every root, etc. Most other rootfinding methods are usually a lot more complicated, which is why I left these out here.

Here is a nice overview, and here is a more in-depth overview, along with some MATLAB code examples.

If you're smart, you should only dive into this material if you need to do this computation millions of times on a daily basis for at least the next few weeks, otherwise, it's just not worth the investment.

If you're smarter, you'll recognize that this will undoubtedly come back to you at some point, so it's worthwhile to do anyway.

And if you're an academic, you master all the root-finding methods so you'll have a giant toolbox, so you can pick the best tool for the job whenever a new job comes along. Or even dream up your own method :)