How to calculate roots for multiple polynomial equations simultaneously i.e. without iterating over them one by one

Actually I have a bunch of quadratic equations(around 1 million equations!!) which I need to solve. I made a matrix of 1 million rows with each row is a vector containing coeff(s) for x^2, x^1 & x^0. i named this matrix M and wrote following code:

answers = zeros(1000000,2);
for i=1:1:length(answers)
answers(i,:) = roots(M(i,:));
end

I was wondering if there's a way we can calculate roots simultaneously for every polynomial equation without iterating over them one by one.

Answer 1

[John D'Errico]

In fact, the simple answer is YES. It is trivial. No loop required.

You have a set of QUADRATIC EQUATIONS!!!!!! Surely you learned the quadratic formula for the roots of a quadratic equation?

tic
N = 1e6;
coef = rand(N,3);
D = sqrt(coef(:,2).^2 - 4*coef(:,1).*coef(:,3));

R = [(-coef(:,2) + D)./(2*coef(:,1)), (-coef(:,2) - D)./(2*coef(:,1))];
toc

Elapsed time is 0.115124 seconds.

size(R)
ans =
     1000000           2

One million sets of roots, computed in around 1/10 of a second. Since my coefficients are randomly generated, many of those roots will be complex. As a test to verify it worked...

coef(1,:)
ans =
         0.562209637790579        0.0918349300613903         0.952524012642822
         
R(1,:)
ans =
        -0.0816732086115523 +      1.29906892840699i        -0.0816732086115523 -      1.29906892840699i
        
roots(coef(1,:))
ans =
        -0.0816732086115523 +      1.29906892840699i
        -0.0816732086115523 -      1.29906892840699i               

Hopefully your quadratics will be better behaved, and have real roots.

[Earth Sugandhi]

Thanks man!! this formula had just sliped off my mind

[John D'Errico]

Some years ago, we realized we needed to do the same thing for zillions of cubic polynomials. So we wrote up the cubic formula, fully vectorized. Worked nicely.