Filip Ström: En experimentell studie av termreduktion med Gröbnerbaser och en alternativ algoritm

Abstract

The purpose of this paper is to compare two methods, in the form of algorithms, for reducing terms. In this context, reduction is described as the process of transforming an expression until it reaches a normal form. A classical example of reduction, commonly introduced early in mathematical education, is Gaussian elimination. The expressions being processed in this study are referred to as terms, which can be described as the product of one or more variables-possibly repeated-multiplied by a coefficient.

The first of the two algorithms examined in this project performs term reduction using a reduced Gröbner basis. A Gröbner basis is a special representation of an ideal, structured in such a way that it facilitates determining whether a polynomial belongs to the ideal, and can be computed using Buchberger’s algorithm. The second algorithm, referred to henceforth as the alternative algorithm, is presented in [JLN24] and only applies to ideals of a specific form.

The difference between the two algorithms may affect the computation time of the reduction process. This can be measured using a Python program that performs the calculations while counting the number of iteration steps. The results showed that reduction using a reduced Gröbner basis generally required fewer iteration steps than the alternative algorithm, for ideals that were randomly generated with specific properties.