### Abstract

Computing effective root bounds for constant algebraic expressions is a critical problem in the Exact Geometric Computation approach to robust geometric programs. Classical root bounds are often nonconstructive. Recently, various authors have proposed bounding methods which might be called constructive root bounds. For the important class of radical expressions, Burnikel et al (BFMS) have provided a constructive root bound which, in the division-free case, is an improvement over previously known bounds and is essentially tight. In the presence of division, their bound reguires a guadratic blowup in root bit-bound compared to the division-free case. We present a new constructive root bound that avoids this guadratic blowup and which is applicable to a more general class of algebraic expressions. This leads to dramatically better performance in some computations. We also give an improved version of the degree-measure bound from Mignotte and BFMS. We describe our implementation in the context of the Core Library, and report on some experimental results.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 496-505 |

Number of pages | 10 |

State | Published - 2001 |

Event | 2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 2001 Operating Section Proceedings, American Gas Association |
---|---|

Country | United States |

City | Dallas, TX |

Period | 4/30/01 → 5/1/01 |

### Keywords

- Algorithms
- Design
- Experimentation
- Measurement
- Performance
- Theory
- Verification

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'A new constructive root bound for algebraic expressions'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 496-505). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).