Topics in algebraic computing: Subresultants, GCD, factoring and primary ideal decomposition

Candidate: Ho,Chung-Jen

Abstract

Our goal is to present an algorithm for computing a primary decomposition of a zero-dimensional ideal. We compute the decomposition of the radical ideal of the zero-dimensional ideal and lift it to a primary decomposition. The algorithm for decomposing radicals simply uses Kronecker's method of elimination and GCD and factoring algorithms. Kronecker's method of elimination and GCD computations are related to resultant systems and subresultants. Thus, we first investigate the theory of subresultants. We expound the theory of subresultants along the lines suggested by Loos. However, there were some major oversights in Loos's proof of the Subresultant Theorem. We point out where exactly Loos's proof fails and give a correct version of proofs. Then, we define the Sylvester matrix of many polynomials and explore the properties of the Sylvester matrix. By these properties, we derive fast parallel algorithms for computing the GCD of many polynomials. Our algorithms have better processor bound than Von zur Gathen's algorithm. Moreover, one of the algorithms uses no divisions. The factoring algorithm deals with factoring polynomials over multiple algebraic extensions of rational number field. We present an algorithm to find an integer $D$ such that the defect of an integral basis for a multiple extension of Q divides $D$. Though there is a naive algorithm to find a $D$ by translating a multiple extension to a simple extension, our algorithm has much better time and space bound than the naive algorithm. With this result, we can directly factor polynomials without translating a multiple extension to a simple extension. Finally, we improve Kronecker's method of elimination; and then, by applying the GCD and factoring algorithms on the resultant systems generated by Kronecker's method of elimination, we obtain a tree representation of all the associated prime ideals belonging to the zero-dimensional ideal.