Approximate Solution of Degenerate Algebraic Systems

简并代数系统的近似解

• 批准号: 0306406
• 负责人: Agnes Szanto
• 金额: $ 14.96万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-06-15 至 2006-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0306406&HistoricalAwards=false
• 关键词: Approximate; Solution; Degenerate; Algebraic; Systems

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.

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