Package borderbasis

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

See also: BB.Border