Weighted homogeneous elements of free algebras, in letterplace implementation¶
AUTHOR:
Simon King (2011-03-23): Trac ticket trac ticket #7797
-
class
sage.algebras.letterplace.free_algebra_element_letterplace.FreeAlgebraElement_letterplace¶ Bases:
sage.structure.element.AlgebraElementWeighted homogeneous elements of a free associative unital algebra (letterplace implementation)
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: x+y x + y sage: x*y !=y*x True sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F sage: (y^3).reduce(I) y*y*y sage: (y^3).normal_form(I) y*y*z - y*z*y + y*z*z
Here is an example with nontrivial degree weights:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: I = F*[x*y-y*x, x^2+2*y*z, (x*y)^2-z^2]*F sage: x.degree() 2 sage: y.degree() 1 sage: z.degree() 3 sage: (x*y)^3 x*y*x*y*x*y sage: ((x*y)^3).normal_form(I) z*z*y*x sage: ((x*y)^3).degree() 9
-
degree()¶ Return the degree of this element.
NOTE:
Generators may have a positive integral degree weight. All elements must be weighted homogeneous.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((x+y+z)^3).degree() 3 sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((x*y+z)^3).degree() 9
-
lc()¶ The leading coefficient of this free algebra element, as element of the base ring.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((2*x+3*y-4*z)^2*(5*y+6*z)).lc() 20 sage: ((2*x+3*y-4*z)^2*(5*y+6*z)).lc().parent() is F.base() True sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((2*x*y+z)^2).lc() 4
-
letterplace_polynomial()¶ Return the commutative polynomial that is used internally to represent this free algebra element.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((x+y-z)^2).letterplace_polynomial() x*x_1 + x*y_1 - x*z_1 + y*x_1 + y*y_1 - y*z_1 - z*x_1 - z*y_1 + z*z_1
If degree weights are used, the letterplace polynomial is homogenized by slack variables:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((x*y+z)^2).letterplace_polynomial() x*x__1*y_2*x_3*x__4*y_5 + x*x__1*y_2*z_3*x__4*x__5 + z*x__1*x__2*x_3*x__4*y_5 + z*x__1*x__2*z_3*x__4*x__5
-
lm()¶ The leading monomial of this free algebra element.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((2*x+3*y-4*z)^2*(5*y+6*z)).lm() x*x*y sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((2*x*y+z)^2).lm() x*y*x*y
-
lm_divides(p)¶ Tell whether or not the leading monomial of self divides the leading monomial of another element.
NOTE:
A free algebra element \(p\) divides another one \(q\) if there are free algebra elements \(s\) and \(t\) such that \(spt = q\).
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((2*x*y+z)^2*z).lm() x*y*x*y*z sage: (y*x*y-y^4).lm() y*x*y sage: (y*x*y-y^4).lm_divides((2*x*y+z)^2*z) True
-
lt()¶ The leading term (monomial times coefficient) of this free algebra element.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: ((2*x+3*y-4*z)^2*(5*y+6*z)).lt() 20*x*x*y sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[2,1,3]) sage: ((2*x*y+z)^2).lt() 4*x*y*x*y
-
normal_form(I)¶ Return the normal form of this element with respect to a twosided weighted homogeneous ideal.
INPUT:
A twosided homogeneous ideal \(I\) of the parent \(F\) of this element, \(x\).
OUTPUT:
The normal form of \(x\) wrt. \(I\).
NOTE:
The normal form is computed by reduction with respect to a Groebnerbasis of \(I\) with degree bound \(deg(x)\).
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F sage: (x^5).normal_form(I) -y*z*z*z*x - y*z*z*z*y - y*z*z*z*z
We verify two basic properties of normal forms: The difference of an element and its normal form is contained in the ideal, and if two elements of the free algebra differ by an element of the ideal then they have the same normal form:
sage: x^5 - (x^5).normal_form(I) in I True sage: (x^5+x*I.0*y*z-3*z^2*I.1*y).normal_form(I) == (x^5).normal_form(I) True
Here is an example with non-trivial degree weights:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[1,2,3]) sage: I = F*[x*y-y*x+z, y^2+2*x*z, (x*y)^2-z^2]*F sage: ((x*y)^3).normal_form(I) z*z*y*x - z*z*z sage: (x*y)^3-((x*y)^3).normal_form(I) in I True sage: ((x*y)^3+2*z*I.0*z+y*I.1*z-x*I.2*y).normal_form(I) == ((x*y)^3).normal_form(I) True
-
reduce(G)¶ Reduce this element by a list of elements or by a twosided weighted homogeneous ideal.
INPUT:
Either a list or tuple of weighted homogeneous elements of the free algebra, or an ideal of the free algebra, or an ideal in the commutative polynomial ring that is currently used to implement the multiplication in the free algebra.
OUTPUT:
The twosided reduction of this element by the argument.
Note
This may not be the normal form of this element, unless the argument is a twosided Groebner basis up to the degree of this element.
EXAMPLES:
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace') sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F sage: p = y^2*z*y^2+y*z*y*z*y
We compute the letterplace version of the Groebner basis of \(I\) with degree bound 4:
sage: G = F._reductor_(I.groebner_basis(4).gens(),4) sage: G.ring() is F.current_ring() True
Since the element \(p\) is of degree 5, it is no surprise that its reductions with respect to the original generators of \(I\) (of degree 2), or with respect to \(G\) (Groebner basis with degree bound 4), or with respect to the Groebner basis with degree bound 5 (which yields its normal form) are pairwise different:
sage: p.reduce(I) y*y*z*y*y + y*z*y*z*y sage: p.reduce(G) y*y*z*z*y + y*z*y*z*y - y*z*z*y*y + y*z*z*z*y sage: p.normal_form(I) y*y*z*z*z + y*z*y*z*z - y*z*z*y*z + y*z*z*z*z sage: p.reduce(I) != p.reduce(G) != p.normal_form(I) != p.reduce(I) True
-
-
sage.algebras.letterplace.free_algebra_element_letterplace.poly_reduce(ring=None, interruptible=True, attributes=None, *args)¶ This function is an automatically generated C wrapper around the Singular function ‘NF’.
This wrapper takes care of converting Sage datatypes to Singular datatypes and vice versa. In addition to whatever parameters the underlying Singular function accepts when called, this function also accepts the following keyword parameters:
INPUT:
args– a list of argumentsring– a multivariate polynomial ringinterruptible– ifTruepressing Ctrl-C during the execution of this function will interrupt the computation (default:True)attributes– a dictionary of optional Singular attributes assigned to Singular objects (default:None)
If
ringis not specified, it is guessed from the given arguments. If this is not possible, then a dummy ring, univariate polynomial ring overQQ, is used.EXAMPLES:
sage: groebner = sage.libs.singular.function_factory.ff.groebner sage: P.<x, y> = PolynomialRing(QQ) sage: I = P.ideal(x^2-y, y+x) sage: groebner(I) [x + y, y^2 - y] sage: triangL = sage.libs.singular.function_factory.ff.triang__lib.triangL sage: P.<x1, x2> = PolynomialRing(QQ, order='lex') sage: f1 = 1/2*((x1^2 + 2*x1 - 4)*x2^2 + 2*(x1^2 + x1)*x2 + x1^2) sage: f2 = 1/2*((x1^2 + 2*x1 + 1)*x2^2 + 2*(x1^2 + x1)*x2 - 4*x1^2) sage: I = Ideal(Ideal(f1,f2).groebner_basis()[::-1]) sage: triangL(I, attributes={I:{'isSB':1}}) [[x2^4 + 4*x2^3 - 6*x2^2 - 20*x2 + 5, 8*x1 - x2^3 + x2^2 + 13*x2 - 5], [x2, x1^2], [x2, x1^2], [x2, x1^2]]
The Singular documentation for ‘NF’ is given below.
5.1.127 reduce -------------- `*Syntax:*' `reduce (' poly_expression`,' ideal_expression `)' `reduce (' poly_expression`,' ideal_expression`,' int_expression `)' `reduce (' poly_expression`,' poly_expression`,' ideal_expression `)' `reduce (' vector_expression`,' ideal_expression `)' `reduce (' vector_expression`,' ideal_expression`,' int_expression `)' `reduce (' vector_expression`,' module_expression `)' `reduce (' vector_expression`,' module_expression`,' int_expression `)' `reduce (' vector_expression`,' poly_expression`,' module_expression `)' `reduce (' ideal_expression`,' ideal_expression `)' `reduce (' ideal_expression`,' ideal_expression`,' int_expression `)' `reduce (' ideal_expression`,' matrix_expression`,' ideal_expression `)' `reduce (' module_expression`,' ideal_expression `)' `reduce (' module_expression`,' ideal_expression`,' int_expression `)' `reduce (' module_expression`,' module_expression `)' `reduce (' module_expression`,' module_expression`,' int_expression `)' `reduce (' module_expression`,' matrix_expression`,' module_expression `)' `reduce (' poly/vector/ideal/module`,' ideal/module`,' int`,' intvec `)' `reduce (' ideal`,' matrix`,' ideal`,' int `)' `reduce (' poly`,' poly`,' ideal`,' int `)' `reduce (' poly`,' poly`,' ideal`,' int`,' intvec `)' `*Type:*' the type of the first argument `*Purpose:*' reduces a polynomial, vector, ideal or module to its normal form with respect to an ideal or module represented by a standard basis. Returns 0 if and only if the polynomial (resp. vector, ideal, module) is an element (resp. subideal, submodule) of the ideal (resp. module). The result may have no meaning if the second argument is not a standard basis. The third (optional) argument of type int modifies the behavior: * 0 default * 1 consider only the leading term and do no tail reduction. * 2 tail reduction:n the local/mixed ordering case: reduce also with bad ecart * 4 reduce without division, return possibly a non-zero constant multiple of the remainder If a second argument `u' of type poly or matrix is given, the first argument `p' is replaced by `p/u'. This works only for zero dimensional ideals (resp. modules) in the third argument and gives, even in a local ring, a reduced normal form which is the projection to the quotient by the ideal (resp. module). One may give a degree bound in the fourth argument with respect to a weight vector in the fifth argument in order have a finite computation. If some of the weights are zero, the procedure may not terminate! `*Note_*' The commands `reduce' and `NF' are synonymous. `*Example:*' ring r1 = 0,(z,y,x),ds; poly s1=2x5y+7x2y4+3x2yz3; poly s2=1x2y2z2+3z8; poly s3=4xy5+2x2y2z3+11x10; ideal i=s1,s2,s3; ideal j=std(i); reduce(3z3yx2+7y4x2+yx5+z12y2x2,j); ==> -yx5+2401/81y14x2+2744/81y11x5+392/27y8x8+224/81y5x11+16/81y2x14 reduce(3z3yx2+7y4x2+yx5+z12y2x2,j,1); ==> -yx5+z12y2x2 // 4 arguments: ring rs=0,x,ds; // normalform of 1/(1+x) w.r.t. (x3) up to degree 5 reduce(poly(1),1+x,ideal(x3),5); ==> // ** _ is no standard basis ==> 1-x+x2 * Menu: See * division:: * ideal:: * module:: * poly operations:: * std:: * vector::
-
sage.algebras.letterplace.free_algebra_element_letterplace.singular_system(ring=None, interruptible=True, attributes=None, *args)¶ This function is an automatically generated C wrapper around the Singular function ‘system’.
This wrapper takes care of converting Sage datatypes to Singular datatypes and vice versa. In addition to whatever parameters the underlying Singular function accepts when called, this function also accepts the following keyword parameters:
INPUT:
args– a list of argumentsring– a multivariate polynomial ringinterruptible– ifTruepressing Ctrl-C during the execution of this function will interrupt the computation (default:True)attributes– a dictionary of optional Singular attributes assigned to Singular objects (default:None)
If
ringis not specified, it is guessed from the given arguments. If this is not possible, then a dummy ring, univariate polynomial ring overQQ, is used.EXAMPLES:
sage: groebner = sage.libs.singular.function_factory.ff.groebner sage: P.<x, y> = PolynomialRing(QQ) sage: I = P.ideal(x^2-y, y+x) sage: groebner(I) [x + y, y^2 - y] sage: triangL = sage.libs.singular.function_factory.ff.triang__lib.triangL sage: P.<x1, x2> = PolynomialRing(QQ, order='lex') sage: f1 = 1/2*((x1^2 + 2*x1 - 4)*x2^2 + 2*(x1^2 + x1)*x2 + x1^2) sage: f2 = 1/2*((x1^2 + 2*x1 + 1)*x2^2 + 2*(x1^2 + x1)*x2 - 4*x1^2) sage: I = Ideal(Ideal(f1,f2).groebner_basis()[::-1]) sage: triangL(I, attributes={I:{'isSB':1}}) [[x2^4 + 4*x2^3 - 6*x2^2 - 20*x2 + 5, 8*x1 - x2^3 + x2^2 + 13*x2 - 5], [x2, x1^2], [x2, x1^2], [x2, x1^2]]
The Singular documentation for ‘system’ is given below.
5.1.151 system -------------- `*Syntax:*' `system (' string_expression `)' `system (' string_expression`,' expression `)' `*Type:*' depends on the desired function, may be none `*Purpose:*' interface to internal data and the operating system. The string_expression determines the command to execute. Some commands require an additional argument (second form) where the type of the argument depends on the command. See below for a list of all possible commands. `*Note_*' Not all functions work on every platform. `*Functions:*' `system("alarm",' int `)' abort the Singular process after computing for that many seconds (system+user cpu time). `system("absFact",' poly `)' absolute factorization of the polynomial (from a polynomial ring over a transzedental extension) Returns a list of the ideal of the factors, intvec of multiplicities, ideal of minimal polynomials and the bumber of factors. `system("blackbox")' list all blackbox data types. `system("browsers");' returns a string about available help browsers. *Note The online help system::. `system("bracket",' poly, poly `)' returns the Lie bracket [p,q]. `system("btest",' poly, i2 `)' internal for shift algebra (with i2 variables): last block of the poly `system("complexNearZero",' number_expression `)' checks for a small value for floating point numbers `system("contributors")' returns names of people who contributed to the SINGULAR kernel as string. `system("cpu")' returns the number of cpus as int (for creating multiple threads/processes). (see `system("--cpus")'). `system("denom_list")' returns the list of denominators (number) which occured in the latest std computationi(s). Is reset to the empty list at ring changes or by this system call. `system("eigenvals",' matrix `)' returns the list of the eigenvalues of the matrix (as ideal, intvec). (see `system("hessenberg")'). `system("env",' ring `)' returns the enveloping algebra (i.e. R tensor R^opp) See `system("opp")'. `system("executable",' string `)' returns the path of the command given as argument or the empty string (for: not found) See `system("Singular")'. See `system("getenv","PATH")'. `system("freegb",' ideal, i2, i3 `)' returns the standrda basis in the shift algebra i(with i3 variables) up to degree i2. See `system("opp")'. `system("getenv",' string_expression`)' returns the value of the shell environment variable given as the second argument. The return type is string. `system("getPrecDigits")' returns the precision for floating point numbers `system("gmsnf",' ideal, ideal, matrix,int, int `)' Gauss-Manin system: for gmspoly.lib, gmssing.lib `system("HC")' returns the degree of the "highest corner" from the last std computation (or 0). `system("hessenberg",' matrix `)' returns the Hessenberg matrix (via QR algorithm). `system("install",' s1, s2, p3, i4 `)' install a new method p3 for s2 for the newstruct type s1. s2 must be a reserved operator with i4 operands (i4 may be 1,2,3; use 4 for more than 3 or a varying number of arguments) See *Note Commands for user defined types::. `system("LLL",' B `)' B must be a matrix or an intmat. Interface to NTLs LLL (Exact Arithmetic Variant over ZZ). Returns the same type as the input. B is an m x n matrix, viewed as m rows of n-vectors. m may be less than, equal to, or greater than n, and the rows need not be linearly independent. B is transformed into an LLL-reduced basis. The first m-rank(B) rows of B are zero. More specifically, elementary row transformations are performed on B so that the non-zero rows of new-B form an LLL-reduced basis for the lattice spanned by the rows of old-B. `system("nblocks")' or `system("nblocks",' ring_name `)' returns the number of blocks of the given ring, or of the current basering, if no second argument is given. The return type is int. `system("nc_hilb",' ideal, int, [,...] `)' internal support for ncHilb.lib, return nothing `system("neworder",' ideal `)' string of the ring variables in an heurically good order for `char_series' `system("newstruct")' list all newstruct data types. `system("opp",' ring `)' returns the opposite ring. `system("oppose",' ring R, poly p `)' returns the opposite polynomial of p from R. `system("pcvLAddL",' list, list `)' `system("pcvPMulL",' poly, list `)' `system("pcvMinDeg",' poly `)' `system("pcvP2CV",' list, int, int `)' `system("pcvCV2P",' list, int, int `)' `system("pcvDim",' int, int `)' `system("pcvBasis",' int, int `)' internal for mondromy.lib `system("pid")' returns the process number as int (for creating unique names). `system("random")' or `system("random",' int `)' returns or sets the seed of the random generator. `system("reduce_bound",' poly, ideal, int `)' or `system("reduce_bound",' ideal, ideal, int `)' or `system("reduce_bound",' vector, module, int `)' or `system("reduce_bound",' module, module, int `)' returns the normalform of the first argument wrt. the second up to the given degree bound (wrt. total degree) `system("reserve",' int `)' reserve a port and listen with the given backlog. (see `system("reservedLink")'). `system("reservedLink")' accept a connect at the reserved port and return a (write-only) link to it. (see `system("reserve")'). `system("semaphore",' string, int `)' operations for semaphores: string may be `"init"', `"exists"', `"acquire"', `"try_acquire"', `"release"', `"get_value"', and int is the number of the semaphore. Returns -2 for wrong command, -1 for error or the result of the command. `system("semic",' list, list `)' or `system("semic",' list, list, int `)' computes from list of spectrum numbers and list of spectrum numbers the semicontinuity index (qh, if 3rd argument is 1). `system("setenv",'string_expression, string_expression`)' sets the shell environment variable given as the second argument to the value given as the third argument. Returns the third argument. Might not be available on all platforms. `system("sh"', string_expression `)' shell escape, returns the return code of the shell as int. The string is sent literally to the shell. `system("shrinktest",' poly, i2 `)' internal for shift algebra (with i2 variables): shrink the poly `system("Singular")' returns the absolute (path) name of the running SINGULAR as string. `system("SingularLib")' returns the colon seperated library search path name as string. `system("spadd",' list, list `)' or `system("spadd",' list, list, int `)' computes from list of spectrum numbers and list of spectrum numbers the sum of the lists. `system("spectrum",' poly `)' or `system("spectrum",' poly, int `)' `system("spmul",' list, int `)' or `system("spmul",' list, list, int `)' computes from list of spectrum numbers the multiple of it. `system("std_syz",' module, int `)' compute a partial groebner base of a module, stopp after the given column `system("stest",' poly, i2, i3, i4 `)' internal for shift algebra (with i4 variables): shift the poly by i2, up to degree i3 `system("tensorModuleMult",' int, module `)' internal for sheafcoh.lib (see id_TensorModuleMult) `system("twostd",' ideal `)' returns the two-sided standard basis of the two-sided ideal. `system("uname")' returns a string identifying the architecture for which SINGULAR was compiled. `system("version")' returns the version number of SINGULAR as int. (Version a-b-c-d returns a*10000+b*1000+c*100+d) `system("with")' without an argument: returns a string describing the current version of SINGULAR, its build options, the used path names and other configurations with a string argument: test for that feature and return an int. `system("--cpus")' returns the number of available cpu cores as int (for using multiple cores). (see `system("cpu")'). `system("'-`")' prints the values of all options. `system("'-long_option_name`")' returns the value of the (command-line) option long_option_name. The type of the returned value is either string or int. *Note Command line options::, for more info. `system("'-long_option_name`",' expression`)' sets the value of the (command-line) option long_option_name to the value given by the expression. Type of the expression must be string, or int. *Note Command line options::, for more info. Among others, this can be used for setting the seed of the random number generator, the used help browser, the minimal display time, or the timer resolution. `*Example:*' // a listing of the current directory: system("sh","ls"); // execute a shell, return to SINGULAR with exit: system("sh","sh"); string unique_name="/tmp/xx"+string(system("pid")); unique_name; ==> /tmp/xx4711 system("uname") ==> ix86-Linux system("getenv","PATH"); ==> /bin:/usr/bin:/usr/local/bin system("Singular"); ==> /usr/local/bin/Singular // report value of all options system("--"); ==> // --batch 0 ==> // --execute ==> // --sdb 0 ==> // --echo 1 ==> // --profile 0 ==> // --quiet 1 ==> // --sort 0 ==> // --random 12345678 ==> // --no-tty 1 ==> // --user-option ==> // --allow-net 0 ==> // --browser ==> // --cntrlc ==> // --emacs 0 ==> // --no-stdlib 0 ==> // --no-rc 1 ==> // --no-warn 0 ==> // --no-out 0 ==> // --no-shell 0 ==> // --min-time "0.5" ==> // --cpus 4 ==> // --threads 4 ==> // --MPport ==> // --MPhost ==> // --link ==> // --ticks-per-sec 1 // set minimal display time to 0.02 seconds system("--min-time", "0.02"); // set timer resolution to 0.01 seconds system("--ticks-per-sec", 100); // re-seed random number generator system("--random", 12345678); // allow your web browser to access HTML pages from the net system("--allow-net", 1); // and set help browser to firefox system("--browser", "firefox"); ==> // ** Could not get 'DataDir'. ==> // ** Either set environment variable 'SINGULAR_DATA_DIR' to 'DataDir', ==> // ** or make sure that 'DataDir' is at "/home/hannes/singular/doc/../Sin\ gular/../share/" ==> // ** Could not get 'IdxFile'. ==> // ** Either set environment variable 'SINGULAR_IDX_FILE' to 'IdxFile', ==> // ** Could not get 'DataDir'. ==> // ** Either set environment variable 'SINGULAR_DATA_DIR' to 'DataDir', ==> // ** or make sure that 'DataDir' is at "/home/hannes/singular/doc/../Sin\ gular/../share/" ==> // ** or make sure that 'IdxFile' is at "%D/singular/singular.idx" ==> // ** resource `x` not found ==> // ** Setting help browser to 'dummy'.