#7797: Full interface to letterplace from singular
---------------------------------------------------------------+------------
Reporter: burcin | Owner:
burcin
Type: enhancement | Status:
needs_work
Priority: major | Milestone:
sage-4.7
Component: algebra | Keywords:
singular
Author: Simon King, Michael Brickenstein, Burcin Erocal | Upstream:
N/A
Reviewer: | Merged:
Work_issues: |
---------------------------------------------------------------+------------
Comment(by SimonKing):
I have attached a new patch that replaces all previous patches and
provides a lot more functionality.
Since I learned much from the previous patches, I hesitate to remove
Michael and Burcin from the author list. But perhaps you like to be
referee? Then you should move your name into the reviewer field.
'''__Technical Remarks__'''
`singular_function` is very useful! However, it was impossible to simply
call the `freegb.lib` library functions of Singular, since they rely on
ring attributes -- but ring attributes have not been wrapped in
`libSingular`.
Moreover, it is not a good idea to call the `makeLetterplaceRing` function
from Singular and then transform the resulting `RingWrap` into a
polynomial ring. It ''is'' possible -- but the result can not be pickled,
since its variable names look like `x(1),y(1),x(2),y(2)` and are thus no
valid identifiers.
But it is no problem to create another ring with more sober variable
names, and apply the letterplace functions to it. One just needs to work
around the attribute tests that these functions do. In fact, these
functions do only one thing after the checking, namely a system call. So,
I simply did this system calls as well.
In the current release, Singular does provide the Gröbner basis
computations in free algebras, but it does ''not'' provide normal form
computations. Grischa Studzinski has send me some code that is supposed to
become part of `freegb.lib` -- again, I can not call it directly, but it
was fairly straight forward to implement along the lines of Grischa's
code.
'''__New Features__'''
''__Free Algebra constructor as `UniqueFactory`__''
Up to now, the `FreeAlgebra` constructor was based on an incomplete way of
caching: When you pickle and unpickle a free algebra, you would not get
the same object.
{{{
# old behaviour
sage: F.<a,b,c> = FreeAlgebra(QQ,3)
sage: loads(dumps(F)) is F
False
}}}
This is now resolved. Moreover, it is not needed to explicitly provide the
number of generators, when it is obvious from the list of names:
{{{
sage: F.<x,y,z> = FreeAlgebra(QQ)
sage: loads(dumps(F)) is F
True
}}}
I did one change that may be subject to criticism, and I wouldn't oppose
to revert it. A free algebra in one generator is a polynomial ring. So, I
return a polynomial ring:
{{{
sage: FreeAlgebra(QQ,'x')
Univariate Polynomial Ring in x over Rational Field
}}}
The constructor can now also be asked for a different implementation, as
in all examples below.
''__Free Algebra via Letterplace__''
I provide a new implementation of free algebras. It can be constructed as
follows:
{{{
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators ('x', 'y', 'z') over
Rational Field
}}}
Due to some shortcomings of Singular's letterplace implementation,
unfortunately we need to restrict to homogeneous elements:
{{{
sage: (x+2*y)^2
x*x + 2*x*y + 2*y*x + 4*y*y
sage: x+0
x
Traceback (most recent call last):
...
ArithmeticError: Can only add elements of the same degree
}}}
This is why the new implementation can not yet become the default.
However, the arithmetic in the new implementation is much faster than the
old:
{{{
sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F_old.<a,b,c> = FreeAlgebra(QQ)
sage: timeit('t=(x+y)^15')
5 loops, best of 3: 27.7 ms per loop
sage: timeit('t=(a+b)^15')
sage: %time t=(a+b)^15
CPU times: user 4.51 s, sys: 0.09 s, total: 4.60 s
Wall time: 6.46 s
sage: 4510/27.7
162.815884476534
sage: timeit('t=(x+y)^15')
25 loops, best of 3: 19.7 ms per loop
sage: %time t=(a+b)^15
CPU times: user 2.70 s, sys: 0.02 s, total: 2.72 s
Wall time: 2.73 s
sage: 2700/19.7
137.055837563452
}}}
''__One- and Twosided Ideals of Noncommutative Rings__''
I implemented it in a fairly general way, ideals can be created for any
ring:
{{{
sage: A = SteenrodAlgebra(2)
sage: IL = A*[A.1+A.2,A.1^2]; IL
Left Ideal (Sq(2) + Sq(4), Sq(1,1)) of mod 2 Steenrod algebra
sage: IR = [A.1+A.2,A.1^2]*A; IR
Right Ideal (Sq(2) + Sq(4), Sq(1,1)) of mod 2 Steenrod algebra
sage: IT = A*[A.1+A.2,A.1^2]*A; IT
Twosided Ideal (Sq(2) + Sq(4), Sq(1,1)) of mod 2 Steenrod algebra
}}}
Note some nastyness: The parent of an ideal still is the "monoid of ideals
of a ring". But we actually have no multiplication in the non-commutative
setting:
{{{
sage: IL*IR
Traceback (most recent call last):
...
NotImplementedError: Can not multiply non-commutative ideals.
}}}
Of course, in general, we have no way to solve the ideal containment
problem. But in free algebras, we have letterplace:
{{{
sage: I.groebner_basis(degbound=3)
Twosided Ideal (y*y*y - y*y*z + y*z*y - y*z*z, y*y*x + y*y*z + y*z*x +
y*z*z, x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital
Algebra on 3 generators ('x', 'y', 'z') over Rational Field
sage: (x*y*z*y*x).normal_form(I)
y*z*z*y*z + y*z*z*z*x + y*z*z*z*z
sage: x*y*z*y*x - (x*y*z*y*x).normal_form(I) in I
True
sage: x*I.0-I.1*y+I.0*y in I
True
sage: 1 in I
False
}}}
''__Quotient Rings__''
Previously, quotient rings have only been available for rings that inherit
from the base class of commutative rings. My patch makes them available
for all rings, and actually it should work to some extent even for objects
that belong to the category `Rings()` but do not inherit from
`sage.rings.ring.Ring`.
The requirement is that we mod by an ideal `I` that is ''twosided'' and
that has a method `I.reduce(x)` that returns a normal form of an element
`x` with respect to `I`. That requirement holds for ideals of polynomial
rings, and also for homogeneous ideals of free associative algebras. In
particular:
{{{
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: Q.<a,b,c> = F.quo(I); Q
Quotient of Free Associative Unital Algebra on 3 generators ('x', 'y',
'z') over Rational Field by the ideal (x*y + y*z, x*x + x*y - y*x - y*y)
sage: a*b
-b*c
sage: a^3
-b*c*a - b*c*b - b*c*c
sage: J = Q*[a^3-b^3]*Q
sage: R.<i,j,k> = Q.quo(J); R
Quotient of Free Associative Unital Algebra on 3 generators ('x', 'y',
'z') over Rational Field by the ideal (-y*y*z - y*z*x - 2*y*z*z, x*y +
y*z, x*x + x*y - y*x - y*y)
sage: i^3
-j*k*i - j*k*j - j*k*k
sage: j^3
-j*k*i - j*k*j - j*k*k
}}}
One can also test if the quotient is commutative:
{{{
sage: Q.is_commutative()
False
sage: J = F*[x*y-y*x,x*z-z*x,y*z-z*y,x^3-y^3]*F
sage: R = F.quo(J)
sage: R.is_commutative()
True
}}}
'''__Miscellaneous__'''
I inserted the documentation of the new modules into the reference manual
- I think it looks nice, but I guess a referee should double check.
Doc tests pass for me. Thus: Ready for review!!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7797#comment:21>
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.
