Difference between revisions of "Package borderbasis"

From ApCoCoAWiki
 
(14 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
This page describes the <code>borderbasis</code> package. The package contains various functions for computing with border bases of order ideals in a polynomial ring P=K[x_1,...,x_n] over a field K. We refer the book [M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2, Springer-Verlag, Berlin, 2005] for more details about border bases. For a complete list of functions, see also [[:Category:Package borderbasis]].
 
This page describes the <code>borderbasis</code> package. The package contains various functions for computing with border bases of order ideals in a polynomial ring P=K[x_1,...,x_n] over a field K. We refer the book [M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2, Springer-Verlag, Berlin, 2005] for more details about border bases. For a complete list of functions, see also [[:Category:Package borderbasis]].
  
 +
The Global Alias of the package is <code>BB</code>.
  
 +
== List of the main functions ==
  
−
== List of the main functions ==
+
[[IsOrderIdeal]]
 +
<pre>
 +
IsOrderIdeal(OO): checks whether OO is an order ideal.
 +
    input: OO a non-empty set of terms in K[x[1..N]]
 +
    output: boolean value for checking OO being an order ideal
 +
</pre>
 +
[[IndexO]]
 +
<pre>
 +
IndexO(P,T,OO): returns index of a term in K[x[1..N]]w.r.t an order ideal OO.
 +
    input: T a term in P= K[x[1..N]], OO an oder ideal in P
 +
    output: the index of T w.r.t. OO
 +
</pre>
 +
[[Border]]
 +
<pre>
 +
Border(OO): computes the border of an order ideal.
 +
    input: list of terms
 +
    output: list of terms in ascending order
 +
</pre>
 +
[[Box]]
 +
<pre>
 +
Box(P,D): computes the 'box' order ideal of type D=[D1,..,DN].
 +
    input: list of integers D of length NumIndets(P), P=K[x[1..N]]
 +
    output: list of terms (sorted w.r.t. current TO)
 +
</pre>
 +
[[BBasisForOI]]
 +
<pre>
 +
BBasisForOI(F,OO): computes the border basis of the ideal I=<F> with respect to the order ideal OO,
 +
          gives an error messages if no border basis exists, uses the O_sigma(I) border basis and the BB transformation.
 +
    input: list of poly F, list of terms OO
 +
    output: list of poly
 +
</pre>
 +
[[BorderDivAlg]]
 +
<pre>
 +
BorderDivAlg(P,F,OO,Prebasis): applies the Border Division Algorithm w.r.t. the order ideal OO and the border prebasis
 +
          Prebasis to the polynomial F and returns a record with fields
 +
          Quotients and Remainder where Remainder is the normal OO-remainder of F.
 +
    input: poly F, list of terms OO, list of poly Prebasis
 +
    output: record with two fields Quotients and Remainder
 +
</pre>
 +
[[BorderDivAlgForCoeffs]]
 +
<pre>
 +
BorderDivAlgForCoeffs(P,F,OO,Prebasis): applies BorderDivAlg to form
 +
          a list La in P such that F has a presentation of form
 +
          F=La[1]*OO[1]+...+La[Mu]*OO[Mu]+H, H in <Prebasis>.
 +
    input: poly F, list of terms OO, list of poly Prebasis   
 +
output: list of polys of length Mu=len(OO)
 +
</pre>
 +
[[BBRing]]
 +
<pre>
 +
BBRing(OO): creates the (standard) bb poly ring of OO.
 +
    input: list of terms OO in K[x[1..N]]
 +
    output: the ring K[c_ij] of OO
 +
</pre>
 +
[[GenMultMat]]
 +
<pre>
 +
GenMultMat(BBS,OO): computes the generic multiplication matrices with respect to the order ideal OO.
 +
    input: BBS the bb poly ring of OO, OO order ideal in K[x[1..N]]
 +
output: matrices of size Mu x Mu over the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[IthGenMultMat]]
 +
<pre>
 +
IthGenMultMat(BBS,OO,I): computes the generic multiplication matrix
 +
          for x[I] with respect to the order ideal OO.
 +
    input: I pos integer, OO order ideal in K[x[1..N]], BBS the bb poly ring of OO
 +
output: matrix of size Mu x Mu over the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[GenHomMultMat]]
 +
<pre>
 +
GenHomMultMat(BBS,OO): computes the generic homog. mult. matrices with respect to the order ideal OO.
 +
    input: BBS the bb poly ring of OO, OO order ideal in K[x[1..N]]
 +
    output: matrices of size Mu x Mu over the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[IthGenHomMultMat]]
 +
<pre>
 +
IthGenHomMultMat(BBS,OO,I): computes the generic homog. mult. matrix
 +
        for x[I] with respect to the order ideal OO.
 +
    input: I pos integer, OO order ideal in K[x[1..N]], BBS the bb poly ring of OO
 +
    output: matrix of size Mu x Mu over the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[GenDfMultMat]]
 +
<pre>
 +
GenDfMultMat(BBS,OO): computes the generic deg-filt mult. matrices with respect to the order ideal OO.
 +
    input: BBS the bb poly ring of OO, OO order ideal in K[x[1..N]]
 +
    output: matrices of size Mu x Mu over the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[IthGenDfMultMat]]
 +
<pre>
 +
IthGenDfMultMat(BBS,OO,I): computes the generic deg-filt mult. matrix
 +
        for x[I] with respect to the order ideal OO.
 +
    input: I pos integer, OO order ideal in K[x[1..N]], BBS the bb poly ring of OO
 +
    output: matrix of size Mu x Mu over the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[BBscheme]]
 +
<pre>
 +
BBscheme(BBS,OO): computes the defining equations of the border basis scheme
 +
        using the commutators of the multiplication matrices.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: an ideal in the ring BBS = K[c_{ij}]
 +
</pre>
 +
[[IdealOfBBScheme]]
 +
<pre>
 +
IdealOfBBScheme(BBS,OO): the same as BBscheme(BBS,OO).
 +
</pre>
 +
[[DfBBscheme]]
 +
<pre>
 +
DfBBscheme(BBS,OO): computes the defining equations of the deg-filt BB scheme
 +
        using the commutators of the multiplication matrices.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: an ideal in the ring BBS = K[c_{ij}]
 +
</pre>
 +
[[IdealOfDfBBscheme]]
 +
<pre>
 +
IdealOfDfBBscheme(BBS,OO): the same as DfBBscheme(BBS,OO).
 +
</pre>
 +
[[HomBBscheme]]
 +
<pre>
 +
HomBBscheme(BBS,OO): compute the defining equations of the homog. BB scheme
 +
          using the commutators of the generic homog mult matrices.
 +
    input: OO order ideal, BBS is the bb poly ring of OO
 +
    output: an ideal in the ring BBS = K[c_{ij}]
 +
</pre>
 +
[[IdealOfHomBBscheme]]
 +
<pre>
 +
IdealOfHomBBscheme(BBS,OO): the same as HomBBscheme(BBS,OO).
 +
</pre>
 +
[[RingOfFamily]]
 +
<pre>
 +
RingOfFamily(OO): forms the ring of universal bb family.
 +
    input: OO is an order ideal in K[x[1..N]]
 +
    output: the ring of univ bb family K[c_ij,x[1..N]]
 +
</pre>
 +
[[GenericBB]]
 +
<pre>
 +
GenericBB(UF,OO): computes the 'generic' border prebasis w.r.t. OO
 +
        i.e. the polys g_j = b_j - sum_i c_{ij} t_i.
 +
    input: OO is the order ideal in K[x[1..N]]";
 +
          UF=K[c_ij,x[1..N]] is the ring of universal bb family of OO
 +
    output: list of Poly in UF
 +
</pre>
 +
[[GenericHomBB]]
 +
<pre>
 +
GenericHomBB(UF,OO): computes the 'generic' homog. border basis w.r.t. OO
 +
    input: OO is the order ideal in K[x[1..N]]";
 +
          UF=K[c_ij,x[1..N]] is the ring of universal bb family of OO
 +
    output: list of Poly in UF
 +
</pre>
 +
[[MultMat]]
 +
<pre>
 +
MultMat(I,OO,BB): returns the multiplication matrix associated to the
 +
          border basis BB with respect to the I-th indet of the poly ring.
 +
    input: integer index I, list of terms OO, list of poly BB
 +
    output: matrix
 +
</pre>
 +
[[CoeffOfBB]]
 +
<pre>
 +
CoeffOfBB(BB,OO): returns the coefficient matrix of the border basis BB.
 +
    input: list of poly BB, list of terms OO
 +
    output: matrix
 +
</pre>
 +
[[NDneighbors]]
 +
<pre>
 +
NDneighbors(BBS,OO): computes the list of next-door neighbors w.r.t. OO.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: list of triples [i,j,k] s.t. b_i = x_k * b_j
 +
</pre>
 +
[[ARneighbors]]
 +
<pre>
 +
ARneighbors(BBS,OO): computes the list of across-the-rim neighbors w.r.t. OO.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: List of [i,j,k,l,m] s.t. x_k*b_i = x_l*b_j, b_i = x_l*t_m
 +
            and b_j = x_k*t_m for some t_m in OO (l>k)
 +
</pre>
 +
[[ASneighbors]]
 +
<pre>
 +
ASneighbors(BBS,OO): computes the list of across-the-street neighbors w.r.t. OO.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: List of quadruples [i,j,k,l] s.t. x_k*b_i = x_l*b_j
 +
</pre>
 +
[[LiftND]]
 +
<pre>
 +
LiftND(BBS,OO): computes the equations defining the border basis scheme
 +
          and coming from the lifting of next-door neighbors.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: list of poly in the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[LiftAR]]
 +
<pre>
 +
LiftAR(BBS,OO): computes the equations defining the border basis scheme
 +
          and coming from the lifting of across-the-rim neighbors.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: list of poly in the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[LiftAS]]
 +
<pre>
 +
LiftAS(BBS,OO): computes the equations defining the border basis scheme
 +
          and coming from the lifting of across-the-street neighbors.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: list of poly in the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[LiftHomND]]
 +
<pre>
 +
LiftHomND(BBS,OO): computes the equations defining the homog. BB scheme
 +
          and coming from the lifting of next-door neighbors.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: list of poly in the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[LiftHomAS]]
 +
<pre>
 +
LiftHomAS(BBS,OO): computes the equations defining the homog. BB scheme
 +
          and coming from the lifting of across-the-street neighbors.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: list of poly in the ring BBS=K[c_{ij}]
 +
</pre>
 +
[[NDgens]]
 +
<pre>
 +
NDgens(BBS,K,OO): computes the generators of the defining ideal of the border basis scheme
 +
  corresponding to the lifting of the K-th element of NDneighbors(BBS,OO).
 +
    input: K=index of a NDneighbor, OO order ideal, BBS bb poly ring
 +
    output: list of polynomials in BBS=K[c_{ij}]
 +
</pre>
 +
[[ARgens]]
 +
<pre>
 +
ARgens(BBS,K,OO): computes the generators of the defining ideal of the border basis scheme
 +
  corresponding to the lifting of the K-th element of ARneighbors(BBS,OO).
 +
    input: K=index of an ARneighbor, OO order ideal, BBS bb poly ring
 +
    output: list of polynomials in BBS=K[c_{ij}]
 +
</pre>
 +
[[ASgens]]
 +
<pre>
 +
ASgens(BBS,K,OO): computes the generators of the defining ideal of the border basis scheme
 +
  corresponding to the lifting of the K-th element of ASneighbors(BBS,OO).
 +
    input: K=index of a ASneighbor, OO order ideal, BBS bb poly ring
 +
    output: list of polynomials in BBS=K[c_{ij}]
 +
</pre>
 +
[[NatIdealOfBBS]]
 +
<pre>
 +
NatIdealOfBBS(BBS,OO): computes the defining ideal of border basis scheme of OO with natural generators.
 +
    input: OO is an order ideal, BBS is the bb poly ring of OO
 +
    output: A set of natural generators of I_BO
 +
</pre>
 +
[[HomNDgens]]
 +
<pre>
 +
HomNDgens(BBS,K,OO): computes the generators of the vanishing ideal of the homogeneous border basis scheme
 +
          corresp. to the lifting of the K-th element of NDneighbors(BBS,OO).
 +
    input: K=index of a NDneighbor, OO order ideal, BBS bb poly ring
 +
    output: list of polynomials in BBS=K[c_{ij}]
 +
</pre>
 +
[[HomASgens]]
 +
<pre>
 +
HomASgens(BBS,K,OO): computes the generators of the vanishing ideal of the
 +
          homogeneous border basis scheme corresp. to the lifting of
 +
          the K-th element of ASneighbors(BBS,OO).
 +
    input: K=index of a ASneighbor, OO order ideal, BBS bb poly ring
 +
    output: list of polynomials in BBS=K[c_{ij}]
 +
</pre>
 +
[[LiftHomND]]
 +
<pre>
 +
LiftHomND(BBS,OO): computes the equations defining the homog BBsch
 +
          and coming from the lifting of ND-neighbors (using Spoly).
 +
    input: OO order ideal, BBS bb poly ring
 +
    output: list of generators of I_BO^hom lifting of NDs
 +
</pre>
 +
[[LiftHomAS]]
 +
<pre>
 +
LiftHomAS(BBS,OO): computes the equations defining the homog BBsch
 +
          and coming from the lifting of AS-neighbors (using Spoly).
 +
    input: OO order ideal, BBS bb poly ring
 +
    output: list of generators of I_BO^hom lifting of ASs
 +
</pre>
 +
 
 +
== List of support functions ==
  
  
 +
<pre>
 +
LinPart(P,F): computes the homogeneous part of degree 1.
 +
    input: P = Poly ring, F = Poly or list of Poly
 +
    output: Poly or list of Poly
 +
</pre>
 +
<pre>
 +
RLF(P,F): RLF of a polynomial returns its linear form which vanishes at the origin, independently of the grading.
 +
        RLF of a list of poly or an ideal I returns the reduced GB of the ideal generatd by the RLF of the Gens of I.
 +
    input: P = Poly ring, F = Poly or list of Poly or ideal
 +
    output: Poly or list of Poly
 +
</pre>
 +
<pre>
 +
CoeffPoly(P,T,F,X): find the 'multivariate' coefficient of a term in a poly.
 +
    input: P = Poly ring, T term, F poly, X set of indets
 +
    output: polynomial coefficent of T in F such that no coefficient is in <X>
 +
</pre>
 +
<pre>
 +
DF(P,F): degree form of a polynomial F.
 +
    input: P = Poly ring, F poly
 +
    output: Poly
 +
</pre>
 +
<pre>
 +
Ccolumn(BBS, J): contructs the column (C[1,J],...,C[Mu,J])^{tr}.
 +
    input: BBS is the bb poly ring, J In 1..Nu
 +
    output: a (Mu x 1)-matrix of indets
 +
</pre>
 +
<pre>
 +
HomCcolumn(BBS,J,OO): contructs the 'homogeneous' column (D[1,J],...,D[Mu,J])^{tr}
 +
          where D[I,J]=C[I,J] if Deg(t_i)=Deg(b_j) and D[I,J]=0 otherwise.
 +
    input: BBS is the bb poly ring, J In 1..Nu, OO order ideal
 +
    output: a (Mu x 1)-matrix of indets
 +
</pre>
 +
<pre>
 +
IsListOfTerms(L): checks if a list is a list of terms.
 +
    input: non-empty LIST of POLY
 +
    output: TRUE if L is a list of terms, FALSE otherwise
 +
</pre>
 +
<pre>
 +
ArrDeg(BBS, OO, opt L): computes the triple [indet, arrow-degree, arrow] of the indeterminates in L.
 +
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
 +
    output: [indet, arrow-degree, arrow]
 +
</pre>
 +
<pre>
 +
TotArrDeg(BBS, OO, opt L): computes the triple [indet, Total arrow-degree, arrow] of the indeterminates in L.
 +
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
 +
    output: [indet, Total arrow-degree, arrow]
 +
</pre>
 +
<pre>
 +
NonNegTotArrDeg(BBS, OO, opt L): computes the indets with non-negative total-arrow-degree.
 +
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
 +
    output: list of indets";
 +
</pre>
 +
<pre>
 +
PositiveArrow(BBS, OO, opt L): computes the indets with positive total-arrow-degree.
 +
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
 +
    output: list of indets
 +
</pre>
 +
<pre>
 +
ZeroTotArrDeg(BBS, OO, opt L): computes the indets with zero total-arrow-degree.
 +
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
 +
    output: list of indets
 +
</pre>
 +
<pre>
 +
InteriorCij(BBS,OO): computes the indeterminates in BBS associated to the interior terms in OO
 +
    input: OO order ideal, BBS is the bb poly ring
 +
    output: list of interior indets
 +
</pre>
  
 
== Example for computations ==
 
== Example for computations ==
 +
 +
Let us apply several functions in the package <code>borderbasis</code> to an explicit example.
 +
 +
<pre>
 +
Use P :: = QQ[x,y];
 +
OO := [one(P), y, x, x*y, x^3];
 +
--
 +
--1. checks order ideals
 +
BB.IsOrderIdeal(OO);
 +
  false
 +
OO := [one(P), y, x, y^2];
 +
BB.IsOrderIdeal(OO);
 +
  true
 +
--
 +
--2. computes index of a term w.r.t. OO
 +
BB.IndexO(P, x^5*y^2, OO);
 +
  5
 +
--
 +
--3. computes "box" border
 +
BB.Box(P,[1,2]);
 +
  [1,  y,  x,  y^2,  x*y,  x*y^2]
 +
--
 +
--4. computes border
 +
BO := BB.Border(OO); BO;
 +
  [x*y,  x^2,  y^3,  x*y^2]
 +
--
 +
--5. computes the border basis of <F> w.r.t. OO
 +
F := [x*y -x, x^2+2*x, y^3-2*y+1];
 +
BB.BBasisForOI(F,OO);
 +
  [x*y -x,  x^2 +2*x,  y^3 -2*y +1,  x*y^2 -x]
 +
--
 +
--6. border division algorithm
 +
F := x^4+y^4;
 +
Prebasis := [x*y -x,  x^2 +2*x,  y^3 -2*y +1,  x*y^2 -x];
 +
BB.BorderDivAlg(P,F,OO,Prebasis);
 +
  record[Quotients := [0,  x^2 -2*x +4,  y,  0], Remainder := 2*y^2 -8*x -y]
 +
BB.BorderDivAlgForCoeffs(P,F,OO,Prebasis);
 +
  [0,  -1,  -8,  2]
 +
--
 +
--7. creates the bb poly ring
 +
BBS := BB.BBRing(OO);
 +
Use BBS;
 +
NumIndets(BBS);
 +
  16
 +
--
 +
--8. computes generic mult matrices
 +
GMM := BB.GenMultMat(BBS,OO); indent(GMM[1]);
 +
  matrix( /*RingWithID(9, "QQ[...]")*/
 +
          [[0, c[1,1], c[1,2], c[1,4]], 
 +
          [0, c[2,1], c[2,2], c[2,4]],
 +
          [1, c[3,1], c[3,2], c[3,4]],
 +
          [0, c[4,1], c[4,2], c[4,4]]]))
 +
BB.IthGenMultMat(BBS,OO,1); --the same mat
 +
--
 +
GHMM:=BB.GenHomMultMat(BBS,OO); indent(GHMM[1]);
 +
  matrix( /*RingWithID(9, "QQ[...]")*/
 +
          [[0, 0, 0, 0],
 +
          [0, 0, 0, 0],
 +
          [1, 0, 0, 0],
 +
          [0, c[4,1], c[4,2], 0]])
 +
BB.IthGenHomMultMat(BBS,OO,1); --the same mat
 +
--
 +
--9. computes the defining ideal of BBscheme
 +
IBO := BB.BBscheme(BBS,OO);
 +
IBO := BB.IdealOfBBScheme(BBS,OO);
 +
IBO := BB.NatIdealOfBBS(BBS,OO);
 +
Ge := Gens(IBO); len(Ge);
 +
  12
 +
--
 +
--10. creates the ring of universal bb family
 +
UF := BB.RingOfFamily(OO);
 +
--
 +
--11. computes the generic border prebasis
 +
GBB := BB.GenericBB(UF,OO); indent(GBB);
 +
  [
 +
    -c[4,1]*y^2 -c[3,1]*x -c[2,1]*y +x*y -c[1,1],
 +
    -c[4,2]*y^2 -c[3,2]*x +x^2 -c[2,2]*y -c[1,2],
 +
    -c[4,3]*y^2 +y^3 -c[3,3]*x -c[2,3]*y -c[1,3],
 +
    -c[4,4]*y^2 +x*y^2 -c[3,4]*x -c[2,4]*y -c[1,4]
 +
  ]
 +
--
 +
--12. computes the mult matrix assoc. to the border basis BB
 +
Use P;  BB := [x*y -x,  x^2 +2*x,  y^3 -2*y +1,  x*y^2 -x];
 +
BB.MultMat(1,OO,BB);
 +
  matrix(QQ,
 +
    [[0, 0, 0, 0, 0],
 +
      [0, 0, 0, 0, 0],
 +
      [1, 1, -2, 1, 1],
 +
      [0, 0, 0, 0, 0],
 +
      [0, 0, 0, 0, 0]])
 +
--
 +
--13. computes the coeff matrix of BB
 +
BB.CoeffOfBB(BB,OO);
 +
  matrix(QQ,
 +
    [[0, 0, 1, 0],
 +
      [0, 0, -2, 0],
 +
      [-1, 2, 0, -1],
 +
      [0, 0, 0, 0]]))
 +
--
 +
--14. Form ND, AR, AS neighbours
 +
Use BBS;
 +
BB.NDneighbors(BBS,OO);
 +
  [[4,  1,  2]]
 +
BB.ARneighbors(BBS,OO);
 +
  [[1,  2,  1,  2,  3],  [3,  4,  1,  2,  4]]
 +
BB.ASneighbors(BBS,OO);
 +
  [[1,  2,  1,  2],  [3,  4,  1,  2]]
 +
BB.LiftND(BBS,OO);
 +
  [-c[1,1]*c[3,1] -c[1,3]*c[4,1] +c[1,4],  -c[2,1]*c[3,1] -c[2,3]*c[4,1] -c[1,1] +c[2,4], 
 +
    -c[3,1]^2 -c[3,3]*c[4,1] +c[3,4],  -c[3,1]*c[4,1] -c[4,1]*c[4,3] -c[2,1] +c[4,4]]
 +
BB.LiftAR(BBS,OO);
 +
  [c[1,1]*c[2,1] +c[1,2]*c[3,1] -c[1,1]*c[3,2] +c[1,4]*c[4,1] -c[1,3]*c[4,2], 
 +
    c[2,1]^2 +c[2,2]*c[3,1] -c[2,1]*c[3,2] +c[2,4]*c[4,1] -c[2,3]*c[4,2] -c[1,2], 
 +
    c[2,1]*c[3,1] +c[3,4]*c[4,1] -c[3,3]*c[4,2] +c[1,1], 
 +
    c[2,1]*c[4,1] -c[3,2]*c[4,1] +c[3,1]*c[4,2] -c[4,2]*c[4,3] +c[4,1]*c[4,4] -c[2,2], 
 +
    c[1,1]*c[2,3] +c[1,2]*c[3,3] -c[1,1]*c[3,4] +c[1,4]*c[4,3] -c[1,3]*c[4,4], 
 +
    c[2,1]*c[2,3] +c[2,2]*c[3,3] -c[2,1]*c[3,4] +c[2,4]*c[4,3] -c[2,3]*c[4,4] -c[1,4], 
 +
    c[2,3]*c[3,1] +c[3,2]*c[3,3] -c[3,1]*c[3,4] +c[3,4]*c[4,3] -c[3,3]*c[4,4] +c[1,3], 
 +
    c[2,3]*c[4,1] -c[3,4]*c[4,1] +c[3,3]*c[4,2] -c[2,4]]
 +
BB.LiftAS(BBS,OO);
 +
  [c[1,1]*c[2,1] +c[1,2]*c[3,1] -c[1,1]*c[3,2] +c[1,4]*c[4,1] -c[1,3]*c[4,2], 
 +
    c[2,1]^2 +c[2,2]*c[3,1] -c[2,1]*c[3,2] +c[2,4]*c[4,1] -c[2,3]*c[4,2] -c[1,2], 
 +
    c[2,1]*c[3,1] +c[3,4]*c[4,1] -c[3,3]*c[4,2] +c[1,1], 
 +
    c[2,1]*c[4,1] -c[3,2]*c[4,1] +c[3,1]*c[4,2] -c[4,2]*c[4,3] +c[4,1]*c[4,4] -c[2,2], 
 +
    c[1,1]*c[2,3] +c[1,2]*c[3,3] -c[1,1]*c[3,4] +c[1,4]*c[4,3] -c[1,3]*c[4,4], 
 +
    c[2,1]*c[2,3] +c[2,2]*c[3,3] -c[2,1]*c[3,4] +c[2,4]*c[4,3] -c[2,3]*c[4,4] -c[1,4], 
 +
    c[2,3]*c[3,1] +c[3,2]*c[3,3] -c[3,1]*c[3,4] +c[3,4]*c[4,3] -c[3,3]*c[4,4] +c[1,3], 
 +
    c[2,3]*c[4,1] -c[3,4]*c[4,1] +c[3,3]*c[4,2] -c[2,4]]
 +
</pre>
 +
  
  
−
:''See also: [[/BB.Border/]]
 
 
[[Category:Package borderbasis]]
 
[[Category:Package borderbasis]]
 
[[Category:ApCoCoA Packages]]
 
[[Category:ApCoCoA Packages]]

Latest revision as of 00:54, 18 November 2022

This article is about a function from ApCoCoA-2. If you are looking for the ApCoCoA-1 version of it, see Category:ApCoCoA-1:Package borderbasis.

This page describes the borderbasis package. The package contains various functions for computing with border bases of order ideals in a polynomial ring P=K[x_1,...,x_n] over a field K. We refer the book [M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2, Springer-Verlag, Berlin, 2005] for more details about border bases. For a complete list of functions, see also Category:Package borderbasis.

The Global Alias of the package is BB.

List of the main functions

IsOrderIdeal 

IsOrderIdeal(OO): checks whether OO is an order ideal.
    input: OO a non-empty set of terms in K[x[1..N]]
    output: boolean value for checking OO being an order ideal

IndexO 

IndexO(P,T,OO): returns index of a term	in K[x[1..N]]w.r.t an order ideal OO.
    input: T a term in P= K[x[1..N]], OO an oder ideal in P
    output: the index of T w.r.t. OO

Border 

Border(OO): computes the border of an order ideal.
    input: list of terms
    output: list of terms in ascending order

Box 

Box(P,D): computes the 'box' order ideal of type D=[D1,..,DN].
    input: list of integers D of length NumIndets(P), P=K[x[1..N]]
    output: list of terms (sorted w.r.t. current TO)

BBasisForOI 

BBasisForOI(F,OO): computes the border basis of the ideal I=<F> with respect to the order ideal OO, 
          gives an error messages if no border basis exists, uses the O_sigma(I) border basis and the BB transformation.
    input: list of poly F, list of terms OO
    output: list of poly

BorderDivAlg 

BorderDivAlg(P,F,OO,Prebasis): applies the Border Division Algorithm w.r.t. the order ideal OO and the border prebasis
          Prebasis to the polynomial F and returns a record with fields 
          Quotients and Remainder where Remainder is the normal OO-remainder of F.
    input: poly F, list of terms OO, list of poly Prebasis
    output: record with two fields Quotients and Remainder

BorderDivAlgForCoeffs 

BorderDivAlgForCoeffs(P,F,OO,Prebasis): applies BorderDivAlg to form
          a list La in P such that F has a presentation of form
          F=La[1]*OO[1]+...+La[Mu]*OO[Mu]+H, H in <Prebasis>.
    input: poly F, list of terms OO, list of poly Prebasis    
	output: list of polys of length Mu=len(OO)

BBRing 

BBRing(OO): creates the (standard) bb poly ring of OO.
    input: list of terms OO in K[x[1..N]]
    output: the ring K[c_ij] of OO

GenMultMat 

GenMultMat(BBS,OO): computes the generic multiplication matrices with respect to the order ideal OO.
    input: BBS the bb poly ring of OO, OO order ideal in K[x[1..N]]
	output: matrices of size Mu x Mu over the ring BBS=K[c_{ij}]

IthGenMultMat 

IthGenMultMat(BBS,OO,I): computes the generic multiplication matrix
          for x[I] with respect to the order ideal OO.
    input: I pos integer, OO order ideal in K[x[1..N]], BBS the bb poly ring of OO
	output: matrix of size Mu x Mu over the ring BBS=K[c_{ij}]

GenHomMultMat 

GenHomMultMat(BBS,OO): computes the generic homog. mult. matrices with respect to the order ideal OO.
    input: BBS the bb poly ring of OO, OO order ideal in K[x[1..N]]
    output: matrices of size Mu x Mu over the ring BBS=K[c_{ij}]

IthGenHomMultMat 

IthGenHomMultMat(BBS,OO,I): computes the generic homog. mult. matrix
         for x[I] with respect to the order ideal OO.
    input: I pos integer, OO order ideal in K[x[1..N]], BBS the bb poly ring of OO
    output: matrix of size Mu x Mu over the ring BBS=K[c_{ij}]

GenDfMultMat 

GenDfMultMat(BBS,OO): computes the generic deg-filt mult. matrices with respect to the order ideal OO.
    input: BBS the bb poly ring of OO, OO order ideal in K[x[1..N]]
    output: matrices of size Mu x Mu over the ring BBS=K[c_{ij}]

IthGenDfMultMat 

IthGenDfMultMat(BBS,OO,I): computes the generic deg-filt mult. matrix
         for x[I] with respect to the order ideal OO.
    input: I pos integer, OO order ideal in K[x[1..N]], BBS the bb poly ring of OO
    output: matrix of size Mu x Mu over the ring BBS=K[c_{ij}]

BBscheme 

BBscheme(BBS,OO): computes the defining equations of the border basis scheme
         using the commutators of the multiplication matrices.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: an ideal in the ring BBS = K[c_{ij}]

IdealOfBBScheme 

IdealOfBBScheme(BBS,OO): the same as BBscheme(BBS,OO).

DfBBscheme 

DfBBscheme(BBS,OO): computes the defining equations of the deg-filt BB scheme
         using the commutators of the multiplication matrices.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: an ideal in the ring BBS = K[c_{ij}]

IdealOfDfBBscheme 

IdealOfDfBBscheme(BBS,OO): the same as DfBBscheme(BBS,OO).

HomBBscheme 

HomBBscheme(BBS,OO): compute the defining equations of the homog. BB scheme
          using the commutators of the generic homog mult matrices.
    input: OO order ideal, BBS is the bb poly ring of OO
    output: an ideal in the ring BBS = K[c_{ij}]

IdealOfHomBBscheme 

IdealOfHomBBscheme(BBS,OO): the same as HomBBscheme(BBS,OO).

RingOfFamily 

RingOfFamily(OO): forms the ring of universal bb family.
    input: OO is an order ideal in K[x[1..N]]
    output: the ring of univ bb family K[c_ij,x[1..N]]

GenericBB 

GenericBB(UF,OO): computes the 'generic' border prebasis w.r.t. OO
         i.e. the polys g_j = b_j - sum_i c_{ij} t_i.
    input: OO is the order ideal in K[x[1..N]]";
           UF=K[c_ij,x[1..N]] is the ring of universal bb family of OO
    output: list of Poly in UF

GenericHomBB 

GenericHomBB(UF,OO): computes the 'generic' homog. border basis w.r.t. OO
    input: OO is the order ideal in K[x[1..N]]";
           UF=K[c_ij,x[1..N]] is the ring of universal bb family of OO
    output: list of Poly in UF

MultMat 

MultMat(I,OO,BB): returns the multiplication matrix associated to the
          border basis BB with respect to the I-th indet of the poly ring.
    input: integer index I, list of terms OO, list of poly BB
    output: matrix

CoeffOfBB 

CoeffOfBB(BB,OO): returns the coefficient matrix of the border basis BB.
    input: list of poly BB, list of terms OO
    output: matrix

NDneighbors 

NDneighbors(BBS,OO): computes the list of next-door neighbors w.r.t. OO.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: list of triples [i,j,k] s.t. b_i = x_k * b_j

ARneighbors 

ARneighbors(BBS,OO): computes the list of across-the-rim neighbors w.r.t. OO.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: List of [i,j,k,l,m] s.t. x_k*b_i = x_l*b_j, b_i = x_l*t_m
            and b_j = x_k*t_m for some t_m in OO (l>k)

ASneighbors 

ASneighbors(BBS,OO): computes the list of across-the-street neighbors w.r.t. OO.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: List of quadruples [i,j,k,l] s.t. x_k*b_i = x_l*b_j

LiftND 

LiftND(BBS,OO): computes the equations defining the border basis scheme
           and coming from the lifting of next-door neighbors.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: list of poly in the ring BBS=K[c_{ij}]

LiftAR 

LiftAR(BBS,OO): computes the equations defining the border basis scheme
           and coming from the lifting of across-the-rim neighbors.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: list of poly in the ring BBS=K[c_{ij}]

LiftAS 

LiftAS(BBS,OO): computes the equations defining the border basis scheme
           and coming from the lifting of across-the-street neighbors.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: list of poly in the ring BBS=K[c_{ij}]

LiftHomND 

LiftHomND(BBS,OO): computes the equations defining the homog. BB scheme
           and coming from the lifting of next-door neighbors.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: list of poly in the ring BBS=K[c_{ij}]

LiftHomAS 

LiftHomAS(BBS,OO): computes the equations defining the homog. BB scheme
           and coming from the lifting of across-the-street neighbors.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: list of poly in the ring BBS=K[c_{ij}]

NDgens 

NDgens(BBS,K,OO): computes the generators of the defining ideal of the border basis scheme 
		   corresponding to the lifting of the K-th element of NDneighbors(BBS,OO).
    input: K=index of a NDneighbor, OO order ideal, BBS bb poly ring
    output: list of polynomials in BBS=K[c_{ij}]

ARgens 

ARgens(BBS,K,OO): computes the generators of the defining ideal of the border basis scheme 
		   corresponding to the lifting of the K-th element of ARneighbors(BBS,OO).
    input: K=index of an ARneighbor, OO order ideal, BBS bb poly ring
    output: list of polynomials in BBS=K[c_{ij}]

ASgens 

ASgens(BBS,K,OO): computes the generators of the defining ideal of the border basis scheme 
		  corresponding to the lifting of the K-th element of ASneighbors(BBS,OO).
    input: K=index of a ASneighbor, OO order ideal, BBS bb poly ring
    output: list of polynomials in BBS=K[c_{ij}]

NatIdealOfBBS 

NatIdealOfBBS(BBS,OO): computes the defining ideal of border basis scheme of OO with natural generators.
    input: OO is an order ideal, BBS is the bb poly ring of OO
    output: A set of natural generators of I_BO

HomNDgens 

HomNDgens(BBS,K,OO): computes the generators of the vanishing ideal of the homogeneous border basis scheme 
          corresp. to the lifting of the K-th element of NDneighbors(BBS,OO).
    input: K=index of a NDneighbor, OO order ideal, BBS bb poly ring
    output: list of polynomials in BBS=K[c_{ij}]

HomASgens 

HomASgens(BBS,K,OO): computes the generators of the vanishing ideal of the
           homogeneous border basis scheme corresp. to the lifting of
           the K-th element of ASneighbors(BBS,OO).
    input: K=index of a ASneighbor, OO order ideal, BBS bb poly ring
    output: list of polynomials in BBS=K[c_{ij}]

LiftHomND 

LiftHomND(BBS,OO): computes the equations defining the homog BBsch
           and coming from the lifting of ND-neighbors (using Spoly).
    input: OO order ideal, BBS bb poly ring
    output: list of generators of I_BO^hom lifting of NDs

LiftHomAS 

LiftHomAS(BBS,OO): computes the equations defining the homog BBsch
           and coming from the lifting of AS-neighbors (using Spoly).
    input: OO order ideal, BBS bb poly ring
    output: list of generators of I_BO^hom lifting of ASs

List of support functions

LinPart(P,F): computes the homogeneous part of degree 1.
    input: P = Poly ring, F = Poly or list of Poly
    output: Poly or list of Poly

RLF(P,F): RLF of a polynomial returns its linear form which vanishes at the origin, independently of the grading.
         RLF of a list of poly or an ideal I returns the reduced GB of the ideal generatd by the RLF of the Gens of I.
    input: P = Poly ring, F = Poly or list of Poly or ideal
    output: Poly or list of Poly

CoeffPoly(P,T,F,X): find the 'multivariate' coefficient of a term in a poly.
    input: P = Poly ring, T term, F poly, X set of indets
    output: polynomial coefficent of T in F such that no coefficient is in <X>

DF(P,F): degree form of a polynomial F.
    input: P = Poly ring, F poly
    output: Poly

Ccolumn(BBS, J): contructs the column (C[1,J],...,C[Mu,J])^{tr}.
    input: BBS is the bb poly ring, J In 1..Nu
    output: a (Mu x 1)-matrix of indets

HomCcolumn(BBS,J,OO): contructs the 'homogeneous' column (D[1,J],...,D[Mu,J])^{tr}
           where D[I,J]=C[I,J] if Deg(t_i)=Deg(b_j) and D[I,J]=0 otherwise.
    input: BBS is the bb poly ring, J In 1..Nu, OO order ideal
    output: a (Mu x 1)-matrix of indets

IsListOfTerms(L): checks if a list is a list of terms.
    input: non-empty LIST of POLY
    output: TRUE if L is a list of terms, FALSE otherwise

ArrDeg(BBS, OO, opt L): computes the triple [indet, arrow-degree, arrow] of the indeterminates in L.
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
    output: [indet, arrow-degree, arrow]

TotArrDeg(BBS, OO, opt L): computes the triple [indet, Total arrow-degree, arrow] of the indeterminates in L.
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
    output: [indet, Total arrow-degree, arrow]

NonNegTotArrDeg(BBS, OO, opt L): computes the indets with non-negative total-arrow-degree.
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
    output: list of indets";

PositiveArrow(BBS, OO, opt L): computes the indets with positive total-arrow-degree.
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
    output: list of indets

ZeroTotArrDeg(BBS, OO, opt L): computes the indets with zero total-arrow-degree.
    input: BBS is the bb poly ring, L list of indets of BBS, OO order ideal
    output: list of indets

InteriorCij(BBS,OO): computes the indeterminates in BBS associated to the interior terms in OO
    input: OO order ideal, BBS is the bb poly ring
    output: list of interior indets

Example for computations

Let us apply several functions in the package borderbasis to an explicit example. 

Use P :: = QQ[x,y];
OO := [one(P), y, x, x*y, x^3];
--
--1. checks order ideals
BB.IsOrderIdeal(OO);
   false
OO := [one(P), y, x, y^2];
BB.IsOrderIdeal(OO);
   true
--
--2. computes index of a term w.r.t. OO
BB.IndexO(P, x^5*y^2, OO);
   5
--
--3. computes "box" border
BB.Box(P,[1,2]);
   [1,  y,  x,  y^2,  x*y,  x*y^2]
--
--4. computes border
BO := BB.Border(OO); BO;
   [x*y,  x^2,  y^3,  x*y^2]
--
--5. computes the border basis of <F> w.r.t. OO
F := [x*y -x, x^2+2*x, y^3-2*y+1];
BB.BBasisForOI(F,OO);
   [x*y -x,  x^2 +2*x,  y^3 -2*y +1,  x*y^2 -x]
--
--6. border division algorithm
F := x^4+y^4;
Prebasis := [x*y -x,  x^2 +2*x,  y^3 -2*y +1,  x*y^2 -x];
BB.BorderDivAlg(P,F,OO,Prebasis);
   record[Quotients := [0,  x^2 -2*x +4,  y,  0], Remainder := 2*y^2 -8*x -y]
BB.BorderDivAlgForCoeffs(P,F,OO,Prebasis);
   [0,  -1,  -8,  2]
--
--7. creates the bb poly ring
BBS := BB.BBRing(OO); 
Use BBS;
NumIndets(BBS);
   16
--
--8. computes generic mult matrices
GMM := BB.GenMultMat(BBS,OO); indent(GMM[1]);
   matrix( /*RingWithID(9, "QQ[...]")*/
           [[0, c[1,1], c[1,2], c[1,4]],  
           [0, c[2,1], c[2,2], c[2,4]],
           [1, c[3,1], c[3,2], c[3,4]],
           [0, c[4,1], c[4,2], c[4,4]]]))
BB.IthGenMultMat(BBS,OO,1); --the same mat
--
GHMM:=BB.GenHomMultMat(BBS,OO); indent(GHMM[1]);
   matrix( /*RingWithID(9, "QQ[...]")*/
          [[0, 0, 0, 0],
          [0, 0, 0, 0],
          [1, 0, 0, 0],
          [0, c[4,1], c[4,2], 0]])
BB.IthGenHomMultMat(BBS,OO,1); --the same mat
--
--9. computes the defining ideal of BBscheme
IBO := BB.BBscheme(BBS,OO);
IBO := BB.IdealOfBBScheme(BBS,OO);
IBO := BB.NatIdealOfBBS(BBS,OO);
Ge := Gens(IBO); len(Ge);
   12
--
--10. creates the ring of universal bb family
UF := BB.RingOfFamily(OO); 
--
--11. computes the generic border prebasis
GBB := BB.GenericBB(UF,OO); indent(GBB);
   [
    -c[4,1]*y^2 -c[3,1]*x -c[2,1]*y +x*y -c[1,1],
    -c[4,2]*y^2 -c[3,2]*x +x^2 -c[2,2]*y -c[1,2],
    -c[4,3]*y^2 +y^3 -c[3,3]*x -c[2,3]*y -c[1,3],
    -c[4,4]*y^2 +x*y^2 -c[3,4]*x -c[2,4]*y -c[1,4]
   ]
--
--12. computes the mult matrix assoc. to the border basis BB
Use P;  BB := [x*y -x,  x^2 +2*x,  y^3 -2*y +1,  x*y^2 -x];
BB.MultMat(1,OO,BB);
   matrix(QQ,
     [[0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0],
      [1, 1, -2, 1, 1],
      [0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0]])
--
--13. computes the coeff matrix of BB
BB.CoeffOfBB(BB,OO);
   matrix(QQ,
     [[0, 0, 1, 0],
      [0, 0, -2, 0],
      [-1, 2, 0, -1],
      [0, 0, 0, 0]]))
--
--14. Form ND, AR, AS neighbours
Use BBS;
BB.NDneighbors(BBS,OO);
   [[4,  1,  2]]
BB.ARneighbors(BBS,OO);
   [[1,  2,  1,  2,  3],  [3,  4,  1,  2,  4]]
BB.ASneighbors(BBS,OO);
   [[1,  2,  1,  2],  [3,  4,  1,  2]]
BB.LiftND(BBS,OO);
   [-c[1,1]*c[3,1] -c[1,3]*c[4,1] +c[1,4],  -c[2,1]*c[3,1] -c[2,3]*c[4,1] -c[1,1] +c[2,4],  
    -c[3,1]^2 -c[3,3]*c[4,1] +c[3,4],  -c[3,1]*c[4,1] -c[4,1]*c[4,3] -c[2,1] +c[4,4]]
BB.LiftAR(BBS,OO);
   [c[1,1]*c[2,1] +c[1,2]*c[3,1] -c[1,1]*c[3,2] +c[1,4]*c[4,1] -c[1,3]*c[4,2],  
    c[2,1]^2 +c[2,2]*c[3,1] -c[2,1]*c[3,2] +c[2,4]*c[4,1] -c[2,3]*c[4,2] -c[1,2],  
    c[2,1]*c[3,1] +c[3,4]*c[4,1] -c[3,3]*c[4,2] +c[1,1],  
    c[2,1]*c[4,1] -c[3,2]*c[4,1] +c[3,1]*c[4,2] -c[4,2]*c[4,3] +c[4,1]*c[4,4] -c[2,2],  
    c[1,1]*c[2,3] +c[1,2]*c[3,3] -c[1,1]*c[3,4] +c[1,4]*c[4,3] -c[1,3]*c[4,4],  
    c[2,1]*c[2,3] +c[2,2]*c[3,3] -c[2,1]*c[3,4] +c[2,4]*c[4,3] -c[2,3]*c[4,4] -c[1,4],  
    c[2,3]*c[3,1] +c[3,2]*c[3,3] -c[3,1]*c[3,4] +c[3,4]*c[4,3] -c[3,3]*c[4,4] +c[1,3],  
    c[2,3]*c[4,1] -c[3,4]*c[4,1] +c[3,3]*c[4,2] -c[2,4]]
BB.LiftAS(BBS,OO);
   [c[1,1]*c[2,1] +c[1,2]*c[3,1] -c[1,1]*c[3,2] +c[1,4]*c[4,1] -c[1,3]*c[4,2],  
    c[2,1]^2 +c[2,2]*c[3,1] -c[2,1]*c[3,2] +c[2,4]*c[4,1] -c[2,3]*c[4,2] -c[1,2],  
    c[2,1]*c[3,1] +c[3,4]*c[4,1] -c[3,3]*c[4,2] +c[1,1],  
    c[2,1]*c[4,1] -c[3,2]*c[4,1] +c[3,1]*c[4,2] -c[4,2]*c[4,3] +c[4,1]*c[4,4] -c[2,2],  
    c[1,1]*c[2,3] +c[1,2]*c[3,3] -c[1,1]*c[3,4] +c[1,4]*c[4,3] -c[1,3]*c[4,4],  
    c[2,1]*c[2,3] +c[2,2]*c[3,3] -c[2,1]*c[3,4] +c[2,4]*c[4,3] -c[2,3]*c[4,4] -c[1,4],  
    c[2,3]*c[3,1] +c[3,2]*c[3,3] -c[3,1]*c[3,4] +c[3,4]*c[4,3] -c[3,3]*c[4,4] +c[1,3],  
    c[2,3]*c[4,1] -c[3,4]*c[4,1] +c[3,3]*c[4,2] -c[2,4]]
Retrieved from "http://apcocoa.uni-passau.de/wiki/index.php?title=Package_borderbasis&oldid=16418"