Cited By
View all- Emiris ITsigaridas E(2008)Real algebraic numbers and polynomial systems of small degreeTheoretical Computer Science10.1016/j.tcs.2008.09.009409:2(186-199)Online publication date: 10-Dec-2008
Computing a rational in between
Pages 160 - 161
Abstract
We are interested in the following problem: Given two (distinct) real algebraic numbers in isolating interval representation, that is an isolating interval with rational endpoints and a square free polynomial with integer coefficients, can we compute a number between them as a rational function of the coefficients of the polynomials that define these two numbers?
Assume that the order of the two numbers is known (we will remove this assumption in the sequel). If we are given intervals that contain the real algebraic numbers and a procedure to refine them, we can solve our problem as follows: We refine the intervals until they become disjoint, this will happen eventually since we assume that the algebraic numbers are not equal, and then we compute a rational between the intervals, which separates the algebraic numbers. However, this iterative approach depends on separation bounds, e.g. [7]. We present a direct method, which is applicable when we allow in addition to compute the floor of a polynomial expression that involves real algebraic numbers.
The problem arises when we wish to compute rational numbers that isolate the roots of an integer polynomial of small degree, say ≤ 5 [2]. Also in geometry, in order to analyse the intersection of two quadrics P and Q [6], one needs to determine the real roots of the polynomial det(P +xQ) = 0, their multiplicities and a value in between each of these roots. Another motivation comes from the arrangement of quadrics [4] In this case a rational is needed separating two real roots of two polynomials with real algebraic numbers as coefficients. The real roots of such polynomials can be expressed as real algerbaic numbers and so we face the problem of computing a rational separating two real algebraic numbers.
References
[1]
B. Beauzamy, E. Bombieri, P. Enflo, and H.L. Montgomery. Products of polynomials in many variables. J. Number Theory, 36:219--245, 1990.
[2]
I. Z. Emiris and E. P. Tsigaridas. Real algebraic numbers and polynomial systems of small degree. Theoretical Computer Science, 2008. (to appear).
[3]
M. Mignotte and D. Ştefănescu. Polynomials: An algorithmic approach. Springer, 1999.
[4]
B. Mourrain, J.-P. Técourt, and M. Teillaud. On the computation of an arrangement of quadrics in 3d. Computational Geometry: Theory and Applications, 30(2):145--164, 2005.
[5]
D. Ştefănescu. Inequalities on polynomial roots. Mathematical Inequalities and Applications, 5(3):335--347, 2002.
[6]
C. Tu, W. Wang, B. Mourrain, and J. Wang. Signature sequence of intersection curve of two quadrics for exact morphological classification. 2005. URL citeseer.ist.psu.edu/tu05signature.html. (to appear in CAGD).
[7]
C.K. Yap. Fundamental Problems of Algorithmic Algebra. Oxford University Press, New York, 2000.
Recommendations
Computing rational Gauss-Chebyshev quadrature formulas with complex poles: The algorithm
We provide an algorithm to compute arbitrarily many nodes and weights for rational Gauss-Chebyshev quadrature formulas integrating exactly in spaces of rational functions with complex poles outside [-1, 1]. Contrary to existing rational quadrature ...
Orthogonal rational functions and rational modifications of a measure on the unit circle
In this paper we present formulas expressing the orthogonal rational functions associated with a rational modification of a positive bounded Borel measure on the unit circle, in terms of the orthogonal rational functions associated with the initial ...
Orthogonal rational functions and quadrature on an interval
Rational functions with real poles and poles in the complex lower half-plane, orthogonal on the real line, are well known. Quadrature formulas similar to the Gauss formulas for orthogonal polynomials have been studied. We generalize to the case of ...
Comments
Information & Contributors
Information
Published In
Copyright © 2009 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 06 February 2009
Published in SIGSAM-CCA Volume 42, Issue 3
Check for updates
Qualifiers
- Poster
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 49Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Mar 2025
Other Metrics
Citations
Cited By
View all- Emiris ITsigaridas E(2008)Real algebraic numbers and polynomial systems of small degreeTheoretical Computer Science10.1016/j.tcs.2008.09.009409:2(186-199)Online publication date: 10-Dec-2008
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in