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

Construction of a Superrobust Computation Paradigm

构建超鲁棒计算范式

基本信息

批准号：
15100001
负责人：
SUGIHARA Kokichi
金额：
$ 75.3万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (S)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2007
项目状态：
已结题

项目摘要

The goal of this research was to construct a paradigm for designing robust algorithms in a wide area of computation. To achieve this goal, we developed robust computation techniques in individual areas of computations such as physical simulation, parallel and distributed computation, computation for control, geometric computation, discrete optimization, information coding, and quantum computation, and from them we tried to extract common and transversal principles applicable to designing robust algorithms in a wide area of computation. As the results, we succeeded in extracting the following general principles. The first principle is to use structural invariances that lay behind the computation. Applying this principle, we developed robust geometric algorithms based on topologically consistent graph manipulations, robust methods for solving partial differential equations based on physical laws behind, robust control based on causal relations among events, and robust algebraic computations based on sign patterns and zero-nonzero patterns. The second principle is to remove restrictions by extending the object world; examples are hyperfigure algebra and symbolic perturbation in geometric computations. The third principle is to remove uncertainty by restricting the object world. The other principles include modeling of uncertainty for coping with the worst case, and the generalizations by the removal of unrealistic assumptions of the computational world. These principles have also been applied to individual computation such as discrete optimization, mathematical programming, coding, matrix computation, integer programming related to practical problems. Thus we established a first version of superrobust computation paradigm.

本研究的目的是为在广泛的计算领域中设计健壮的算法构建一个范例。为了实现这一目标，我们在物理模拟、并行和分布式计算、控制计算、几何计算、离散优化、信息编码和量子计算等计算领域开发了鲁棒计算技术，并试图从中提取适用于在广泛计算领域设计鲁棒算法的通用和横向原则。作为结果，我们成功地提取了以下一般原则。第一个原则是使用计算背后的结构不变性。应用这一原理，我们开发了基于拓扑一致性图操作的鲁棒几何算法，基于背后物理定律的求解偏微分方程的鲁棒方法，基于事件之间因果关系的鲁棒控制，以及基于符号模式和零-非零模式的鲁棒代数计算。第二个原则是通过扩展对象世界来消除限制；例如几何计算中的超图形代数和符号摄动。第三个原则是通过限制对象世界来消除不确定性。其他原则包括应对最坏情况的不确定性建模，以及通过消除计算世界中不切实际的假设来进行概括。这些原则也被应用于个别计算，如离散优化，数学规划，编码，矩阵计算，整数规划相关的实际问题。因此，我们建立了第一个版本的超鲁棒计算范式。

项目成果

期刊论文数量（248）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

On the relationship between convex bodies related to correlation experiments with dichotomic observables

DOI：
10.1088/0305-4470/39/36/010
发表时间：
2006-05
期刊：
Journal of Physics A
影响因子：
0
作者：
D. Avis;H. Imai;Tsuyoshi Ito McGill University;T. U. O. Tokyo;Japan Science;Technology Agency;Japan Science
通讯作者：
D. Avis;H. Imai;Tsuyoshi Ito McGill University;T. U. O. Tokyo;Japan Science;Technology Agency;Japan Science

Polynomial-time algorithms for probabilistic solutions of parameter-dependent linear matrix inequalities

参数相关线性矩阵不等式概率解的多项式时间算法