Study of Algorithms and Applications of Approximate Algebra

本研究的目的是：（1）发展许多代数运算的近似代数算法;（B）近似代数算法的误差分析和稳定化;（3）进一步改进NSL-GAL系统;（4）寻求近似代数的应用。我们为每个目的进行了以下研究。算法研究：对近似因式分解算法（Sasaki）进行了重大改进，利用Hensel构造发展了多元近似GCD算法（Zhi，Kai & Noda），二元多项式的有理函数逼近方法（Kai，Noda和Kihara），代数函数解析延拓的证明方法的发展（Sasaki & Inaba）等。误差分析和稳定化：具有相互接近的根的多项式的子结式理论和欧几里得算法中的消除误差的分析（Sasaki），有理函数逼近病态性的澄清与逼近的稳定化（Kai，Noda & Murakami），一元多项式的小根分离公式的推导（Terui & Sasaki），耦合代数方程吴方法的稳定化（Kai，Noda，Zhi & Notake）等。系统改进：漂浮物的重要性和注意点（有效浮点数）的定义如下：在许多近似代数计算中，浮式算法对于估计抵消误差非常有用，但是在迭代近似算法（如牛顿法）中，浮式算法高估了误差（Kako，福井，Sasaki & Oyoshi）.适用范围：对于由二维矩阵给出的数据进行图像重建，发现如果用Shirayanagi-Sweedler（Kai，Noda & Mizukuchi）的技术稳定广义逆矩阵方法，则可以很好地重建图像。

The purposes of this research are, A) to develop approximate algebraic algorithms for many algebraic operations, B) error analysis and stabilization of approximate algebraic algorithms, C) further improvement of NSL-GAL system, and D) to seek for applications of approximate algebra. We performed the following researches for each purpose.Algorithm study : drastic improvement of approximate factorization algorithm (Sasaki), development of multivariate approximate GCD algorithm using Hensel construction (Zhi, Kai & Noda), method of rational function approximation of bivariate polynomials (Kai, Noda & Kihara), development of certified method of analytic continuation of algebraic functions (Sasaki & Inaba), and so on. Error analysis and Stabilization : theory of subresultant of polynomials having mutually close roots and analysis of cancellation errors in the Euclidean algorithm (Sasaki), clarification of ill-conditionedness in rational function approximation and stabilization of the approximation (Kai, Noda & Murakami), derivation of a formula for separating small roots from others of univariate polynomial (Terui & Sasaki), stabilization of Wu's method for coupled algebraic equations (Kai, Noda, Zhi & Notake), and so on. System improvement : Usefulness and notice point of the efloat (effective floating-point number) are clarified : the efloat is very useful for estimating cancellation errors in many approximate algebraic computations, but it over-estimates the errors in iteratively approximating algorithms such as Newton's method (Kako, Fukui, Sasaki & Oyoshi). Application : As for image reconstruction from the data given as 2-dimensional matrix, it was found that the image can be reconstructed pretty well if the generalized inverse matrix method is stabilized by the technique of Shirayanagi-Sweedler (Kai, Noda & Mizukuchi).