期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

CAGD/CG领域中一元多项式方程求根问题综述 被引量：6

Survey of Real Root Finding of Univariate Polynomial Equation in CAGD/CG
在线阅读 下载PDF
导出
摘要 在CAGD/CG领域中的很多基本算法都可以归结为一元方程的求根问题,经典的一元多项式方程求根算法多是针对幂基函数表示的.Bernstein基函数以其良好的数值计算稳定性、直观的几何意义在CAGD/CG中有着广泛的应用.文中对CAGD/CG中的一元幂基和Bernstein多项式方程求根算法从理论基础、数值鲁棒性与计算效率等方面做了详细介绍、分析和实验对比,并对于如何选用各种算法给出了建议. Many basic algorithms in the field of CAGD/CC can be reduced to the problems of root finding of univariate polynomials. In the early years of CAGD/CG, this problem is solved by converting to power basis for root finding, since many algorithms in power basis have been widely used. However, root finding algorithms for polynomials in Bernstein form are getting more and more attractive for their numerical stability and intuitive geometric significance. In this survey, different root finding algorithms for univariate polynomial in both power and Bernstein forms are introduced, analyzed and compared in terms of theoretical basis, numerical robustness and computational efficiency. Meanwhile, suggestions on how to select suitable algorithm are given.
作者 卫飞飞 周飞 冯结青
机构地区 浙江大学CAD&CG国家重点实验室 云南大学云南省电子计算中心数字媒体实验室
出处 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2011年第2期193-207,共15页 Journal of Computer-Aided Design & Computer Graphics
基金 国家自然科学基金(60933007 60736019) 国家"九七三"重点基础研究发展计划项目(2009CB320801)
关键词 BERNSTEIN基函数 幂基函数 一元多项式方程 求根 Bernstein basis function power basis function univariate polynomial equation root finding
分类号 TP391 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献76

  • 1McNamee J M. A bibliography on roots of polynomials [J]. Journal of Computational and Applied Mathematics, 1993, 47 (3) : 391-394.
  • 2McNamee J M. An updated supplementary bibliography on roots of polynomials [J]. Journal of Computational and Applied Mathematics, 1999, 110(2):305-306.
  • 3McNamee J M. A 2002 update of the supplementary bibliography on roots of polynomials [J]. Journal of Computational and Applied Mathematics, 2002, 142 ( 2 ):433-434.
  • 4Pan V Y. Solving a polynomial equation: some history and recent progress [J]. SIAM Review, 1997, 39(2) : 187-220.
  • 5Burnside W S, Panton A W. The theory of equations: with an introduction to the theory of binary algebraic forms [M]. 2nd ed. New York: Dover Publications, 1960.
  • 6Press W H, Teukolsky S A, Vetterling W T. Numerical recipes in C1 the art of scientific computing [M]. 2nd ed. New York: Cambridge University Press, 1992.
  • 7Rice J R. Numerical methods, software, and analysis[M]. New York: McGraw Hill Book Company, 1983.
  • 8Salmon G. Lessons introductory to the modern higher algebra [M]. 5th ed. New York: Chelsea Publishing, 1964.
  • 9Sederberg T W. Algorithm for algebraic curve intersection [J]. Computer-Aided Design, 1989, 21(9): 547-554.
  • 10Manocha D, Demmel J. Algorithms for intersecting parametric and algebraic curves I: simple intersections [J]. ACM Transactions on Graphics, 1994, 13(1): 73-100.

二级参考文献6

  • 1Sederberg T W,Nishita T.Curve intersection using Bézier clipping[J].Computer-Aided Design.1990,22(9):538-549.
  • 2Schulz C.Bézier clipping is quadratically convergent[J].Computer Aided Geometric Design.2009,26(3):61-74.
  • 3Bartovň M,Jüttler B.Computing roots of polynomials by quadratic clipping[J].Computer Aided Geometric Design.2007,24(3):125-141.
  • 4North N S.Intersection algorithms based on geometric intervals[D].Provo:Brigham Young University.Department of Computer Science.2007.
  • 5Liu L G,Zhang L,Lin B B,et al.Fast approach for computing roots of polynomials using cubic clipping[J].Computer Aided Geometric Design.2009,26(5):547-559.
  • 6Farin G.Curves and surfaces for CAGD:a practical guide[M].San Francisco:Morgan Kaufmann Publishers Inc.2002.

同被引文献38

  • 1孙伟,张彩明,杨兴强.Marching Cubes算法研究现状[J].计算机辅助设计与图形学学报,2007,19(7):947-952. 被引量：26
  • 2Elber G, Kim M S. Geometric constraint solver using multivariate rational spline functions [C] /]Proceedings of the 6th ACM Symposium on Solid Modeling and Applications. New York ACM Press, 2001 1-10.
  • 3Jakli G, Kozak J, Krajnc M, et al. On geometric interpolation by planar parametric polynomial curves [J]. Mathematics of Computation, 2007, 76(260) : 1981-1993.
  • 4Liu L G, Zhang L, Lin 13 B, et al. Fast approach for computing roots of polynomials using cubic clipping [J]. Computer Aided Geometric Design, 2009, 26(5) : 547-559.
  • 5Sederberg T W, Nishita T. Curve intersection using Bfizier clipping [J]. Computer-Aided Design, 1990, 22(9) : 538-549.
  • 6Patrikalakis N M, Maekawa T. Intersection problems [M] // Shape Interrogation for Computer Aided Design and Manufacturing. Heidelberg: Springer, 2002:109-160.
  • 7Choi Y K, Wang W P, Liu Y, et al. Continuous collision detection for elliptic disks [J]. IEEE Transactions on Robotics, 2006, 22(2): 213-224.
  • 8Chen X D, Yong J H, Wang G Z, et al. Computing the minimum distance between a point and a NURBS curve [J]. Computer-Aided Design, 2008, 40(10/11) : 1051-1054.
  • 9Collins G E, Akritas A G. Polynomial real root isolationusing Descartes's rule of signs [C] //Proceedings of the 3rd ACM Symposium on Symbolic and Algebraic Computation. New York: ACM Press, 1976: 272-275.
  • 10Rouilller F, Zimmermann P. Efficient isolation of polynomial's real roots [J]. Journal of Computational and Applied Mathematics, 2004, 162(1): 33-50.

引证文献6

二级引证文献12

计算机辅助设计与图形学学报
2011年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部