The Computation of Gröbner Bases Using an Alternative Algorithm View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1998

AUTHORS

Joachim Apel

ABSTRACT

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. More... »

PAGES

35-45

Book

TITLE

Symbolic Rewriting Techniques

ISBN

978-3-0348-9779-2
978-3-0348-8800-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-0348-8800-4_2

DOI

http://dx.doi.org/10.1007/978-3-0348-8800-4_2

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1049932321


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, Augustusplatz 10/11, D-04109, Leipzig, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Apel", 
        "givenName": "Joachim", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1006/jsco.1995.1026", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004048476"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/190347.190416", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007445910"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0747-7171(86)80019-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035682132"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/202489.202492", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036419538"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0747-7171(08)80003-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047509416"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "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\u00f6bner 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\u00f6bner 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.", 
    "editor": [
      {
        "familyName": "Bronstein", 
        "givenName": "Manuel", 
        "type": "Person"
      }, 
      {
        "familyName": "Weispfenning", 
        "givenName": "Volker", 
        "type": "Person"
      }, 
      {
        "familyName": "Grabmeier", 
        "givenName": "Johannes", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-0348-8800-4_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-0348-9779-2", 
        "978-3-0348-8800-4"
      ], 
      "name": "Symbolic Rewriting Techniques", 
      "type": "Book"
    }, 
    "name": "The Computation of Gr\u00f6bner Bases Using an Alternative Algorithm", 
    "pagination": "35-45", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049932321"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-0348-8800-4_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "eddc9164c7a6237a8ed69fe36098d08f649c3c48cc52c54e978052e290ee91e2"
        ]
      }
    ], 
    "publisher": {
      "location": "Basel", 
      "name": "Birkh\u00e4user Basel", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-0348-8800-4_2", 
      "https://app.dimensions.ai/details/publication/pub.1049932321"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T09:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000371_0000000371/records_130814_00000004.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-0348-8800-4_2"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-0348-8800-4_2'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-0348-8800-4_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-0348-8800-4_2'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-0348-8800-4_2'


 

This table displays all metadata directly associated to this object as RDF triples.

88 TRIPLES      23 PREDICATES      32 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-0348-8800-4_2 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N0aac9db7e01144508dcec8840b422c50
4 schema:citation https://doi.org/10.1006/jsco.1995.1026
5 https://doi.org/10.1016/s0747-7171(08)80003-x
6 https://doi.org/10.1016/s0747-7171(86)80019-0
7 https://doi.org/10.1145/190347.190416
8 https://doi.org/10.1145/202489.202492
9 schema:datePublished 1998
10 schema:datePublishedReg 1998-01-01
11 schema:description 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.
12 schema:editor Nda0e09e8280c4e2fad34338684541dd7
13 schema:genre chapter
14 schema:inLanguage en
15 schema:isAccessibleForFree true
16 schema:isPartOf Nff6082c0842f4ac682126974fefd3b1f
17 schema:name The Computation of Gröbner Bases Using an Alternative Algorithm
18 schema:pagination 35-45
19 schema:productId N238a954cfac046df88de29a5e05df7e2
20 N68783af7a12e454284ef2c07409f2314
21 Nad6426e903624199a45bcd9e957d7d33
22 schema:publisher Ncbc75a2781f84ff0a340126a3efd8002
23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049932321
24 https://doi.org/10.1007/978-3-0348-8800-4_2
25 schema:sdDatePublished 2019-04-16T09:16
26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
27 schema:sdPublisher Ncabf525f433146debeb9f7edb5727dc8
28 schema:url https://link.springer.com/10.1007%2F978-3-0348-8800-4_2
29 sgo:license sg:explorer/license/
30 sgo:sdDataset chapters
31 rdf:type schema:Chapter
32 N0aac9db7e01144508dcec8840b422c50 rdf:first Nc685614df11245c8bb8ff2377951ecbc
33 rdf:rest rdf:nil
34 N15e55cb3ec574811af550527b9e3796a schema:familyName Grabmeier
35 schema:givenName Johannes
36 rdf:type schema:Person
37 N238a954cfac046df88de29a5e05df7e2 schema:name readcube_id
38 schema:value eddc9164c7a6237a8ed69fe36098d08f649c3c48cc52c54e978052e290ee91e2
39 rdf:type schema:PropertyValue
40 N68783af7a12e454284ef2c07409f2314 schema:name doi
41 schema:value 10.1007/978-3-0348-8800-4_2
42 rdf:type schema:PropertyValue
43 N6e9084a00e3a4c3b8974fc05ebaf2e8d schema:name Institut für Informatik, Universität Leipzig, Augustusplatz 10/11, D-04109, Leipzig, Germany
44 rdf:type schema:Organization
45 N6f13a4ea7a254c82a40e4513e2fb55e3 schema:familyName Bronstein
46 schema:givenName Manuel
47 rdf:type schema:Person
48 N8183bf26d4c940a39466de4da46955af rdf:first N15e55cb3ec574811af550527b9e3796a
49 rdf:rest rdf:nil
50 Nad6426e903624199a45bcd9e957d7d33 schema:name dimensions_id
51 schema:value pub.1049932321
52 rdf:type schema:PropertyValue
53 Nc685614df11245c8bb8ff2377951ecbc schema:affiliation N6e9084a00e3a4c3b8974fc05ebaf2e8d
54 schema:familyName Apel
55 schema:givenName Joachim
56 rdf:type schema:Person
57 Nc9ec4c9231074576807157c83d06e25b schema:familyName Weispfenning
58 schema:givenName Volker
59 rdf:type schema:Person
60 Ncabf525f433146debeb9f7edb5727dc8 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 Ncbc75a2781f84ff0a340126a3efd8002 schema:location Basel
63 schema:name Birkhäuser Basel
64 rdf:type schema:Organisation
65 Nd3e7654bc83f4bb5bb3fc374fbfd1b93 rdf:first Nc9ec4c9231074576807157c83d06e25b
66 rdf:rest N8183bf26d4c940a39466de4da46955af
67 Nda0e09e8280c4e2fad34338684541dd7 rdf:first N6f13a4ea7a254c82a40e4513e2fb55e3
68 rdf:rest Nd3e7654bc83f4bb5bb3fc374fbfd1b93
69 Nff6082c0842f4ac682126974fefd3b1f schema:isbn 978-3-0348-8800-4
70 978-3-0348-9779-2
71 schema:name Symbolic Rewriting Techniques
72 rdf:type schema:Book
73 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
74 schema:name Mathematical Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
77 schema:name Pure Mathematics
78 rdf:type schema:DefinedTerm
79 https://doi.org/10.1006/jsco.1995.1026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004048476
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1016/s0747-7171(08)80003-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1047509416
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1016/s0747-7171(86)80019-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035682132
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1145/190347.190416 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007445910
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/202489.202492 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036419538
88 rdf:type schema:CreativeWork
 




Preview window. Press ESC to close (or click here)


...