A Modified Parallel F4 Algorithm for Shared and Distributed Memory Architectures

In applications of symbolic computation an often required but complex procedure is finding Gröbner bases for polynomial ideals. Hence it is obvious to realize parallel algorithms to compute them. There are already flavours of the F4 algorithm like [4] and [13] using the special structure of the occurring matrices to speed up the reductions on parallel architec-tures with shared memory. In this paper we start from these and present modifications allowing efficient computations of Gröbner bases on systems with distributed memory. To achieve this we concentrate on the following objectives: decreasing the memory consump-tion and avoiding communication overhead. We remove not required steps of the reduction, split the columns of the matrix in blocks for distribution and review the effectiveness of the SIMPLIFY function. Finally we evaluate benchmarks with up to 256 distributed threads of an implementation being available a