AF: Small: Relaxation Techniques in Symbolic-Numeric Computation

AF：小：符号数值计算中的松弛技术

• 批准号: 1217557
• 负责人: Agnes Szanto
• 金额: $ 30万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217557&HistoricalAwards=false
• 关键词: AF; Small; Relaxation; Techniques; Symbolic

In many physical and engineering applications one needs to solve ``ill-posed'' or ``ill-conditioned'' computational problems, i.e. problems such that a small perturbation of the input substantially changes the output. The objective of the project is to tackle the following ill-posed or ill-conditioned problems:1. Solution of consistent overdetermined systems of polynomial equations, i.e. systems with more equations than unknowns. The coefficients of the input polynomials may be given only with limited accuracy due to measurement or rounding errors, thus the actual input system may be inconsistent. Such ill-posed problems arise for example in geometric modeling, robotics, or computer vision. 2. Decomposition of symmetric tensors which have low rank, or equivalently, decomposition of homogeneous polynomials into minimal sums of powers of linear forms. Again, small perturbations of the entries of the tensor will increase the rank to the ``generic rank'', so the structure of the decomposition changes, thus the problem is ill-posed. Low rank tensors have been utilized in numerous application areas where two-dimensional matrix representation of data was not sufficient for obtaining satisfying data analysis, including image and signal processing, algebraic complexity theory, higher order statistics, etc. 3. Solution of polynomial systems of equations which have root multiplicities. Small perturbations of the coefficients will create clusters of roots, completely changing the root structure, so these systems are ill-posed. Furthermore, roots of systems near ones with multiple roots are very sensitive to coefficient perturbations, thus they are ill-conditioned. These systems pose significant difficulties for global numerical solvers, and the distance from such degenerate systems is closely related to the computational complexity of such solvers. Although distant in appearance, these problems will be tackled using very similar techniques: convert them into well-conditioned optimization problems based on the underlying geometry that made these problems ill-posed, analyze output sensitivity under perturbations of the input, and apply relaxation techniques to improve efficiency. This project builds on the PI's and her collaborators' previous results, further advancing the understanding of how these different symbolic-numeric techniques relate to each other, and finding a unified platform which enhance their efficiency and robustness.

在许多物理和工程应用中，人们需要解决“病态”或“病态”的计算问题，即输入的微小扰动实质上改变输出的问题。该项目的目标是解决以下不适定或病态问题：1.相容的超定多项式方程组的解，即方程多于未知数的系统。由于测量或舍入误差，输入多项式的系数可能仅以有限的精度给出，因此实际输入系统可能不一致。这种不适定的问题出现在例如几何建模、机器人学或计算机视觉中。2.具有低秩次的对称张量的分解，或等价地，将齐次多项式分解成线性形式的最小幂和。同样，张量的条目的小扰动将把排名增加到“通用排名”，因此分解的结构改变，因此问题是不适定的。低秩张量已被用于许多应用领域，其中数据的二维矩阵表示不足以获得满意的数据分析，包括图像和信号处理、代数复杂性理论、高阶统计量等。3.具有根重数的多项式方程组的求解。系数的微小扰动将产生根簇，完全改变根的结构，因此这些系统是不适定的。此外，具有多个根的系统的根对系数扰动非常敏感，因此它们是病态的。这些系统给全局数值求解器带来了很大的困难，而与这种退化系统的距离与这种求解器的计算复杂性密切相关。尽管表面上看起来很遥远，但这些问题将使用非常相似的技术来解决：将它们转换为基于使这些问题不适定的基础几何的良好条件优化问题，分析输入扰动下的输出敏感度，并应用松弛技术来提高效率。这个项目建立在PI和她的合作者之前的结果的基础上，进一步促进了对这些不同的符号-数字技术如何相互关联的理解，并找到了一个统一的平台，从而提高了它们的效率和健壮性。