Collaborative Research: Randomized and Structure-Based Algorithms in Commutative Algebra

合作研究：交换代数中的随机和基于结构的算法

• 批准号: 1522662
• 负责人: Sonja Petrovic
• 金额: $ 22.96万
• 依托单位: Illinois Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1522662&HistoricalAwards=false
• 关键词: Collaborative; Research; Randomized; Structure; Based

Systems of multivariate polynomial equations are ubiquitous in optimization, statistics, biology, and other fields of science and engineering. Solving such systems is a cornerstone of computational algebra today and the main focus of this project. The project addresses fundamental problems in symbolic computation with multivariate polynomials, with particular interest in very large systems that appear, for example, in biological data modeling and data mining. Such systems are so large that they cannot be completely read into the computer's memory. This project proposes the use of probabilistic and statistical analysis to cleverly select and sample smaller subsystems that lead to the desired solution. The problems attacked are fundamental questions of practical relevance. The project will also have educational and training activities in the development of human resources. In addition to many students working with the investigators, the project includes a Summer School on the foundational mathematical concepts from the areas relevant to this interdisciplinary research project. The target audience is graduate students; the School will foster a sense of community among the students and enhance further interdisciplinary collaboration. This research project approaches the problem of solving systems of polynomial equations, and of finding generators for polynomial ideals using a probabilistic method -- focusing on providing low expected runtime and the use of random choices -- for computational algebra problems that have high worst case complexity. The project uses the underlying combinatorial structure of certain families of problems (e.g. polynomial system feasibility) for significant speed-up. The resulting algorithms and software will be of use in commutative algebra, statistics, optimization, graph theory, and other fields where large-scale systems of polynomial equations arise naturally. The project adapts to the problem under study a sampling technique that has been used in computational geometry and optimization. The theoretically expected running time will be linear in the number of input polynomials. There are several applications including statistics and optimization, where key applied methods rely on algorithms to compute such ideal generators. Furthermore, the research will increase the use of combinatorial structures in polynomial computational problems, in particular, for the calculation of Nullstellensatz infeasibility certificates and syzygies. Applications have been found in graph theory, and further applications are expected in combinatorics, coding theory, and systems biology.

多元多项式方程组在最优化、统计学、生物学和其他科学与工程领域中无处不在。求解这样的系统是当今计算代数的基石，也是本项目的主要焦点。该项目解决了多变量多项式符号计算中的基本问题，特别关注诸如生物数据建模和数据挖掘等非常大的系统。这样的系统是如此之大，以至于它们不能完全读取到计算机的内存中。该项目建议使用概率和统计分析来巧妙地选择和采样导致所需解决方案的较小子系统。所讨论的问题是具有实际意义的基本问题。该项目还将进行人力资源开发方面的教育和培训活动。除了许多学生与研究人员一起工作外，该项目还包括一个与该跨学科研究项目相关领域的基础数学概念的暑期学校。目标受众是研究生；学院将培养学生的社区意识，并进一步加强跨学科合作。本研究项目解决多项式方程系统的问题，并使用概率方法寻找多项式理想的生成器，重点是提供低预期运行时间和随机选择的使用，用于具有高最坏情况复杂性的计算代数问题。该项目使用某些问题族（例如多项式系统可行性）的潜在组合结构来实现显著的加速。由此产生的算法和软件将用于交换代数、统计学、优化、图论和其他自然出现大规模多项式方程系统的领域。该项目采用了一种在计算几何和优化中应用的采样技术来研究所研究的问题。理论上期望的运行时间在输入多项式的数量上是线性的。有几种应用，包括统计和优化，其中关键的应用方法依赖于算法来计算这种理想的生成器。此外，该研究将增加组合结构在多项式计算问题中的使用，特别是在计算Nullstellensatz不可行性证明和协同性方面。已经在图论中发现了应用，并期望在组合学、编码理论和系统生物学中进一步应用。