采用数值计算求解一类半代数系统全部整数解

Solving semi-algebraic systems is one of the main research objects in real algebraic geometry. It is one of the most active research topics in symbolic computation. Finding all the integer solutions of a bounded full-dimensional semi-algebraic system has important applications in the fields of nonlinear program optimization, automatic parallelization, etc. Most of the current methods for such problems are symbolic, which can produce the exact results. However, the high complexity of the symbolic methods limits their applications to small size problems. Instead, in this project we will make use of pure numerical methods to study such problems. This project will help initializing the numerical projection theory of semi-algebraic sets, developing efficient algorithms for zero-error computation, and designing an efficient multi-nested loop model to describe and enumerate all the integer solutions. The proposed idea in this project can avoid the expression swell problem occurring in symbolic computation. It is also easy to be implemented in mainstream programming languages. This project will provide theoretical support and computational tools for nonlinear program optimization, automatic parallelization and other applications.

半代数系统的求解是实代数几何研究的主要对象之一，它是符号计算领域最活跃的研究课题之一。计算有界全维数的半代数系统的全部整数解集在非线性程序优化和程序自动并行化方面具有重要的应用价值。目前求解半代数系统全部解的方法几乎是符号方法，符号方法具有计算结果准确的优势，但不足之处就是计算复杂度高，在实际应用中效率低，只能求解小规模的半代数系统。本项目将采用全数值的方法研究有界的全维数的半代数系统全部整数解问题，通过本项目的实施，我们将初步建立起半代数集数值投影的理论基础，发展零误差计算的高效率算法，设计出高效的多重循环的模型来描述和遍历全部整数解的方法。本项目提出的方法可避免符号算法的中间表达式膨胀问题，易于在目前流行的编程语言上实现，为非线性程序优化、自动并行化等领域提供理论支持和计算工具。

程序自动并行化是高性能计算的核心技术之一，大规模多重循环程序自动并行化和优化是程序并行化的难点。多重循环条件可采用有界半代数系统描述。因此，本项目瞄准大规模循环程序的自动并行化和优化这一应用目标，以半代数系统的解为研究对象，开展三个方面研究：在数值PSLQ算法的稳定性分析方面，解决了在有误差干扰的情况下，PSLQ算法的终止性问题，设计出了数值PSLQ算法，并完成了数值PSLQ算法的稳定性和算法复杂度分析，将二十世纪十大算法之一的准确计算的PSLQ推广到了数值计算的PSLQ，使其具有实用性和有效性；在此基础上，对零误差计算的基本问题进行研究，回答了可进行零误差计算的充要条件是这个数属于一致离散集合，从而将零误差计算的精度控制问题转换成对一致离散集合最小距离的下界的估计，按照这种思路，重新对有理数和高次代数数进行研究取得了一系列新结果，初步建立起了零误差计算学科方向。 在误差可控的数值投影方面，我们给出了代数曲面数值Roadmap的概念的严格定义，设计出了其误差可控的计算方法，从而为数值投影计算和曲面的拓扑结构的数值代数表示奠定了基础；我们针对代数系统正则和奇异的不同情形，给出了平面及高维空间曲线的数值追踪方法；在大规模循环程序自动并行和优化应用方面，提出了基于“问题规模”、程序结构和缓存访问等信息来表征一类特殊参数半代数系统描述的循环程序的方法，通过非线性拟合解决了不同规模循环程序真实性能的预测问题并由此反推出最佳分块参数。实现了相关算法，完成了曲线绘制的ApproxPlot、Roadmap的计算以及开源的循环程序分块优化等软件包。本项目发表论文18篇，培养研究生9人，其中4人毕业并获硕士学位，1人获博士学位。