TY - JOUR

T1 - On the Communication Complexity of Distributed Algebraic Computation

AU - Luo, Zhi Quan

AU - Tsitsiklis, John N.

N1 - Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 1993/1/11

Y1 - 1993/1/11

N2 - We consider a situation where two processors F'l and Pz are to evaluate a collection of functions f],.… f, of two-vector variables x, v, under the assumption that processor P] (respectively, Pz ) has access only to the value of the variable x (respectively, y) and the functional form of ~1,.… f,. 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 are polynomials. We also derive some new lower bounds for the case of two-way communication that improve on earlier bounds by Abelson [2]. As an application, we consider the case where x and y are n X t~ matrices and f(x, y) is a particular entry of the inverse of.r + y. Under a certain restriction on the class of allowed communication protocols, we obtain an fl(n2) lower bound, in contrast to the Q(n) lower bound obtained by applying Abelson's results. Our results are based on certain tools from classical algebraic geomet~ and field extension theory.

AB - We consider a situation where two processors F'l and Pz are to evaluate a collection of functions f],.… f, of two-vector variables x, v, under the assumption that processor P] (respectively, Pz ) has access only to the value of the variable x (respectively, y) and the functional form of ~1,.… f,. 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 are polynomials. We also derive some new lower bounds for the case of two-way communication that improve on earlier bounds by Abelson [2]. As an application, we consider the case where x and y are n X t~ matrices and f(x, y) is a particular entry of the inverse of.r + y. Under a certain restriction on the class of allowed communication protocols, we obtain an fl(n2) lower bound, in contrast to the Q(n) lower bound obtained by applying Abelson's results. Our results are based on certain tools from classical algebraic geomet~ and field extension theory.

KW - Algebraic computation

KW - communication complexity

KW - lower bound

UR - http://www.scopus.com/inward/record.url?scp=0027693949&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027693949&partnerID=8YFLogxK

U2 - 10.1145/174147.174149

DO - 10.1145/174147.174149

M3 - Article

AN - SCOPUS:0027693949

SN - 0004-5411

VL - 40

SP - 1019

EP - 1047

JO - Journal of the ACM

JF - Journal of the ACM

IS - 5

ER -