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.