Study of Algorithms and Applications of Approximate Algebra

本研究的目的是：A)开发许多代数运算的近似代数算法；B)近似代数算法的误差分析与稳定；C) NSL-GAL系统的进一步改进；D)寻求近似代数的应用。我们针对每个目的进行了以下研究。算法研究：近似分解算法的大幅改进（Sasaki），利用Hensel构造开发多元近似GCD算法（Zhi, Kai & Noda），二元多项式的有理函数逼近方法（Kai, Noda & Kihara），代数函数解析延拓的证明方法的开发（Sasaki & Inaba），等等。误差分析与稳定：具有紧密根的多项式的子式理论及欧氏算法中的消去误差分析（Sasaki），有理函数近似的病态澄清及近似的稳定化（Kai, Noda & Murakami），一元多项式的小根与其他小根分离公式的推导（Terui & Sasaki），耦合代数方程Wu方法的稳定化（Kai, Noda, Zhi & Notake）等。系统改进：澄清了浮点数的有用性和注意点（有效浮点数）：在许多近似代数计算中，浮点数对于估计消去误差非常有用，但它过高估计了迭代逼近算法（如Newton方法）的误差（Kako, Fukui, 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).