Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma

Benutzer


products/Sources/formale Sprachen/GAP/pkg/ibnp/doc/ (GAP Algebra Version 4.15.1^©) Datei vom 11.8.2025 mit Größe 10 kB

Quelle chap2.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/ibnp/doc/chap2.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (IBNP) - Chapter 2: Using the packages GBNP
and NMO</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap2" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap1.html">[Previous Chapter]</a> <a href="chap3.html">[Next Chapter]</a> </div>

<a href="chap2_mj.html">[MathJax on]</a>
<a id="X86057870803DCA93" name="X86057870803DCA93"></a>
<div class="ChapSects"><a href="chap2.html#X86057870803DCA93">2 Using the packages GBNP
and NMO</a>
<div class="ContSect"> <a href="chap2.html#X783C6EC87988B533">2.1 Noncommutative polynomials (NPs)</a>

</div>
<div class="ContSect"> <a href="chap2.html#X7E4277497D877661">2.2 Gröbner Bases</a>

</div>
<div class="ContSect"> <a href="chap2.html#X7F82A3608248CD31">2.3 Orderings for monomials</a>

</div>
</div>

<h3>2 Using the packages GBNP
and NMO</h3>

This package deals with polynomials in noncommutative algebras and to do so makes use of the noncommutative polynomial operations provided by the GBNP <a href="chapBib.html#biBGBNP">[CK24]</a> package, and orderings provided by the NMO package, which is now included within GBNP. In this chapter we remind users how to call some of these operations.

<a id="X783C6EC87988B533" name="X783C6EC87988B533"></a>

<h4>2.1 Noncommutative polynomials (NPs)</h4>

Recall that the main datatype used by the GBNP package is a list of noncommutative polynomials (NPs). The data type for a noncommutative polynomial (its NP format) is a list of two lists:

<ul>
<li>The first is a list m of monomials.

</li>
<li>The second is a list c of coefficients of these monomials.

</li>
</ul>
The two lists have the same length. The polynomial represented by the ordered pair [m,c] is ∑_i c_i m_i. A monomial is a list of positive integers. They are interpreted as the indices of the variables. So, if k = [1,3,2,2,1] and the variables are x,y,z (in this order), then k represents the monomial xzy^2x. There are various ways to print these, but the default uses variables a,b,c,.... The zero polynomial is represented by <code class="code">[[],[]]</code> and the polynomial 1 is represented by <code class="code">[[[]],[1]]</code>. The algorithms are applicable for the algebra F[x_1,x_2,...,x_t] of noncommutative polynomials in <var class="Arg">t</var> variables over the field F. Accordingly, the list c should contain elements of F.

The GBNP functions <code class="code">GP2NP</code> and <code class="code">NP2GP</code> convert a polynomial to NP format and back again. Polynomials returned by <code class="code">NP2GP</code> print with their coefficients enclosed in brackets. Polynomials may also be printed using the function <code class="code">PrintNP</code>. The function PrintNPList is used to print a list of NPs, with one polynomial per line. The function <code class="code">CleanNP</code> is used to collect terms and reorder them. The default ordering is first by degree and then lexicographically - <code class="code">MonomialGrlexOrdering</code>. Alternative orderings are available - see section <a href="chap2.html#X7F82A3608248CD31">2.3</a>.

<div class="example"><pre>

gap> A3 := FreeAssociativeAlgebraWithOne(Rationals,"a","b","c");;
gap> a := A3.1;; b := A3.2;; c := A3.3;;
gap> ## define a polynomial and convert to NP-format
gap> p1 := 7*a^2*b*c + 8*b*c*a;
(8)*b*c*a+(7)*a^2*b*c
gap> Lp1 := GP2NP( p1 );
[ [ [ 1, 1, 2, 3 ], [ 2, 3, 1 ] ], [ 7, 8 ] ]
gap> ## define an NP-poly; clean it; and convert to a polynomial
gap> Lp2 := [ [ [1,1], [1,2,1], [3], [1,1], [3,1,2] ], [5,6,7,8,9] ];;
gap> PrintNP( Lp2 );
5a^2 + 6aba + 7c + 8a^2 + 9cab
gap> Lp2 := CleanNP( Lp2 );
[ [ [ 3, 1, 2 ], [ 1, 2, 1 ], [ 1, 1 ], [ 3 ] ], [ 9, 6, 13, 7 ] ]
gap> ## note the degree lexicographic ordering
gap> PrintNP( Lp2 );
9cab + 6aba + 13a^2 + 7c
gap> p2 := NP2GP( Lp2, A3 );
(9)*c*a*b+(6)*a*b*a+(13)*a^2+(7)*c
gap> PrintNPList( [ Lp1, Lp2, [ [], [] ], [ [ [] ], [9] ] ] );
7a^2bc + 8bca
9cab + 6aba + 13a^2 + 7c
0
9

</pre></div>

<a id="X7E4277497D877661" name="X7E4277497D877661"></a>

<h4>2.2 Gröbner Bases</h4>

The GBNP package computes Gröbner bases using the function <code class="code">SGrobner</code>. In the example below the polynomials {p,q} define an ideal in Z[a,b] which has a three element Gröbner basis.

<div class="example"><pre>

gap> p := [ [ [2,2,2], [2,1], [1,2] ], [1,3,-1] ];;
gap> q := [ [ [1,1], [2] ], [1,1] ];; 
gap> PrintNPList( [p,q] );
b^3 + 3ba - ab
a^2 + b
gap> GB := SGrobner( [p,q] );;
gap> PrintNPList(GB);
a^2 + b
ba - ab
b^3 + 2ab

</pre></div>

<a id="X7F82A3608248CD31" name="X7F82A3608248CD31"></a>

<h4>2.3 Orderings for monomials</h4>

The three monomial orderings provided by the main GAP library are <code class="code">MonomialLexOrdering</code>, <code class="code">MonomialGrlexOrdering</code> and <code class="code">MonomialGrevlexOrdering</code>. The first of these is the default used by GBNP.

The NMO package is now part of the package GBNP. It provides a choice of orderings on monomials, including lexicographic and length-lexicographic ones.

<div class="example"><pre>

gap> Lp1;
[ [ [ 1, 1, 2, 3 ], [ 2, 3, 1 ] ], [ 7, 8 ] ]
gap> Lp2;
[ [ [ 3, 1, 2 ], [ 1, 2, 1 ], [ 1, 1 ], [ 3 ] ], [ 9, 6, 13, 7 ] ]
gap> GtNPoly( Lp1, Lp2 );
true
gap> ## select the lexicographic ordering and reorder p1, p2
gap> lexord := NCMonomialLeftLexicographicOrdering( A3 );;
gap> PatchGBNP( lexord );
LtNP patched.
GtNP patched.
gap> Lp1 := CleanNP( Lp1 );
[ [ [ 2, 3, 1 ], [ 1, 1, 2, 3 ] ], [ 8, 7 ] ]
gap> Lp2 := CleanNP( Lp2 );
[ [ [ 3, 1, 2 ], [ 3 ], [ 1, 2, 1 ], [ 1, 1 ] ], [ 9, 7, 6, 13 ] ]
gap> GtNPoly( Lp1, Lp2 );
false
gap> ## revert to degree lex order
gap> UnpatchGBNP();;
LtNP restored.
GtNP restored.
gap> Lp1 := CleanNP( Lp1 );
[ [ [ 1, 1, 2, 3 ], [ 2, 3, 1 ] ], [ 7, 8 ] ]
gap> Lp2 := CleanNP( Lp2 );
[ [ [ 3, 1, 2 ], [ 1, 2, 1 ], [ 1, 1 ], [ 3 ] ], [ 9, 6, 13, 7 ] ]
gap> GtNPoly( Lp1, Lp2 );
true

</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap1.html">[Previous Chapter]</a> <a href="chap3.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

Messung
C	H	Z	G
86	100	100	95

¤ Dauer der Verarbeitung: 0.12 Sekunden ¤

Wurzel

Suchen

PVS Prover

Isabelle Prover

Cephes Mathematical Library

Vienna Development Method

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.