Dynamic algebraic algorithms


Journal Article

The authors examine the problem of incrementally evaluating algebraic functions. The paper presents both lower bounds and algorithm design techniques for algebraic problems. The first presentation deals with the lower bounds for simply stated algebraic problems: multipoint polynomial evaluation, polynomial reciprocal, and extended polynomial GCD. The second deals with two general purpose techniques for designing incremental algorithms. The first method can produce highly efficient incremental algorithms and the second method gives a slightly slower incremental algorithm for these problems but can be applicable to a wider class of problems than the first method.

Duke Authors

Cited Authors

  • Reif, JH; Tate, SR

Published Date

  • January 1, 1994

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 290 - 301

Citation Source

  • Scopus