ISBN 9783843925303

978-3-8439-2530-3, Reihe Mathematik

Stephan Oberfranz
A randomized variant of the Gröbner Walk

111 Seiten, Dissertation Technische Universität Kaiserslautern (2016), Softcover, A5

Zusammenfassung / Abstract

The conversion of Gröbner bases with respect to different orderings can be done using the Gröbner Walk, regardless the dimension of the ideal, which has been introduced by Collart, Kalkbrener and Mall in 1997. In general, this is less computational costly than to compute a Gröbner basis with respect to the desired ordering directly using Buchberger's famous algorithm.

Gröbner Walk means computing Gröbner bases of an ideal for different orderings along a path through the Gröbner fan. Considering subalgebras instead of ideals, one can formulate the Sagbi Walk, an algorithm similar to the Gröbner Walk algorithm for converting subalgebra bases.\par We present the idea of randomization in the Gröbner Walk. Moreover, we show that the Gröbner Walk also works for arbitrary Gröbner bases. This gives rise to new and efficient versions of the Gröbner Walk, the Random Walk algorithms which we develop for Gröbner bases and for subalgebra bases.