Robust Numerical Methods in Polynomial Algebra with Approximate Data

该项目旨在开发强大的数值方法和高质量软件包PolynPak，用于解决三个基本代数问题：单变量多项式AGCD（近似最大公约数），多变量多项式AGCD和精确的多重识别/寻根。这三个问题在应用中都有一个共同的假设，即给定的数据是经验性的，可能包含测量和舍入的误差。本项目的方法包括两阶段方法和理论，虽然GCD和多根在任意扰动下是不适定的/病态的，但当扰动保持结构时，它们是非常不敏感的。因此，在计算AGCD的结构和多重性后，将问题重新表述为结构约束下的最小二乘设置，可以消除病态性。该方法也适用于数值计算中的其他病态问题。这项研究是在计算机代数和数值分析领域进行的，其任务是为科学界和工业界提供可靠的算法和软件来解决数学问题。由于多项式是应用数学中最基本的模型之一，在经济平衡、化学反应、图像处理/恢复等领域有着广泛的应用，因此，开发多项式代数的鲁棒算法和软件，作为本项目的目标，可能会对这些应用和科学计算产生深远的影响。

The project aims to develop robust numerical methods and a high quality software package PolynPak for solving three fundamental algebraic problems: the univariate polynomial AGCD (approximate greatest common divisor), the multivariate polynomial AGCD, and accurate multiplicity-identification/root-finding. All three problems are under a common assumption in application that the given data are empirical and may contain errors from measurement and rounding-off. The methodology in this project consists of a two-stage approach and the theory that, while GCD and multiple roots are ill-posed/ill-conditioned under arbitrary perturbation, they are remarkably insensitive when perturbations are structure-preserving. Therefore, the ill-posedness can be removed by reformulating the problem in a least squares setting under a structural constraint after calculating the structure of AGCD and multiplicity. The approach in this project may also be applicable to other ill-posed problems in numerical computation. This research is carried out in the fields of computer algebra and numerical analysis where the mission is to provide the scientific and industrial community with reliable algorithms and software for solving mathematical problems. Since polynomial is one of the most fundamental models in applied mathematics with a wide range of applications in areas such as economic equilibria, chemical reaction, image processing/restoration, to name a few, developing robust algorithms and software for polynomial algebra, as the objective of this project, may have profound impact in those applications and in scientific computing.