High-Performance Polynomial Solver

Abstract

We present a computationally-efficient and numerically-robust algorithm for finding real roots of polynomials. It begins with determining the intervals where the given polynomial is monotonic. Then, it performs a robust variant of Newton iterations to find the real root within each interval, providing fast and guaranteed convergence and satisfying the given error bound, as permitted by the numerical precision used.

For cubic polynomials, the algorithm is more accurate and faster than both the analytical solution and directly applying Newton iterations. It trivially extends to polynomials with arbitrary degrees, but it is limited to finding the real roots only and has quadratic worst-case complexity in terms of the polynomial's degree.

We show that our method outperforms alternative polynomial solutions we tested up to degree 20. We also present an example rendering application with a known efficient numerical solution and show that our method provides faster, more accurate, and more robust solutions by solving polynomials of degree 10.

Performance

Computation Time of Cubic (Degree 3) Polynomials

Computation time of different cubic polynomial solvers. Our solution outperforms the analytical solution for cubics and achieves better accuracy. It is also faster than Blinn's analytical solution. Unlike regular Newton iterations, ours can quickly determine the cases with no root and skip computation. Also, regular Newton iterations can only find one of the roots and often fails to find an existing root, while ours can find them all.

Computation Time of Higher-Order Polynomials

Computation time of polynomial solvers for polynomials of different degrees. The computation time of our method depends on the given error threshold. This graph shows the computation time of our method with a low-accuracy, high-accuracy, and full-accuracy (up to the full 64-bit double-precision accuracy), in comparison to RPOLY, a popular numerical root finding method that is optimized for polynomials with real coefficients. Our solution can achieve better accuracy and provide an order of magnitude faster computation for polynomials of relatively low degrees (<10).