{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T19:39:04Z","timestamp":1768073944450,"version":"3.49.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T00:00:00Z","timestamp":1658707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Comput. Graph. Interact. Tech."],"published-print":{"date-parts":[[2022,7,25]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3543865","type":"journal-article","created":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T23:35:58Z","timestamp":1658964958000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["High-Performance Polynomial Root Finding for Graphics"],"prefix":"10.1145","volume":"5","author":[{"given":"Cem","family":"Yuksel","sequence":"first","affiliation":[{"name":"University of Utah, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14208"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2006.60"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2006.81"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2005.134"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2006.129"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2007.10"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2007.60"},{"key":"e_1_2_2_8_1","unstructured":"Gerolamo Cardano. 1570. Artis Magnae Sive de Regulis Algebraicis Liber Unus.  Gerolamo Cardano. 1570. Artis Magnae Sive de Regulis Algebraicis Liber Unus."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13265"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/3619497"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation","author":"George","unstructured":"George E. Collins and R\u00fcdiger Loos. 1976. Polynomial Real Root Isolation by Differentiation . In Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation ( Yorktown Heights, New York, USA) (SYMSAC '76). Association for Computing Machinery, New York, NY, USA, 15--25. https:\/\/doi.org\/10.1145\/800205.806319 George E. Collins and R\u00fcdiger Loos. 1976. Polynomial Real Root Isolation by Differentiation. In Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation (Yorktown Heights, New York, USA) (SYMSAC '76). Association for Computing Machinery, New York, NY, USA, 15--25. https:\/\/doi.org\/10.1145\/800205.806319"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13622"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699468"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0707045"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.rinam.2019.100078"},{"key":"e_1_2_2_16_1","volume-title":"Numerical Methods for Roots of Polynomials - Part I","author":"McNamee John M.","unstructured":"John M. McNamee . 2007. Numerical Methods for Roots of Polynomials - Part I . Elsevier . John M. McNamee. 2007. Numerical Methods for Roots of Polynomials - Part I. Elsevier."},{"key":"e_1_2_2_17_1","volume-title":"McNamee and Victor Pan","author":"John","year":"2013","unstructured":"John M. McNamee and Victor Pan . 2013 . Numerical Methods for Roots of Polynomials - Part II. Elsevier. John M. McNamee and Victor Pan. 2013. Numerical Methods for Roots of Polynomials - Part II. Elsevier."},{"key":"e_1_2_2_18_1","volume-title":"Combinatorial and Computational Geometry","author":"Mourrain Bernard","unstructured":"Bernard Mourrain , Fabrice Rouillier , and Marie-Fran\u00e7oise Roy . 2005. Bernstein's basis and real root isolation . In Combinatorial and Computational Geometry . MSRI Publications, Vol . 52. Cambridge University Press , 459--478. Bernard Mourrain, Fabrice Rouillier, and Marie-Fran\u00e7oise Roy. 2005. Bernstein's basis and real root isolation. In Combinatorial and Computational Geometry. MSRI Publications, Vol. 52. Cambridge University Press, 459--478."},{"key":"e_1_2_2_19_1","volume-title":"Solution of Cubic and Quartic Equations","author":"Neumark Stefan","unstructured":"Stefan Neumark . 1965. Solution of Cubic and Quartic Equations . Pergamon . 5--11 pages. https:\/\/doi.org\/10.1016\/B978-0-08-011220-6.50005-6 Stefan Neumark. 1965. Solution of Cubic and Quartic Equations. Pergamon. 5--11 pages. https:\/\/doi.org\/10.1016\/B978-0-08-011220-6.50005-6"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2002.0531"},{"key":"e_1_2_2_21_1","volume-title":"Flannery","author":"Press William H.","year":"1992","unstructured":"William H. Press , Saul A. Teukolsky , William T. Vetterling , and Brian P . Flannery . 1992 . Numerical Recipes in C (2nd Ed.): The Art of Scientific Computing. Cambridge University Press , USA. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. 1992. Numerical Recipes in C (2nd Ed.): The Art of Scientific Computing. Cambridge University Press, USA."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3233307"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2015.03.004"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.piutam.2011.04.023"},{"key":"e_1_2_2_25_1","first-page":"251","article-title":"A universal method of solving quartic equations","volume":"71","author":"Shmakov Sergei L","year":"2011","unstructured":"Sergei L Shmakov . 2011 . A universal method of solving quartic equations . Int. J. Pure Appl. Math 71 , 2 (2011), 251 -- 259 . Sergei L Shmakov. 2011. A universal method of solving quartic equations. Int. J. Pure Appl. Math 71, 2 (2011), 251--259.","journal-title":"Int. J. Pure Appl. Math"},{"key":"e_1_2_2_26_1","first-page":"013","volume-title":"Wavelet-based Multiresolution Isosurface Rendering. In IEEE\/EG Symposium on","volume":"10","author":"Steinberger Markus","year":"2010","unstructured":"Markus Steinberger and Markus Grabner . 2010 . Wavelet-based Multiresolution Isosurface Rendering. In IEEE\/EG Symposium on Volume Graphics. The Eurographics Association. https:\/\/doi.org\/ 10 .2312\/VG\/VG10\/ 013 - 020 Markus Steinberger and Markus Grabner. 2010. Wavelet-based Multiresolution Isosurface Rendering. In IEEE\/EG Symposium on Volume Graphics. The Eurographics Association. https:\/\/doi.org\/10.2312\/VG\/VG10\/013-020"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2010.04.015"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2010.12.025"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185603"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661237"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406178"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601199"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/S002555720000454X"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073692"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3400301"},{"key":"e_1_2_2_36_1","unstructured":"Cem Yuksel. 2022. Polynomial Roots. http:\/\/www.cemyuksel.com\/?x=polynomials  Cem Yuksel. 2022. Polynomial Roots. http:\/\/www.cemyuksel.com\/?x=polynomials"}],"container-title":["Proceedings of the ACM on Computer Graphics and Interactive Techniques"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543865","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:40Z","timestamp":1750268980000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,25]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,25]]}},"alternative-id":["10.1145\/3543865"],"URL":"https:\/\/doi.org\/10.1145\/3543865","relation":{},"ISSN":["2577-6193"],"issn-type":[{"value":"2577-6193","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,25]]},"assertion":[{"value":"2022-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}