权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

A Study of Research Supporting Environment of Parallel Algorithms

并行算法研究支撑环境研究

基本信息

批准号：
05680267
负责人：
NAKAMORI Mario
金额：
$ 1.09万
依托单位：
Tokyo University of Agriculture and Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至 1994
项目状态：
已结题

项目摘要

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.

本研究的目的是建立并行算法数据库，并建立一套设计新型并行算法的系统方法。为了做到这一点，我们考虑了如何表示算法。我们发现了类似问题的算法之间的相似性。特别是，我们发现了问题与算法之间的同态性。因此，我们研究了并行算法之间的关系。结果表明，如果我们适当地定义问题的代数结构和运算，算法通常以一种简单的形式描述。例如，列表上的算法以统一的方式描述，因此，排序和求和的算法具有相同的结构，只是操作不同。这种观点对并行算法的设计是有用的。同时，我们证明了许多np完全问题可以被描述为双线性规划问题。例如，我们将众所周知的可满足性问题描述为一个关于原始逻辑表达式长度的线性顺序的变量和约束的双线性规划问题。我们还将图上的色数、极大团、Hamilton环和同构等问题描述为多项式阶的双线性规划问题。作为一个相关的主题，我们研究了并行算法中的通信复杂性。我们研究了电子邮件系统中空间复杂性和通信复杂性之间的权衡。