Files in this item
Files  Description  Format 

application/pdf 8701635.pdf (3MB)  (no description provided) 
Description
Title:  The Communication Complexity of Distributed Computing and a Parallel Algorithm for Polynomial Roots 
Author(s):  Tiwari, Prasoon 
Department / Program:  Electrical Engineering 
Discipline:  Electrical Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Engineering, Electronics and Electrical 
Abstract:  In the first part of the thesis, we begin with a discussion of the minimum communication requirements in some distributed networks. The main result is a general technique for determining lower bounds on the communication complexity of problems on various distributed computer networks. This general technique is derived by simulating the general network by a linear array and then using a lower bound on the communication complexity of the problem on the linear array. Applications of this technique yield nontrivial optimal or nearoptimal lower bounds on the communication complexity of distinctness, ranking, uniqueness, merging, and triangledetection on a ring, a mesh, and a complete binary tree of processors. A technique similar to the one used in proving the above results, yields interesting graph theoretic results concerning decomposition of a graph into complete bipartite subgraphs. Let (tau)(G) be the minimum number of complete bipartite graphs needed to partition the edges of G. Our results give tight bounds on (tau)(G) for certain classes of graphs. In an attempt to relate various models of distributed computation, we obtain a simulation result between two different models. We prove that every problem solved by a chaotic algorithm can also be solved by a token algorithm that uses at most three times the total number of messages in the worst case. The second part of the thesis, is devoted to the design of a fast parallel algorithm for determining all roots of a polynomial. Given a polynomial p(z) of degree n with m bit integer coefficients and an integer (mu), we consider the problem of determining all its roots with error less than 2('(mu)). It is shown that this problem is in the class NC if p(z) has all real roots. Some interesting properties of a Sturm sequence of a polynomial are proved and used in the design of a fast parallel algorithm for this problem. Using Newton identities and a novel numerical integration scheme, this algorithm determines good approximations to the linear factors of p(z). As an application of this rootfinding algorithm, we also prove that the problem of finding all eigenvectors of a symmetric matrix is also in NC. 
Issue Date:  1986 
Type:  Text 
Description:  87 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1986. 
URI:  http://hdl.handle.net/2142/69350 
Other Identifier(s):  (UMI)AAI8701635 
Date Available in IDEALS:  20141215 
Date Deposited:  1986 
This item appears in the following Collection(s)

Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois