Efficient Computer Algorithms for Symbolic Mathematics

点击翻译按钮获取中文摘要

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.