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.
