Efficient Randomized Algorithms for Multivariate Algebraic Computations

多元计算是在计算代数、计算代数几何和计算数论的背景下自然产生的。它还出现在各种领域，包括机器人学、计算机视觉、实体建模、自动几何定理证明和编码理论。这些研究领域的兴趣汇聚使得研究有效的多元代数计算方法变得更加重要。S在20世纪80年代对有效希尔伯特不可约定理的工作为设计可证明有效的随机算法来解决多元因式分解和广义随机分解的基本问题铺平了道路。该定理也为基于Kaltofen和Trager的新的黑箱方法以及使用直线规划的相关方法奠定了基础。希尔伯特不可约性定理及其相关理论所蕴含的几何思想，除了应用于多元因式分解和GCD外，还有待于从算法的角度加以充分利用。这项研究的目的是利用这些思想作为更一般的多变量计算问题的有效随机算法的基础。一方面，有效的Hilbert不可约性将被推广为更一般几何环境下的随机约简的基础。另一方面，黑盒方法将被探索为构建有效的多变量计算算法的一般范例。其目标是：(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.