High-Performance Polynomial Root Finding for Graphics
High-Performance Polynomial Root Finding for Graphics
复制标题
高性能图形多项式求根
DOI：
10.1145/3543865
复制
发表时间：
2022
影响因子：
1.3
通讯作者：
Yuksel, Cem
中科院分区：
文献类型：
--
作者：
Yuksel, Cem
提出了一种计算效率高、数值健壮的多项式实根算法。它从确定给定多项式是单调的区间开始。对于三次多项式，该算法比解析解和直接应用牛顿迭代法更准确、更快。该方法一般推广到任意次多项式，但仅限于求实根，且在多项式次数方面具有二次最坏情况下的复杂性.我们证明了我们的方法优于我们测试的直到20次的其他多项式解.我们还给出了一个已知的有效数值解的绘制应用实例，并通过求解10次多项式证明了我们的方法提供了更快、更准确和更健壮的解.
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.
登录
查看更多内容
三次和四次方程的解
DOI：
--
发表时间：
1965
期刊：
影响因子：
--
作者：
S. Neumark
通讯作者：
S. Neumark
算法 954：适用于物理应用的准确高效的三次和四次方程求解器
影响因子：
2.7
作者：
N. Flocke
通讯作者：
N. Flocke
用于 GPU 上矢量图形渲染的曲线基元的分层光栅化
影响因子：
2.5
作者：
Mark Dokter;Jozef Hladky;Mathias Parger;Dieter Schmalstieg;Hans-Peter Seidel;Markus Steinberger
通讯作者：
Markus Steinberger
牛顿法的加速版本，收敛阶数为 3+1
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
T. McDougall;S. Wotherspoon;P. Barker
通讯作者：
P. Barker
尺度不变积分表面的快速光线追踪
影响因子：
2.5
作者：
M. Aydinlilar;C. Zanni
通讯作者：
C. Zanni