AF: Small: Relaxation Techniques in Symbolic-Numeric Computation

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

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.