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.