This thesis aims to create efficient algorithms for computing in the ring R = Q[z1,...,zn]/T where T is a zero-dimensional triangular set. The presence of zero-divisors in R makes it a computational challenge to use modular algorithms. In particular, there has never been a proper modular algorithm for computing greatest common divisors of polynomials in R[x]. We present two new ways of resolving zero-divisors: Hensel lifting and fault tolerant rational reconstruction, which allows us to create a new modular gcd algorithm for R[x] as well as a new inversion algorithm for R. We have implemented our algorithms in Maple using the RECDEN library, and we show that they outperform the methods currently implemented in Mapleu27s RegularChains package. The method of Hensel lifting for resolving zero-divisors should give rise to other new modular algorithms for computing modulo triangular sets and our applications show that this approach is fruitful.
展开▼
