Dynamic algebraic algorithms

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 Scholars

Author John H. Reif Computer Science