Polynomial Homotopy Continuation: Under the Hood

多项式方程组在科学和工程数学模型中是普遍存在的。研究这类系统的解的代数几何领域，有潜力改进这些系统的实际数值研究技术。本研究项目旨在应用代数几何来推进求解多项式方程组的数值算法。研究包括开发新的同伦延拓方法，利用单群的作用、随机游动同伦和混合算法来求解稀疏系统。新的理论框架和算法将在开源软件中实现。同伦延拓算法是现代非线性代数的主干，是解决不一定是线性方程组的艺术。这些算法的主要优势在于近似计算，它通常比经典的精确技术快得多，并且可以处理高维空间中的问题。同伦延拓方法分三步求解问题a:(1)在与问题a相同的问题族中寻找问题B，但其结构更简单；(2)构造简单问题B的解；(3)用同伦即连续变形连接A和B，跟踪B的解如何变形为A的解。本项目旨在开发一种新的基本同伦延拓例程框架。一个主要的观点是，在更大程度上随机化数值算法使它们更快、更健壮，而不需要增加昂贵的计算精度。另一点是，为了最小化计算成本，我们应该发明新的混合方法，将源自不同数学领域的精确和近似技术交织在一起。符号、组合和数值思想的共生关系是求解稀疏系统新方法的关键。来自热带几何和数值代数几何的工具将提供多面体同伦算法的推广，并导致更快的多项式系统求解器，受益于更紧凑的解计数。

Systems of polynomial equations are ubiquitous in mathematical models in science and engineering. The field of algebraic geometry, which studies solutions to such systems, has the potential to improve techniques for practical numerical investigations of these systems. This research project aims to apply algebraic geometry to advance numerical algorithms for solving systems of polynomial equations. The research includes developing new homotopy continuation methods that exploit the action of the monodromy group, random walk homotopies, and hybrid algorithms for solving sparse systems. The new theoretical framework and algorithms will be implemented in open-source software. Homotopy continuation algorithms are a backbone of modern nonlinear algebra, the art of solving systems of equations that are not necessarily linear. The main strength of these algorithms is in approximate computation, which often is much faster than classical exact techniques and allows tackling problems in high-dimensional spaces. Homotopy continuation methods solve a problem A in three steps: (1) look for a problem B in the same family of problems as A, but with a simpler structure; (2) construct solutions to that simpler problem B; (3) connect A and B with a homotopy, that is, a continuous deformation, and track how solutions of B morph into solutions of A. This project aims to develop a novel framework for basic homotopy continuation routines. One major point is that randomizing numerical algorithms to a greater extent makes them even faster and more robust without a costly increase in computational precision. Another point is that, looking to minimize computational costs, we should invent new hybrid methods intertwining exact and approximate techniques originating in different areas of mathematics. The symbiosis of symbolic, combinatorial, and numerical ideas is the key to the new methods for solving sparse systems. Tools from tropical geometry and numerical algebraic geometry will deliver a generalization of polyhedral homotopy algorithms and lead to a faster polynomial system solver that benefits from a tighter solution count.