Resolving Zero-Divisors of Radical Triangular Sets Using Hensel Lifting and Applications

Date created: 
2017-08-16
Identifier: 
etd10318
Keywords: 
Computer Algebra
Modular Algorithms,
Triangular Sets, Radical Ideals
Inversion
Greatest Common Divisors
Maple
Abstract: 

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 Maple's 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.

Document type: 
Thesis
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
File(s): 
Senior supervisor: 
Michael Monagan
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Statistics: