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)中具有相互接近根的多项式的次结式理论和抵消误差分析(Sasaki)，有理函数逼近病态的澄清和逼近的稳定化(KAI，Noda&Murakami)，一元多项式小根与其他根分离公式的推导(Terui&Sasaki)，耦合代数方程(KAI，Noda，Zhi&Notake)吴方法的稳定化，等等。系统改进：阐明了有效浮点数的用处和注意事项：在许多近似代数计算中，有效浮点数对于估计抵消误差非常有用，但它高估了迭代逼近算法中的误差，如牛顿法(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).