Loading...
Please wait, while we are loading the content...
Similar Documents
Algorithms and Orders for Finding Noncommutative Gröbner Bases (1997)
| Content Provider | CiteSeerX |
|---|---|
| Researcher | Keller, Benjamin J. |
| Abstract | The problem of choosing efficient algorithms and good admissible orders for computing Gröbner bases in noncommutative algebras is considered. Gröbner bases are an important tool that make many problems in polynomial algebra computationally tractable. However, the computation of Gröbner bases is expensive, and in noncommutative algebras is not guaranteed to terminate. The algorithm, together with the order used to determine the leading term of each polynomial, are known to affect the cost of the computation, and are the focus of this thesis. A Gröbner basis is a set of polynomials computed, using Buchberger’s algorithm, from another set of polynomials. The noncommutative form of Buchberger’s algorithm repeatedly constructs a new polynomial from a triple, which is a pair of polynomials whose leading terms overlap and form a nontrivial common multiple. The algorithm leaves a number of details underspecified, and can be altered to improve its behavior. A significant improvement is the development of a dynamic dictionary matching approach that efficiently solves the pattern matching problems of noncommutative Gröbner basis computations. Three algorithmic alternatives are considered: the strategy for selecting triples (selection), the strategy for removing triples from consideration (triple elimination), and the approach to keeping the set interreduced (set reduction). |
| File Format | |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Polynomial Algebra Noncommutative Gr Bner Basis Computation Finding Noncommutative Gr Bner Base Efficient Algorithm Buchberger Algorithm Dynamic Dictionary Matching Approach Algorithmic Alternative Significant Improvement Important Tool Gr Bner Basis Triple Elimination New Polynomial Gr Bner Base Many Problem Good Admissible Order Noncommutative Algebra Noncommutative Form Nontrivial Common Multiple Leading Term |
| Content Type | Text |
| Resource Type | Thesis |
