Algorithm to determine if a polynomial has any complex roots

Question

Is there a simple algorithm to determine if a given polynomial (with all real coefficients) has all real roots? I do not need to know what the roots are; I just what to know if a given polynomial has any complex roots.

Background: I am aware that there are algorithms (for example see here) to compute all of the real roots of an arbitrary degree polynomial \begin{equation} \label{polynomial} a_0 + a_1x + a_2x^2 + \cdots + a_n x^n , \end{equation} where $a_0,...,a_n$ are all real constants.

Answer 1

You can use the companion matrix to find the roots via eigenvalue calculation:

Companion matrix

Note that you have to consider Sturm's theorem in order to find the number of complex/real roots without explicitly calculating them (that's the only way):

Sturm's theorem