Using Eigenvalue solver to find Poly roots?

Suppose you have access to a fast and accurate eigenvalue solver (for both real and complex eigenvalues.)  Is there a way to use that to solve for the roots of a polynomial?

In other words, given a polynomial, is there any way to find a matrix that has that polynomial as its characteristic function?

No.

Yes. Given a polynomial p(x) = a0 + a1*x + a2*x^2 + ... + an*x^n + x^(n+1), a matrix with p(x) as its characteristic polynomial can be construct as follows:

In the right most column, -a0, -a1, ... -an from top to bottom. On the spaces immediately below the main diagonal, 1's. Everywhere else, 0's.

>>3
PS: The idea of finding polynomial roots from calculating the eigenvalues of its companion matrix was proposed a while ago, as apparently there is an algorithm for obtaining eignvalues of matrices using quantum computers.