On the Communication Complexity of Distributed Algebraic Computation
Abstract
we consider a situation where two processors P sub 1 and P sub 2 ar e to evaluate a collection of functions function 1,....,function 8 of two vector variables x, y, under the assumption that processor P sub 1 (respectively, P sub 2) has access only to the value of the variable x (respectively, y) and the functional form of function 1,....,function 8. We provide some new bounds on the communication complexity (the amount of information that has to be exchanged between the processors) for this problem. An almost optimal bound is derived for the case of one-way communication when the functions function 1,...., function 8 are polynomials. We also derive some new lower bounds for the case of two-way communication which improve on earlier bounds by Abelson A 80. As an application, we consider the case where x and y are n x n matrices and f(x,y) is a particular entry of the inverse of x + y. Under certain restriction on the class of allowed communication protocols, we obtain an omega(n squared) lower bound, in contrast to the omega(n) lower bound obtained by applying Abelson's results. Our results are based on certain tools from classical algebraic geometry and field extension theory.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1989
- Accession Number
- ADA205784
Entities
People
- John N. Tsitsiklis
- Zhi-quan Luo
Organizations
- Massachusetts Institute of Technology