Efficient Computer Algorithms for Symbolic Mathematics

该项目继续在设计，分析， 几种基本算法高效实现 计算机代数问题。 求解线性方程组的并行时间复杂度 进一步研究了具有最小处理器数目的系统。 新 稀疏线性系统的串行和并行随机算法， 探索，和多项式时间算法，使不可约多项式 可因子分解的通过单项式的变量的替代寻求。 另一个研究方向是如何处理符号计算过程中的不精确数据。 允许浮点数 符号中的系数（即， 参数化模型）被认为是至关重要的 象征性地解决现实世界中的问题 特别是 多项式时间内计算最近奇异Toeplitz问题 一个给定的Toeplitz矩阵的矩阵，和最近的一对多项式与 对于给定的一对相对素的多项式，公因子是一个起始因子。 这是精确容错符号计算理论的一个要点。 最后，在复数上因式分解的问题是最小扰动的， 一个绝对不可约曲线的一个版本被攻击。 算法 实现是使用DSC系统进行的，用于分发符号 计算在一个 工作站网络。

This project continues research in design, analysis, implementation of efficient algorithms for several basic computer algebra problems. The parallel time complexity of solving linear systems with a minimum number of processors is further investigated. New sequential and parallel randomized algorithms for sparse linear systems are explored, and polynomial-time algorithms that make irreducible polynomials factorizable via substitution of the variables by monomials are sought. Another research direction is how to handle imprecise data in the course of symbolic computation. The allowance of floating point coefficients in a symbolic (i.e., parameterized model) is considered crucial for a symbolic approach to real-world problem solving. In particular, the question of computing in polynomial-time the nearest singular Toeplitz matrix for a given Toeplitz matrix, and the nearest pair of polynomials with a common divisor for a given pair of relatively prime polynomials, is a starting point for the theory of precision-tolerant symbolic computation. Ultimately, the problem of factoring over the complex numbers a minimally perturbed version of an absolutely irreducible curve is attacked. Algorithm implementation is done using the DSC system for distributing a symbolic computation over a network of workstations.