#7797: Full interface to letterplace from singular
---------------------------+------------------------------------------------
Reporter: burcin | Owner: burcin
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: algebra | Keywords: singular, free algebra,
letterplace
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King, Michael Brickenstein,
Burcin Erocal
Merged: | Dependencies: #11068, #11268
---------------------------+------------------------------------------------
Changes (by SimonKing):
* keywords: singular => singular, free algebra, letterplace
Old description:
> The new aim of this ticket is to add an interface to the
> [http://www.singular.uni-kl.de/Manual/latest/sing_427.htm#SEC480
> letterplace] component of Singular, namely providing
>
> * A new implementation of free algebras with fast arithmetic.
> * Degree-wise Gröbner basis computation for twosided homogeneous ideals
> of free algebras.
> * Normal form computation with respect to such ideals.
>
> and in addition
>
> * One- and twosided ideals of noncommutative rings.
> * Quotient rings of such ideals
>
> (Note that the original purpose was merely to compute Groebner bases up
> to a degree bound of two-sided ideals of free algebras, but without
> normal form computation etc.)
>
> Examples are below, in the comments.
>
> Apply trac7797-full_letterplace_wrapper_rel11068.patch
>
> Depends on #11068 #11268
New description:
The new aim of this ticket is to add an interface to the
[http://www.singular.uni-kl.de/Manual/latest/sing_427.htm#SEC480
letterplace] component of Singular, namely providing
* A new implementation of free algebras with fast arithmetic.
* Degree-wise Gröbner basis computation for twosided homogeneous ideals
of free algebras.
* Normal form computation with respect to such ideals.
and in addition
* One- and twosided ideals of noncommutative rings.
* Quotient rings of such ideals
(Note that the original purpose was merely to compute Groebner bases up to
a degree bound of two-sided ideals of free algebras, but without normal
form computation etc.)
Examples are below, in the comments.
Apply
[attachment:trac7797-full_letterplace_wrapper_rel11068.patch]
[attachment:trac7797-letterplace_degree_weights.patch]
Depends on #11068 #11268
--
Comment:
Meanwhile I implemented two other features:
'''Uniqueness of parents'''
We had
{{{
sage: F.<x,y,z> = FreeAlgebra(QQ, 3)
sage: loads(dumps(F)) is F
False
}}}
I rewrote the `FreeAlgebra` constructor using `UniqueFactory`, so that the
answer above becomes `True`.
'''Degree weights'''
The letterplace implementation in Singular is restricted to homogeneous
ideals, and each generator can only have degree 1. With a little hack, I
introduced positive integral degree weights for generators, so that we can
now do:
{{{
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace',
degrees=[1,2,3])
sage: I = F*[x*y+z-y*x,x*y*z-x^6+y^3]*F
sage: I.groebner_basis(Infinity)
Twosided Ideal (x*z*z - y*x*x*z - y*x*y*y + y*x*z*x + y*y*y*x + z*x*z +
z*y*y - z*z*x, x*y - y*x + z, x*x*x*x*z*y*y + x*x*x*z*y*y*x - x*x*x*z*y*z
- x*x*z*y*x*z + x*x*z*y*y*x*x + x*x*z*y*y*y - x*x*z*y*z*x - x*z*y*x*x*z -
x*z*y*x*z*x + x*z*y*y*x*x*x + 2*x*z*y*y*y*x - 2*x*z*y*y*z - x*z*y*z*x*x -
x*z*y*z*y + y*x*z*x*x*x*x*x - 4*y*x*z*x*x*z - 4*y*x*z*x*z*x +
4*y*x*z*y*x*x*x + 3*y*x*z*y*y*x - 4*y*x*z*y*z + y*y*x*x*x*x*z +
y*y*x*x*x*z*x - 3*y*y*x*x*z*x*x - y*y*x*x*z*y + 5*y*y*x*z*x*x*x +
4*y*y*x*z*y*x - 4*y*y*y*x*x*z + 4*y*y*y*x*z*x + 3*y*y*y*y*z +
4*y*y*y*z*x*x + 6*y*y*y*z*y + y*y*z*x*x*x*x + y*y*z*x*z + 7*y*y*z*y*x*x +
7*y*y*z*y*y - 7*y*y*z*z*x - y*z*x*x*x*z - y*z*x*x*z*x + 3*y*z*x*z*x*x +
y*z*x*z*y + y*z*y*x*x*x*x - 3*y*z*y*x*z + 7*y*z*y*y*x*x + 3*y*z*y*y*y -
3*y*z*y*z*x - 5*y*z*z*x*x*x - 4*y*z*z*y*x + 4*y*z*z*z - z*y*x*x*x*z -
z*y*x*x*z*x - z*y*x*z*x*x - z*y*x*z*y + z*y*y*x*x*x*x - 3*z*y*y*x*z +
3*z*y*y*y*x*x + z*y*y*y*y - 3*z*y*y*z*x - z*y*z*x*x*x - 2*z*y*z*y*x +
2*z*y*z*z - z*z*x*x*x*x*x + 4*z*z*x*x*z + 4*z*z*x*z*x - 4*z*z*y*x*x*x -
3*z*z*y*y*x + 4*z*z*y*z + 4*z*z*z*x*x + 2*z*z*z*y, x*x*x*x*x*z +
x*x*x*x*z*x + x*x*x*z*x*x + x*x*z*x*x*x + x*z*x*x*x*x + y*x*z*y - y*y*x*z
+ y*z*z + z*x*x*x*x*x - z*z*y, x*x*x*x*x*x - y*x*z - y*y*y + z*z) of Free
Associative Unital Algebra on 3 generators (x, y, z) over Rational Field
}}}
This and the possibility to compute a complete Gröbner basis (provided a
finite complete Gröbner basis exists) go beyond what is currently in
Singular.
The underlying idea of the degree weights is: Introduce a homogenizing
variable. By default, it is called `x`, but a different name is chosen if
there is a name conflict. Here, it is renamed to `x_`. And then, we
represent a generator `z` of degree `d` internally as `z*x_^(d-1)` (of
course with non-commutative multiplication).
Hence, the underlying truncated letterplace ring becomes a bit bigger, and
in the bigger ring all generators are of degree one. Of course, the
additional variable is omitted in the string representation. We have for
example
{{{
sage: z
z
sage: z.degree()
3
sage: z.letterplace_polynomial()
z*x__1*x__2
}}}
As much as I know, with that approach, Gröbner bases are correctly
computed: If in all polynomials each occurrence of `z` is followed by
`x_^(d-1)` then all S-polynomials and reductions (computed in the ring
with additional generator `x_` and with all generators in degree 1) will
have the same property.
I know this is a hack, but I guess it may be useful. It certainly will be
usefull for my current project, because I ''need'' degree weights.
Apply trac7797-full_letterplace_wrapper_rel11068.patch
trac7797-letterplace_degree_weights.patch
Depends on #11068, #11268
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7797#comment:47>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
