Solving systems of polynomial equations is a central problem in nonlinear and computational algebra. Since Buchberger's algorithm for computing Gr\"obner bases in the 60s, there has been a lot of progress in this domain. Moreover, these equations have been employed to model and solve problems from diverse disciplines such as biology, cryptography, and robotics. Currently, we have a good understanding of how to solve generic systems from a theoretical and algorithmic point of view. However, polynomial equations encountered in practice are usually structured, and so many properties and results about generic systems do not apply to them. For this reason, a common trend in the last decades has been to develop mathematical and algorithmic frameworks to exploit specific structures of systems of polynomials. Arguably, the most common structure is sparsity; that is, the polynomials of the systems only involve a few monomials. Since Bernstein, Khovanskii, and Kushnirenko's work on the expected number of solutions of sparse systems, toric geometry has been the default mathematical framework to employ sparsity. In particular, it is the crux of the matter behind the extension of classical tools to systems, such as resultant computations, homotopy continuation methods, and most recently, Gr\"obner bases. In this work, we will review these classical tools, their extensions, and recent progress in exploiting sparsity for solving polynomial systems. This manuscript complements its homonymous tutorial presented at the conference ISSAC 2022.
翻译:解决多式方程式系统是非线性和计算代数中的一个中心问题。 自Buchberger60年代计算Gr\'obner基数的计算算法以来, 这一领域已经取得了许多进展。 此外, 这些方程式被用于模拟和解决生物、 加密和机器人等不同学科的问题。 目前, 我们从理论和算法的角度对如何解决通用系统有很好的理解。 然而, 实践中遇到的多式方程式通常是结构化的, 通用系统的许多属性和结果并不适用于它们。 由于这个原因, 过去几十年的一个共同趋势是开发数学和算法框架来利用多式系统的具体结构。 可以说, 最常见的结构是偏狭的; 也就是说, 这些系统的多式数只涉及几个单数。 自伯恩斯坦、 科文斯基和库斯奈连连克的多式方程式通常结构, 如此众多的通用系统的属性和结果和结果都不适用于它们。 由于我们所预见的稀有的系统, 直径直的直径几度测量测量系统, 最近的一个常态的基数度框架, 也是其最默认的摩质的计算工具。