• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

The Computation of Gröbner Bases Using an Alternative Algorithm

Apel, Joachim 04 October 2018 (has links)
When Zharkov and Blinkov ([ZB93]) applied the classical ideas of involutive systems originating from the theory of partial differential equations (c.f. [Ja29],[Po78]) to the computation of Gröbner bases (c.f. [Bu65],[BW93]) their theory seemed to be a rather marginal concept. But due to the opportunity of gaining a faster version for one of the most frequently applied algorithms the method came into the focus of computer algebra research (c.f. [Ap95], [GB95], [GS95], [Ma95]). It turned out that Pommaret bases are not only of interest for fast implementations (c.f. [ZB93]) but that they are also a point of contact of different theories which were investigated intensively for a long time. So, the theory of Pommaret bases enables the exchange of useful ideas between the theories as well as it benefits itself from the relationships. A certain similarity of the Zharkov/Blinkov method and the Kandri-Rody/Weispfenning closure technique motivates the study of commutative polynomial rings from a non-commutative point of view. The theory of Pommaret bases can be presented in an algebraic way using the Gröbner theory of graded structures. Here we will present the straight forward generalization of Pommaret bases to the class of algebras of solvable type. Under the non-commutative grading most calculations are pushed back to the free non-commutative polynomial ring. This provides a link to the theory of term rewriting and the Zharkov/Blinkov method appears as an application of the prefix reduction/saturation technique of Madlener and Reinert (c.f.[MR93]) with a restricted saturation. The restricted saturation has its natural origin in the syzygy theory and heavily improves the termination behaviour in the particular case of Pommaret bases. So, it seems to be worth to investigate the effect of splitting the saturation step also for similar term rewriting problems. The main result of this paper consists in the presentation of a termination condition for the Zharkov/Blinkov method providing an alternative algorithm for the computation of ordinary Gröbner bases which terminates for arbitrary ideals in the case of generalized degree compatible term orders.

Page generated in 0.2725 seconds