Approximate Solution of 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.