期刊
THEORETICAL COMPUTER SCIENCE
卷 409, 期 2, 页码 186-199出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2008.09.009
关键词
Algebraic number; Bivariate polynomial; Quartic; Sturm sequence
Based on precomputed Sturm-Habicht sequences, discriminants and invariants, we classify, isolate with rational points, and compare the real roots of polynomials of degree up to 4. In particular, we express all isolating points as rational functions of the input polynomial coefficients. Although the roots are algebraic numbers and can be expressed by radicals, such representation involves some roots of complex numbers. This is inefficient, and hard to handle in applications in geometric computing and quantifier elimination. We also define rational isolating points between the roots of the quintic. We combine these results with a simple version of Rational Univariate Representation to isolate all common real roots of a bivariate system of rational polynomials of total degree <= 2 and to compute the multiplicity of these roots. We present our software within library SYNAPS and perform experiments and comparisons with several public-domain implementations. Our package is 2-10 times faster than numerical methods and exact subdivision-based methods, including software with intrinsic filtering. (C) 2008 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据