Re: [sage-combinat-devel] Re: (free) algebras
On Sat, Mar 26, 2011 at 11:35:18PM -0700, Simon King wrote: On 27 Mrz., 08:11, Simon King simon.k...@uni-jena.de wrote: I guess, what I should do is to test at the beginning of the groebner_basis method whether we have a field, and give a clear error message. Also I should mention that restriction in the doc string of the groebner_basis method. Udate done. But no rebasing, yet. I have rebased it in the sage-combinat queue. I have left it guarded out though, because it requires a lot of recompilation (change to ring.pxd), which is annoying in the queue. Anyone who wants to play with it can just remove the guard in his own series file. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
Hi Simon, Thanks for the explanation! Everything seems to work fine now. I gave a positive review on trac for the added features, perhaps someone else could do a technical review of the patch. Best, Anne On 3/26/11 11:11 PM, Simon King wrote: Hi Anne, On 27 Mrz., 00:39, Anne Schillinga...@math.ucdavis.edu wrote: Hi Simon, I am not sure this is the smallest example, but I get some error messages when playing with the quotients: sage: n=3 sage: F = FreeAlgebra(ZZ,n,'x',implementation='letterplace') That's the other restriction (besides homegeneity): The letterplace Gröbnerbase computation works with fields. So, sadly, ZZ is not possible, but it should work with QQ. This is documented in Singular at http://www.singular.uni-kl.de/Manual/3-1-0/sing_425.htm (All algebras are assumed to be associative $K$-algebras for some field $K$.) and in my code as well, namely in the doc string of LetterplaceIdeal (In the two-sided case over a field, one can compute Groebner bases ...), and later on it gives an exammple: Also, it is currently not possible to compute a Groebner basis when the base ring is not a field: sage: FZ.a,b,c = FreeAlgebra(ZZ, implementation='letterplace') sage: J = FZ*[a^3-b^3]*FZ sage: J.groebner_basis(2) Traceback (most recent call last): ... RuntimeError: Error in Singular function call 'system': system(...) failed I don't know whether that restriction can be lifted, and *if* it is, whether the Singular team is working on it. I guess, what I should do is to test at the beginning of the groebner_basis method whether we have a field, and give a clear error message. Also I should mention that restriction in the doc string of the groebner_basis method. Best regards, Simon -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
Hi Simon,
This is beautiful! Thanks for your (and Singular)'s hard work on this!
What's the category for F? It would be great if it was in
AlgebrasWithBasis, and in particular if CombinatorialFreeModule and
FreeAlgebra would be consistent with each other (in particular for the
accessors on elements). The role of ModulesWithBasis is to enforce
this consistency, though it's not yet up to speed).
Cheers,
Nicolas
On Thu, Mar 24, 2011 at 09:36:17AM -0700, Simon King wrote:
The patch is submitted -- see #7797.
Here are some examples, also addressed to people who might be
interested in reviewing.
1. The arithmetic is fairly quick (but mind that it is restricted to
homogeneous elements, and so it can currently not be the default
implementation):
sage: F.x,y,z = FreeAlgebra(QQ, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators ('x', 'y', 'z') over
Rational Field
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: %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
3. We have Groebner bases and normal forms wrt. twosided homogeneous
ideals, and we can even construct the quotient ring:
sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F
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
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
A quotient ring of a quotient ring works as well.
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
Best regards,
Simon
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
Nicolas
--
Nicolas M. Thiéry Isil nthi...@users.sf.net
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
Hi Simon, Great! This works now. I'll play around with your patch and will report later. Cheers, Anne On 3/25/11 11:05 AM, Simon King wrote: Hi! I got it! On 25 Mrz., 18:59, Simon Kingsimon.k...@uni-jena.de wrote: $ ls sage/algebras/letterplace/ free_algebra_element_letterplace.pxd free_algebra_letterplace.pyx free_algebra_element_letterplace.pyx letterplace_ideal.pyx free_algebra_letterplace.pxd So, everything is put in place by the patch (in particular, the pxd- files are!). No, it isn't: There should also be an empty file, namely __init__.py, which I forgot to include into the patch. So, I'll udate my patch in a few minutes. You can also do touch SAGEROOT/devel/sage/sage/algebras/letterplace/ __init__.py and then do sage -br. Cheers, Simon -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
Hi Nicolas and Simon,
On Fri, Mar 25, 2011 at 05:37:41AM -0700, Anne Schilling wrote:
Nicolas, I wanted to add the patch trac7797-full_letterplace_wrapper.patch
to the sage-combinat queue to test it, but it does not commute with your patch
trac_10961-lie_bracket_in_rings-nt.patch. Would it be possible to rebase it?
Simon: given that #10961 is a 5 min review, would you agree letting it
go first in Sage, and rebasing your patch on top of it? I am happy to
do it too if you confirm that the version on trac is the very
latest. Of course, you are welcome to review #10961 too :-)
I just review #10961, but unfortunately could not give it a positive review
due to a typo in the doc test (the tests do not pass). Once that is fixed
I am happy to give a positive review.
Could you then rebase trac7797 so that it is easier to use it in the
sage-combinat queue? I added it there, but it is currently disabled.
You can use the version of it that Florent put it in
trac_9109-finite_set_maps-fh.patch. This patch is about good to go
into Sage, and comes early in the queue. Note it's in cython, and the
results are Sets, but otherwise it does the same:
sage: from sage.sets.finite_set_map_cy import fibers
sage: fibers(lambda x: x^2, [-1, 2, -3, 1, 3, 4])
{16: {4}, 1: {1, -1}, 4: {2}, 9: {3, -3}}
Great, thanks!
Cheers,
Anne
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
On Sat, Mar 26, 2011 at 06:11:44AM -0700, Anne Schilling wrote: I just review #10961, but unfortunately could not give it a positive review due to a typo in the doc test (the tests do not pass). Once that is fixed I am happy to give a positive review. Done. Thanks Could you then rebase trac7797 so that it is easier to use it in the sage-combinat queue? I added it there, but it is currently disabled. Ok, as soon as I get Simon's green light. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
Hi Simon,
One advantage of having a similar set up to AlgebrasWithBasis would be the
following
commands which are often quite useful:
sage: G = AlgebrasWithBasis(ZZ).example()
sage: G
An example of an algebra with basis: the free algebra on the generators
('a', 'b', 'c') over Integer Ring
sage: x = G.algebra_generators()
sage: p = x[1]*x[0]*x[2] + x[1]
sage: p.support()
[word: b, word: bac]
It currently does not seem so easy to get the support of an element in the free
algebra
sage: F = FreeAlgebra(QQ, 3, 'a', implementation='letterplace')
sage: a = F.gens()
sage: p = a[0]*a[1]*a[1]+a[0]*a[1]*a[2]
sage: p.support()
does not work.
The quotient seems to be working well! Great!
Cheers,
Anne
On 3/26/11 3:28 AM, Simon King wrote:
Hi Nicolas,
On 26 Mrz., 11:00, Simon Kingsimon.k...@uni-jena.de wrote:
Sorry, I first saw your post on sage-algebra and answered there,
although it might have been better to do it on combinat-devel. Anyway,
I am very unhappy with the documentation of the ...WithBasis stuff.
After several attempts, I still do not understand how to do even the
most basic operations with it.
Rather than trying to understand how
AlgebrasWithBasis(QQ).example().basis() is implemented, it might be
better to ask what purpose F.basis() (F a free algebra with generators
x,y,z) should have, in general?
I guess that F.basis() should have some index set. Here, it seems
natural to me to choose M=FreeMonoid(3,['x','y','z']): If m is in M
then F.basis()[m] returns the corresponding element of F.
Is that the only requirement to F.basis()?
Concerning compatibility: Rather than indexing the basis with the
elements of M, one could index it by the words in the alphabet
'x','y','z'. Is there a protocol for doing conversion by changing the
index set, yet? Such conversions could indeed facilitate consistency
between different implementations of the same algebra.
Cheers,
Simon
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
On 3/26/11 7:06 AM, Nicolas M. Thiery wrote: On Sat, Mar 26, 2011 at 06:11:44AM -0700, Anne Schilling wrote: I just review #10961, but unfortunately could not give it a positive review due to a typo in the doc test (the tests do not pass). Once that is fixed I am happy to give a positive review. Done. Thanks Could you then rebase trac7797 so that it is easier to use it in the sage-combinat queue? I added it there, but it is currently disabled. Ok, as soon as I get Simon's green light. Sounds good! Simon, can we rebased #7797? I set a positive review on #10961 and imported the final version on the sage-combinat queue (since you had not pushed your changes there). Best, Anne -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
On Sat, Mar 26, 2011 at 09:23:04AM -0700, Simon King wrote: I'll probably be not able to rebase it until Monday, but if you like, you can rebase it. Ok. I'll try to do that tonight. Otherwise tomorrow evening. Concerning the methods discussed here: For the current version of the patch, I did not think at all about bases. There even is no F.monoid() method of the free algebra F, and thus also no F.basis() indexed by the elements of F.monoid(). And the elements of F have no dict(), monomial_coefficient(), support() etc. I am not sure whether it would really be worth the effort: After all, FreeAlgebra_letterplace does not support inhomogeneous elements (until a future Singular version will be in Sage). And thus, for now, its purpose is quite narrow: Normal forms and degree-wise Gröbner bases of homogeneous two-sided ideals. At the moment, I tend to think that using AlgebrasWithBasis should be implemented only when general (i.e., inhomogeneous) arithmetic can be implemented. But who knows, perhaps I'll change my mind. Short answer for now: could you just implement __iter__, with the whatever representation (word, tuple, ...) is convenient for you for the basis indices? That will make a good incentive for those who need further methods (support/coeffs/...) to implement them generically in ModulesWithBasis :-) Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: (free) algebras
Hi Simon,
I am not sure this is the smallest example, but I get some error messages when
playing with the quotients:
sage: n=3
sage: F = FreeAlgebra(ZZ,n,'x',implementation='letterplace')
sage: x = F.gens()
sage: rel = [x[(i+1)%n]*x[i]*x[i]-x[i]*x[(i+1)%n]*x[i] for i in range(n)]
sage: rel += [x[(i+1)%n]*x[(i+1)%n]*x[i]-x[(i+1)%n]*x[i]*x[(i+1)%n] for i in
range(n)]
sage: rel
[-x0*x1*x0 + x1*x0*x0, -x1*x2*x1 + x2*x1*x1, x0*x2*x2 - x2*x0*x2, -x1*x0*x1 +
x1*x1*x0, -x2*x1*x2 + x2*x2*x1, x0*x0*x2 - x0*x2*x0]
sage: I = F*rel*F
sage: Q = F.quo(I, names='a')
sage: a = Q.gens()
sage: a[1]**3
a1*a1*a1
sage: a[1]**4
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (304, 0))
---
RuntimeError Traceback (most recent call last)
/Users/anne/Documents/Sage/ipython console in module()
/Applications/sage/local/lib/python2.6/site-packages/sage/structure/element.so
in sage.structure.element.RingElement.__pow__ (sage/structure/element.c:11817)()
/Applications/sage/local/lib/python2.6/site-packages/sage/structure/element.so
in sage.structure.element.generic_power_c (sage/structure/element.c:21115)()
/Applications/sage/local/lib/python2.6/site-packages/sage/structure/element.so
in sage.structure.element.RingElement.__mul__ (sage/structure/element.c:11377)()
/Applications/sage/local/lib/python2.6/site-packages/sage/structure/element.so
in sage.structure.element.RingElement._mul_ (sage/structure/element.c:11495)()
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/quotient_ring_element.pyc
in _mul_(self, right)
268 -b^2
269
-- 270 return self.parent()(self.__rep * right.__rep)
271
272 def _div_(self, right):
/Applications/sage/local/lib/python2.6/site-packages/sage/structure/parent.so
in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6676)()
/Applications/sage/local/lib/python2.6/site-packages/sage/structure/coerce_maps.so
in sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3119)()
/Applications/sage/local/lib/python2.6/site-packages/sage/structure/coerce_maps.so
in sage.structure.coerce_maps.DefaultConvertMap_unique._call_
(sage/structure/coerce_maps.c:3022)()
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/quotient_ring.pyc
in _element_constructor_(self, x, coerce)
771 R = self.cover_ring()
772 x = R(x)
-- 773 return quotient_ring_element.QuotientRingElement(self, x)
774
775 def _coerce_map_from_(self, R):
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/quotient_ring_element.pyc
in __init__(self, parent, rep, reduce)
102 self.__rep = rep
103 if reduce:
-- 104 self._reduce_()
105
106 def _reduce_(self):
/Applications/sage/local/lib/python2.6/site-packages/sage/rings/quotient_ring_element.pyc
in _reduce_(self)
121
122 I = self.parent().defining_ideal()
-- 123 self.__rep = I.reduce(self.__rep)
124
125 def lift(self):
/Applications/sage/local/lib/python2.6/site-packages/sage/algebras/letterplace/letterplace_ideal.so in sage.algebras.letterplace.letterplace_ideal.LetterplaceIdeal.reduce
(sage/algebras/letterplace/letterplace_ideal.cpp:3285)()
/Applications/sage/local/lib/python2.6/site-packages/sage/algebras/letterplace/free_algebra_element_letterplace.so in
sage.algebras.letterplace.free_algebra_element_letterplace.FreeAlgebraElement_letterplace.normal_form (sage/algebras/letterplace/free_algebra_element_letterplace.cpp:6257)()
/Applications/sage/local/lib/python2.6/site-packages/sage/algebras/letterplace/letterplace_ideal.so in sage.algebras.letterplace.letterplace_ideal.LetterplaceIdeal.groebner_basis
(sage/algebras/letterplace/letterplace_ideal.cpp:2750)()
/Applications/sage/local/lib/python2.6/site-packages/sage/libs/singular/function.so
in sage.libs.singular.function.SingularFunction.__call__
(sage/libs/singular/function.cpp:9666)()
RuntimeError:
Best wishes,
Anne
On 3/24/11 9:36 AM, Simon King wrote:
Hi Anne,
On 24 Mrz., 10:53, Anne Schillinga...@math.ucdavis.edu wrote:
...
Ok, this should not be a problem since in the application I have in mind
the relations are homogeneous and hence only terms in homogeneous terms
will cancel.
Therefore, in my to-be-submitted-as-soon-as-the-damned-documentation-
correctly-builds patch, it is excluded to even *create* an
inhomogeneous element. Probably that will be allowed as soon as the
next Singular version is in Sage.
Ok, let me know when your patch is available! I would be super happy to try it
out.
The patch is submitted -- see #7797.
Here are some examples, also addressed to people who might be
interested in reviewing.
1.
Re: [sage-combinat-devel] Re: (free) algebras
Hi Simon,
When I apply your patch to sage-4.6.2 and then run sage -b, I get the following
error message.
Building sage/symbolic/ring.pyx because it depends on sage/rings/ring.pxd.
Building sage/ext/interpreters/wrapper_cdf.pyx because it depends on
sage/rings/ring.pxd.
Building sage/ext/interpreters/wrapper_rr.pyx because it depends on
sage/rings/ring.pxd.
python `which cython` --cplus --embed-positions --directive cdivision=True,autotestdict=False -I/Applications/sage-4.6.2/devel/sage-combinat -o sage/algebras/letterplace/free_algebra_letterplace.cpp
sage/algebras/letterplace/free_algebra_letterplace.pyx
Error converting Pyrex file to C:
...
cdef class FreeAlgebra_letterplace
from sage.rings.ring cimport Algebra
from sage.structure.element cimport AlgebraElement, ModuleElement, RingElement,
Element
from sage.rings.polynomial.multi_polynomial_libsingular cimport
MPolynomialRing_libsingular, MPolynomial_libsingular
from sage.algebras.letterplace.free_algebra_element_letterplace cimport
FreeAlgebraElement_letterplace
^
/Applications/sage-4.6.2/devel/sage-combinat/sage/algebras/letterplace/free_algebra_letterplace.pxd:14:0:
'sage.algebras.letterplace.free_algebra_element_letterplace.pxd' not found
Error converting Pyrex file to C:
...
cdef class FreeAlgebra_letterplace
from sage.rings.ring cimport Algebra
from sage.structure.element cimport AlgebraElement, ModuleElement, RingElement,
Element
from sage.rings.polynomial.multi_polynomial_libsingular cimport
MPolynomialRing_libsingular, MPolynomial_libsingular
from sage.algebras.letterplace.free_algebra_element_letterplace cimport
FreeAlgebraElement_letterplace
^
/Applications/sage-4.6.2/devel/sage-combinat/sage/algebras/letterplace/free_algebra_letterplace.pxd:14:0:
'FreeAlgebraElement_letterplace.pxd' not found
Error converting Pyrex file to C:
...
cdef class FreeAlgebra_letterplace
from sage.rings.ring cimport Algebra
from sage.structure.element cimport AlgebraElement, ModuleElement, RingElement,
Element
from sage.rings.polynomial.multi_polynomial_libsingular cimport
MPolynomialRing_libsingular, MPolynomial_libsingular
from sage.algebras.letterplace.free_algebra_element_letterplace cimport
FreeAlgebraElement_letterplace
^
/Applications/sage-4.6.2/devel/sage-combinat/sage/algebras/letterplace/free_algebra_letterplace.pxd:14:72: Name 'FreeAlgebraElement_letterplace' not declared in module
'sage.algebras.letterplace.free_algebra_element_letterplace'
Error running command, failed with status 256.
sage: There was an error installing modified sage library code.
Do you know what could be wrong?
Best,
Anne
On 3/24/11 9:36 AM, Simon King wrote:
Hi Anne,
On 24 Mrz., 10:53, Anne Schillinga...@math.ucdavis.edu wrote:
...
Ok, this should not be a problem since in the application I have in mind
the relations are homogeneous and hence only terms in homogeneous terms
will cancel.
Therefore, in my to-be-submitted-as-soon-as-the-damned-documentation-
correctly-builds patch, it is excluded to even *create* an
inhomogeneous element. Probably that will be allowed as soon as the
next Singular version is in Sage.
Ok, let me know when your patch is available! I would be super happy to try it
out.
The patch is submitted -- see #7797.
Here are some examples, also addressed to people who might be
interested in reviewing.
1. The arithmetic is fairly quick (but mind that it is restricted to
homogeneous elements, and so it can currently not be the default
implementation):
sage: F.x,y,z = FreeAlgebra(QQ, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators ('x', 'y', 'z') over
Rational Field
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: %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
3. We have Groebner bases and normal forms wrt. twosided homogeneous
ideals, and we can even construct the quotient ring:
sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F
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 -
