Robust Numerical Methods in Polynomial Algebra with Approximate Data

具有近似数据的多项式代数中的鲁棒数值方法

• 批准号: 0412003
• 负责人: Zhonggang Zeng
• 金额: $ 9.1万
• 依托单位: Northeastern Illinois University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0412003&HistoricalAwards=false
• 关键词: Robust; Numerical; Methods; Polynomial; Algebra

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.

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