31 - Parallel Computation and Gröbner Bases: An Application for Converting Bases with the Gröbner Walk

Summary

Abstract

Basis conversion arises in many parts of computational mathematics and computer science such as solving algebraic equations, implicitization of algebraic sets, elimination theory, etc. In this paper we discuss the Gröbner walk method of Collart et al. to convert a given Gröbner basis of a multivariate polynomial ideal of arbitrary dimension into a Gröbner basis of the ideal with respect to another term order. We describe some improvements and a parallel implementation in parallel Maple, where we can still utilize the whole sequential library of the popular computer algebra system Maple. The system supports a variety of virtual machines that differ in the manner in which nodes are connected. Therefore, it is independent of the devices and easy to program. The programs may run on different hardware ranging from shared-memory machines over distributed memory architectures up to networks of workstations without any modification or re-compilation. Moreover, the programs are scalable in that they may be written to execute on many thousands of nodes. We show that our best implementation achieves a speed up of up to six over a sequential implementation. We also outline further applications of parallel computation in the Gröbner bases method.

Introduction

Buchberger's algorithm (Buchberger, 1965; Buchberger, 1985) for the computation of Gröbner bases has became one of the most important algorithms in providing exact solutions of scientific problems in multivariate polynomial ideal theory, elimination theory and so on.