  A new measure called min-max elementwise backward error is introduced for
approximate roots of scalar polynomials $p(z)$. Compared with the elementwise
relative backward error, this new measure allows for larger relative
perturbations on the coefficients of $p(z)$ that do not participate much in the
overall backward error. By how much these coefficients can be perturbed is
determined via an associated max-times polynomial and its tropical roots. An
algorithm is designed for computing the roots of $p(z)$. It uses a companion
linearization $C(z) = A-zB$ of $p(z)$ to which we added an extra zero leading
coefficient, and an appropriate two-sided diagonal scaling that balances $A$
and makes $B$ graded in particular when there is variation in the magnitude of
the coefficients of $p(z)$. An implementation of the QZ algorithm with a strict
deflation criterion for eigenvalues at infinity is then used to obtain
approximations to the roots of $p(z)$. Under the assumption that this
implementation of the QZ algorithm exhibits a graded backward error when $B$ is
graded, we prove that our new algorithm is min-max elementwise backward stable.
Several numerical experiments show the superior performance of the new
algorithm compared with the MATLAB \texttt{roots} function. Extending the
algorithm to polynomial eigenvalue problems leads to a new polynomial
eigensolver that exhibits excellent numerical behaviour compared with other
existing polynomial eigensolvers, as illustrated by many numerical tests.

Numerical Analysis;Numerical Analysis