On Dynamic Algorithms for Algebraic Problems

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)

Stephen R. Tate, Professor and Department Head (Creator)

Institution

The University of North Carolina at Greensboro (UNCG )

Web Site: http://library.uncg.edu/

Abstract: In this paper, we examine the problem of incrementally evaluating algebraic functions. In particular, if f(x₁, x₂, …, x_n) = (y₁, y₂, …, y_m) is an algebraic problem, we consider answering on-line requests of the form "change input x_i to value v" or "what is the value of output y_j?" We first present lower bounds for some simply stated algebraic problems such as multipoint polynomial evaluation, polynomial reciprocal, and extended polynomial GCD, proving an Ω(n). lower bound for the incremental evaluation of these functions. In addition, we prove two time-space trade-off theorems that apply to incremental algorithms for almost all algebraic functions. We then derive several general-purpose algorithm design techniques and apply them to several fundamental algebraic problems. For example, we give an O( √ n  ) time per request algorithm for incremental DFT. We also present a design technique for serving incremental requests using a parallel machine, giving a choice of either optimal work with respect to the sequential incremental algorithm or superfast algorithms with O(log log n) time per request with a sublinear number of processors.

On Dynamic Algorithms for Algebraic Problems
PDF (Portable Document Format)
794 KB
Created on 3/14/2011
Views: 2059

Additional Information

Publication

Journal of Algorithms, Vol. 22, No. 2, 1997, pp. 347–371.

Language: English

Date: 1997

Keywords

Algorithms, Incremental, Mathematical models, Algebra

Email this document to