Efficient Randomized Algorithms for Multivariate Algebraic Computations

多元代数计算的高效随机算法

• 批准号: 9820778
• 负责人: Ming-Deh Huang
• 金额: $ 25.46万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-08-15 至 2003-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9820778&HistoricalAwards=false
• 关键词: Efficient; Randomized; Algorithms; Multivariate; Algebraic

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.

多元计算在计算代数、计算代数几何和计算数论中自然出现。它也出现在许多领域，包括机器人、计算机视觉、实体建模、自动几何定理证明和编码理论。这些研究领域的兴趣融合使得研究多元代数计算的有效方法变得更加重要。20世纪80年代对有效希尔伯特不可约定理的研究为设计可证明的高效随机算法解决多元分解和GCD等基本问题铺平了道路。该定理还为Kaltofen和Trager提出的新颖的黑盒方法以及使用直线程序的相关方法奠定了基础。希尔伯特不可约定理及其相关理论中固有的几何思想，除了在多元分解和GCD中的应用之外，还有待从算法的角度来充分利用。本研究的目标是利用这些思想作为更一般的多变量计算问题的高效随机算法的基础。一方面，有效的希尔伯特不可约性将作为随机化约的基础在更一般的几何环境中得到推广。另一方面，黑盒方法将作为构建多变量计算的高效算法的一般范例进行探索。目标是：(1)设计比现有算法更有效的随机算法，(2)将结果应用于计算数论和计算代数几何，并进一步应用于密码学和编码理论，以及其他领域。调查将首先围绕一组涉及多元多项式系统的问题，包括：求解多元多项式系统；将多元多项式系统所定义的代数集分解为不可约分量计算代数集合中每个分量的度；代数集合的组成部分上的抽样随机点；判定多项式是否在代数集合上消失；确定代数集合中某一点的局部维数。这些问题为研究提供了肥沃的土壤，它们有许多有趣的应用，也将在本项目中进行探索。这项研究可能会影响多元计算的理论和实践，并导致对代数和几何计算中随机化的有用性的更深层次的理解。