The Communication Complexity of Distributed Computing and a Parallel Algorithm for Polynomial Roots
Tiwari, Prasoon
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69350
Description
Title
The Communication Complexity of Distributed Computing and a Parallel Algorithm for Polynomial Roots
Author(s)
Tiwari, Prasoon
Issue Date
1986
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(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 near-optimal lower bounds on the communication complexity of distinctness, ranking, uniqueness, merging, and triangle-detection 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 root-finding algorithm, we also prove that the problem of finding all eigenvectors of a symmetric matrix is also in NC.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
