Efficient Computer Algorithms for Symbolic Mathematics

讨论了计算机代数和符号数学中高效顺序和并行算法的设计与开发问题。设计一种处理器效率的并行算法，用于解决抽象的，可能是模块化的域上的一般和特殊线性系统，以及设计一种有效的顺序算法，用于通过计算该矩阵与向量的乘积的函数来计算隐式给定方阵的特征多项式。Goldwasser-Kilian/Atkin Las Vegas整数素数测试的计算机实现将通过改进测试中使用的几个辅助数论算法来增强。一种由黑箱程序给出的多元多项式分解算法也将在工作站网络上实现。此外，对希尔伯特不可约型定理的更有效版本的研究将继续进行。提出了与符号计算的新兴应用相关的两个新课题的研究。在几何设计的激励下，将开发一种计算由多项式定义的具有浮点系数的隐式方程的代数曲线或曲面的不可约分量的算法。在计算机代数方法的攻击下，问题是计算有理二元多项式的近似因式分解。最后，在代数算法的分支，特殊函数的使用，如平方根，指数，或对数，在直线程序将被调查。特别地，我们将建立一个解析直线规划的模型，并研究该模型的转换理论。

Several problems on the subject of efficient sequential and parallel algorithm design and development for computer algebra and symbolic mathematics are considered. The design of a processor-efficient parallel algorithm for solving general and special linear systems over an abstract, possibly modular, domain will be investigated, as well as the design of an efficient sequential algorithm for computing the characteristic polynomial of an implicitly given square matrix by a function that computes the product of this matrix with a vector. A computer implementation of the Goldwasser-Kilian/Atkin Las Vegas integer primality test will be enhanced by improving several auxiliary number theoretical algorithms used in the test. An algorithm for factoring multivariate polynomials that are given by black box programs for their evaluation will also be implemented on a network of workstations. Furthermore, a search for more effective versions of Hilbert irreducibility-type theorems will continue. Research on two new topics that are related to emerging applications of symbolic computation is suggested. Motivated by geometric design, an algorithm for computing the irreducible components of an algebraic curve or surface given by its polynomial defining implicit equation with floating point coefficients will be developed. Attacked by computer algebra methods, the problem is to compute the approximate factorization of a rational bivariate polynomial. Finally, branching out of algebraic arithmetic, the usage of special function, such as squareroots, exponentials, or logarithms, in the straight-line program will be investigated. In particular, a model of an analytic straight- line program will be formulated, and a transformation theory for this model will be investigated.