Tree Structured Grobner Basis Computation on Parallel Machines

With the advent of symbolic mathematical software packages such as Maple, Mathematics, and Macsyma, symbolic computation has become widely used in many scientific applications. Though a significant effort has been put in performing numeric computation on multiprocessors, symbolic computation on parallel machines is still in an unexplored state. However, symbolic mathematical applications are ideal candidates for parallel processing, because they are computationally intensive. This paper considers the parallel computation of Grobner basis, a special basis for a multivariate polynomial ideal over a field that plays a key role in symbolic computation. Large Grobner basis computation poses a challenging problem due to its dynamic data dependent behavior and resource-intensiveness. In an attempt to meet this challenge, a new tree structured approach for Grobner basis computation in parallel is proposed in this paper. It constructs the Grobner basis of a set of polynomials from Grobner basis of its subsets. The tree structured approach proposed in this paper lends itself to parallel implementation and significantly reduces the computation time of large Grobner basis. Finally, experimental results illustrating the effectiveness of the new approacll are provided.