A Study of Research Supporting Environment of Parallel Algorithms

点击翻译按钮获取中文摘要

The aim of this research is to make a database of parallel algorithms and to establish a systematic method of designing new parallel algorithms. In order to do this we considered how to represent algorithms. We found a similarity between algorithms for similar problems. Especially, we found homomorphism between problems and algorithms. Thus, we investigated relations between parallel algorithms. As a result, we showed that algorithms are usually described in a simple form if we define appropriately the algebraic structure and operations of the problem. For instance, algorithms on lists are described in a unified way and, thus, algorithms of sorting and summing numbers have the same structure except that only operations are different. This point of view is usefull for designing parallel algorithms. Also, we showed that many NP-complete problems can be described as a bilinear programming problems. For example, we described the well known satisfiability problem as a bilinear programming problem with variables and constraints of linear order in regard to the length of the original logical expression. We also described problems on graphs such as the chromatic number, the maximal clique, the Hamilton cycle, and the isomorphism as bilinear programming problems wigh variables and constraints of polynomial order. As a relating topic we investigated communication complexity in parallel algorithms. We investigated tradeoffs between space complexity and communication complexity in elctronic mail system.