Approximate Solution of Degenerate Algebraic Systems

本文研究非精确系数过约束多项式方程组的符号-数值解法。我们的目标是开发和实施高效和可证明的强大技术，从根本上改善以前的结果。主题是：（1）建立了摄动分析的数学框架（2）引入了新的符号方法的迭代工具（3）扩展了现有数值方法的适用范围。在研究中应用的工具包括奇异值的非线性推广，多元推广的认证近似GCD，非标准应用的整体牛顿法，局部Weierstrass迭代，和一般的子结式理论。取得的成果包括：（1）具有不精确系数的过约束系统的“近解”的有意义和可验证的概念，（2）向后误差和条件分析，（3）简化现有数值技术的全局行为，（4）利用近解集的可能的小基数，以及（5）改进具有不精确和精确系数的过约束系统的复杂性界限。研究的最终目标是一个算法，它是多项式的输入加上输出的大小。在许多物理和工程应用中，人们需要求解过约束多项式系统，使得解的存在性由一些潜在的物理原因来保证。然而，由于测量或舍入误差，输入多项式的系数可能仅以有限的精度给出。例如，在几何建模、机器人学或机器视觉中出现这样的问题。从传统的数值的角度来看，这些问题被认为是病态的，并避免数值分析。另一方面，传统的符号方法会声明这些输入系统是不一致的，因此不能提供关于底层物理系统的解的信息。所提出的研究是为了从根本上提高效率的解决方案的过约束系统在广泛的应用领域。这项工作的教育目标包括设计一个研究生水平的课程，就上述主题连同讲义和研究生和本科生水平的研究项目清单。课程和项目面向应用和实施，以使学生对工业和学术界都有吸引力。研究人员正在努力创造一个支持代表性不足的学生参加高水平研究的环境。

This research is on symbolic-numeric techniques for the solution of over-constrained polynomial systems with inexact coefficients. The objective is to develop and implement highly efficient and provably robust techniques that radically improve previous results. Topics are: (1) establish a mathematical framework for perturbation analysis (2) introduce novel iterative tools for symbolic methods (3) extend the applicability of existing numerical techniques. The tools being applied in the research include non-linear generalization of singular values, multivariate generalization of certified approximate GCD, non-standard applications of global Newton's method, local Weierstrass iteration, and the theory of general sub-resultants. Results being obtained include: (1) a meaningful and verifiable notion of "near-solutions" of over-constrained systems with inexact coefficients, (2) backward error and conditioning analysis, (3) simplification of the global behavior of existing numerical techniques, (4) utilization of the possible small cardinality of the near-solution set, and (5) improved complexity bounds for over-constrained systems both with inexact and exact coefficients. The ultimate goal of the research is an algorithm, which is polynomial in the input plus the output size. In many physical and engineering applications one needs to solve over-constrained polynomial systems such that the existence of the solutions is guaranteed by some underlying physical reason. However, the coefficients of the input polynomials may be given only with limited accuracy due to measurement or rounding error. Such problems arise for example in geometric modeling, robotics, or machine vision. From the traditional numerical point of view these problems are considered ill-conditioned, and are avoided by numerical analysts. On the other hand, traditional symbolic methods would declare these input systems inconsistent, thus providing no information about the solutions of the underlying physical system. The proposed research is intended to radically improve efficiency of the solutions of over-constrained systems in a wide range of application areas. The educational objectives of this work include the design of a graduate level course on the above topic together with lecture notes and a list of research projects on both the graduate and undergraduate levels. The course and the projects are oriented towards applications and implementation in order to make the students attractive to both industry and academia. The investigator is working to create an environment that is supportive of underrepresented students to participating in high-level research.