Keywords (1)

Academic
Publications
A Separation Bound for Real Algebraic Expressions

A Separation Bound for Real Algebraic Expressions,10.1007/s00453-007-9132-4,Algorithmica,Christoph Burnikel,Stefan Funke,Kurt Mehlhorn,Stefan Schirra,

A Separation Bound for Real Algebraic Expressions   (Citations: 2)
BibTex | RIS | RefWorks Download
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real.
Journal: Algorithmica , vol. 55, no. 1, pp. 14-28, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...There are four ingredients in our real RAM implementation: (a) certified approximation of basic real functions (e.g., [4]), (b) the theory of constructive zero bounds [6, 29], (c) a precision-driven evaluation mechanism [24], and (d) filter mechanism [5, 17]...
    • ...Invisible to users, the evaluation of expressions relies on two critical functions: filters [5, 7, 17] and zero bounds [6,35]...
    • ...E.g., it is useful to add diamond operator [6, 41], product, summation (see below), etc...
    • ...We see here that the default Expr class in Core 2 uses the k-ary BFMSS root bounds [6, 35] and the new BigFloat2 kernel (below)...
    • ...the diamond operator (a0 ,...,a n ,i )t o extract theith real root of a polynomial p(x )= n=0 aix i [6] where ai’s are expressions...

    Jihun Yuet al. The Design of Core 2: A Library for Exact Numeric Computation in Geome...

Sort by: