Efficient Randomized Algorithms for Multivariate Algebraic Computations

多变量计算在计算代数、计算代数几何和计算数论的背景下自然出现。 它也出现在各种领域，包括机器人，计算机视觉，实体建模，自动几何定理证明和编码理论。 从这些研究领域的利益汇合，使其更加重要的是，调查有效的方法，多元代数computation.The工程有效的希尔伯特不可约定理在20世纪80年代铺平了道路，设计可证明有效的随机算法的基本问题的多元因式分解和GCD。 该定理也为卡尔托芬和特雷格的新黑箱方法以及使用直线程序的相关方法奠定了基础。 希尔伯特不可约定理及其相关理论中固有的几何思想还没有从算法的角度得到充分利用，而不仅仅是应用于多元因子分解和GCD。 本研究的目标是利用这些想法的基础上，更一般的多变量计算问题的有效的随机算法。 一方面，有效的希尔伯特不可约性将在更一般的几何环境中作为随机约化的基础。 另一方面，黑盒的方法将探讨作为一个通用的范例，为多变量计算的有效算法的建设。 目标是：（1）设计比现有算法更有效的随机化算法;（2）将结果应用于计算数论和计算代数几何，并进一步应用于密码学和编码理论以及其他领域。 本研究将首先围绕一系列涉及多元多项式系统的问题展开，包括：求解多元多项式系统;将由多元多项式系统定义的代数集分解为不可约分量;计算代数集每个分量的次数;在代数集的分量上随机采样点;判定多项式在代数集上是否为零;以及确定代数集合的点处的局部维数。 这些问题提供了一个肥沃的土壤调查，他们有许多有趣的应用程序，也将在这个项目中进行探索，这项研究可能会影响多元计算的理论和实践，并导致更深入地了解随机化的有用性在代数和几何计算的上下文中。

Multivariate computation arises naturally in the contexts of computational algebra, computational algebraic geometry, and computational number theory. It also arises in a variety of domains including robotics, computer vision, solid modeling, automatic geometric theorem proving, and coding theory. The confluence of interest from these research areas has made it all the more important to investigate efficient methods for multivariate algebraic computation.The works on effective Hilbert irreducibility theorem in the 1980's paved the way for designing provably efficient randomized algorithms for the fundamental problems of multivariate factorization and GCD. The theorem also laid the foundation for the novel black-box approach due to Kaltofen and Trager, as well as a related approach using straight-line programs. The geometric ideas inherent in the Hilbert irreducibility theorem and the related theory are yet to be fully exploited from an algorithmic point of view beyond their applications to multivariate factorization and GCD. The goal of this research is to utilize these ideas as the basis of efficient randomized algorithms for more general multivariate computational problems. On the one hand, effective Hilbert irreducibility will be extended as the basis of randomized reductions in a more general geometric setting. On the other hand, the black-box approach will be explored as a general paradigm for the construction of efficient algorithms for multivariate computations. The objectives are: (1) To design randomized algorithms that are substantially more efficient than the existing algorithms, and (2) To apply the results to computational number theory and computational algebraic geometry, with further application to cryptography and coding theory, and other areas as well. The investigation will initially center around a set of problems that involve multivariate polynomial systems including: solving a system of multivariate polynomials; decomposing an algebraic set defined by a system of multivariate polynomials into irreducible components; computing the degree of each component of an algebraic set; samplingrandom points on a component of an algebraic set; deciding if a polynomial vanishes on a algebraic set; and determining the local dimension at a point of an algebraic set. These problems provide a fertile ground for the investigation and they have many interesting applications which will also be explored in this project.This research will likely impact the theory and practice of multivariate computations and lead to a deeper understanding of the usefulness of randomization in the context of algebraic and geometric computations.