High-Performance Polynomial Root Finding for Graphics
| dc.contributor.author | Yuksel, Cem | en_US |
| dc.contributor.editor | Josef Spjut | en_US |
| dc.contributor.editor | Marc Stamminger | en_US |
| dc.contributor.editor | Victor Zordan | en_US |
| dc.date.accessioned | 2023-01-23T10:23:44Z | |
| dc.date.available | 2023-01-23T10:23:44Z | |
| dc.date.issued | 2022 | |
| dc.description.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. | en_US |
| dc.description.number | 3 | |
| dc.description.sectionheaders | Geometry and Textures | |
| dc.description.seriesinformation | Proceedings of the ACM on Computer Graphics and Interactive Techniques | |
| dc.description.volume | 5 | |
| dc.identifier.doi | 10.1145/3543865 | |
| dc.identifier.issn | 2577-6193 | |
| dc.identifier.uri | https://doi.org/10.1145/3543865 | |
| dc.identifier.uri | https://diglib.eg.org:443/handle/10.1145/3543865 | |
| dc.publisher | ACM Association for Computing Machinery | en_US |
| dc.subject | CCS Concepts: Mathematics of computing -> Nonlinear equations; Computing methodologies -> Ray tracing; Collision detection Additional Key Words and Phrases: Polynomial solver, cubic solver, quartic solver, Newton iterations | |
| dc.subject | Mathematics of computing | |
| dc.subject | Nonlinear equations | |
| dc.subject | Computing methodologies | |
| dc.subject | Ray tracing | |
| dc.subject | Collision detection Additional Key Words and Phrases | |
| dc.subject | Polynomial solver | |
| dc.subject | cubic solver | |
| dc.subject | quartic solver | |
| dc.subject | Newton iterations | |
| dc.title | High-Performance Polynomial Root Finding for Graphics | en_US |