Construction of a Superrobust Computation Paradigm

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

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.