Development of Approximate Algebraic Computation System

本研究的目的是：1)开发一个近似代数系统，使我们能够监测浮点数的消去误差；2)研究各种代数运算的算法；3)寻求近似代数的应用。对于近似代数系统，我们所提出的有效浮点数已经在NSL (Nara Standard Lisp) （Kako）中实现，并被证明对近似代数计算（Sasaki & Kako）非常有用。此外，Kako还在NSL中实现了有效的复数浮点数和区间。在这些设施的基础上，在公式处理系统GAL中配备了有效浮点数和区间的数值类型，并在GAL中实现了这些数字系数的近似多项式的算术（由Sasaki和Kako）。所做的算法研究有：近似GCD算法的改进（Sasaki等人，Noda & Kai），单变量多项式的因子分离及其在多/近根问题中的应用（Sasaki等人），近似GCD与Pade近似的关系及连分式展开（Noda & Kai），单变量多项式项矩阵的特征值和特征向量的Puiseux级数展开方法（Kitamoto），利用多项式根近似幂级数展开的一次分解方法（Kitamoto），多项式GCD的快速算法（Motoyoshi）等。在应用方面，利用近似GCD对有理函数进行数值积分（Noda & Kai），利用多项式根的多元幂级数展开式对带参数控制系统进行代数求解（Kitamoto）等。我们认为这些研究几乎充分证明了近似代数的有效性。

The purposes of this research were, 1) to develop an approximate algebra system which allows us to monitor cancellation errors of the floating-point numbers, 2) to study algorithms of various algebraic operations, and 3) to seek for applications of approximate algebra.As for approximate algebra system, effective floating-point number which we have proposed has been implemented in NSL (Nara Standard Lisp) (by Kako), and proved to be quite useful for approximate algebraic computation (by Sasaki & Kako). Furthermore, effective complex floating-point number and interval have been implemented in NSL (by Kako). On the basis of these facilities, numeric types of effective-float and interval have been equipped in formula manipulation system GAL,and arithmetic of approximate polynomials with coefficients of these numbers have been implemented in GAL (by Sasaki & Kako).Algorithm studies done are, improvement of approximate GCD algorithm (by Sasaki et al., Noda & Kai), factor separation of univariate polynomial and its application to multiple/close root problem (Sasaki et al.), relationship between approximate GCD and Pade approximation & continued fraction expansion (by Noda & Kai), Puiseux series expansion method for eigenvalues and eigenvectors of matrices of univariate polynomial entries (by Kitamoto), primary decomposition method using approximate power series expansion of polynomial roots (by Kitamoto), fast algorithm for polynomial GCD (by Motoyoshi), and so on.As for application, approximate GCD was utilized for numerical integration of rational functions (by Noda & Kai), multivariate power series expansions of polynomial roots was utilized for algebraically solving control system with parameters (by Kitamoto), and so on.We think that effectiveness of approximate algebra has been proved almost sufficiently by these studies.