search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 480 forks source link

Full interface to letterplace from singular #7797

Closed burcin closed 11 years ago

burcin commented 14 years ago

The new aim of this ticket is to add an interface to the letterplace component of Singular, that actually goes beyond what Singular offers.

The patch provides

(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_combined.patch and attachment: trac_7797-ref.patch

Depends on #11068 #11268 #12641 #12749

Depends on #4539 Depends on #11268 Depends on #12461 Depends on #12749 Depends on #12988 Depends on #13237

Upstream: None of the above - read trac for reasoning.

CC: @sagetrac-PolyBoRi @saliola @malb @jhpalmieri @sagetrac-sage-combinat @sagetrac-OleksandrMotsak

Component: algebra

Keywords: singular, free algebra, letterplace

Author: Simon King, Michael Brickenstein, Burcin Erocal

Reviewer: Alexander Dreyer

Merged: sage-5.5.beta2

Issue created by migration from https://trac.sagemath.org/ticket/7797

simon-king-jena commented 13 years ago

Description changed:

--- 
+++ 
@@ -13,6 +13,6 @@

 Examples are below, in the comments.

-Apply trac7797-full_letterplace_wrapper.patch
+Apply trac7797-full_letterplace_wrapper_rel11068.patch

-Depends on #10961
+Depends on #11068
simon-king-jena commented 13 years ago

Changed work issues from Unigenerated free algebra vs. univariate polynomial ring to Unigenerated free algebra vs. univariate polynomial ring; refactoring of nc-ideals

simon-king-jena commented 13 years ago
comment:41

I don't know why, but even though mercurial claims that it tracks sage/algebras/letterplace/__init__.py, it kept forgetting to include it into the patch. So, I decided to fill __init__.py with some comment. Now it should work.

Of course, you may play with the patch, but it still needs work. First of all, there is the issue that the free algebra constructor should never return a polynomial ring (in the univariate case). And then, my plan is to refactor things, such that there will also be dependencies with #9138 and #9944.

Depends on #11068

Apply trac7797-full_letterplace_wrapper_rel11068.patch

simon-king-jena commented 13 years ago
comment:42

I updated the patch.

Apply trac7797-full_letterplace_wrapper_rel11068.patch

Depends on #11068

Actually I am not sure about all dependencies. #11068 should be enough on top of sage-4.7.alpha5. However, here is a full account of the patches that I had applied to sage-4.7.alpha5 before creating the patch here: #10296, #9944, #9138, #9976, #11115, #11068.

In particular, I think the refactoring of rings, quotient rings and non-commutative ideals is successfully solved in #9138 and #11068. Concerning unigenerated free algebras, it seems better to stay in the world of free algebras, rather than returning a polynomial ring. So, we have

sage: F.<x> = FreeAlgebra(QQ)
sage: F
Free Algebra on 1 generators (x,) over Rational Field
sage: F.is_commutative()
True
sage: F.<x> = FreeAlgebra(QQ, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 1 generators (x,) over Rational Field
sage: F.is_commutative()
True

In principle, it could be reviewed now. But the patch chain in front of it is rather large, and not everything has a positive review, yet.

My next plan: Allow positive integer degree weights on the generators, extending the scope of the letterplace wrapper from homogeneous to weighted homogeneous elements, and allow degree-wise computation of weighted homogeneous Gröbner bases. Note that this goes beyond what is currently implemented in Singular, but it should work using a little hack (slack variables).

simon-king-jena commented 13 years ago

Changed work issues from Unigenerated free algebra vs. univariate polynomial ring; refactoring of nc-ideals to none

simon-king-jena commented 13 years ago
comment:43

Sorry, I needed to update the patch due to some outdated doc tests that I forgot to correct.

Apply trac7797-full_letterplace_wrapper_rel11068.patch

Depends on #11068

simon-king-jena commented 13 years ago
comment:44

I just found that the documentation (at least with #9976 applied) is not good. Some stuff is included that certainly does not belong there.

simon-king-jena commented 13 years ago
comment:45

Replying to @simon-king-jena:

I just found that the documentation (at least with #9976 applied) is not good. Some stuff is included that certainly does not belong there.

Actually, on second thought, it belongs there: I am talking about the two singular_function instances included in the module. The main problem was that singular_function includes the documentation provided by Singular without taking care of formatting -- resulting in numerous errors (e.g., back ticks are misinterpreted as the beginning of Latex expressions, the indentation is handled differently, and so on).

In #11268, I suggest to take care if it by turning the Singular documentation into a verbose code block. With that change, the documentation looks a lot better. I therefore make it a new dependency.

Depends on #11068 #11268

simon-king-jena commented 13 years ago

Description changed:

--- 
+++ 
@@ -15,4 +15,4 @@

 Apply trac7797-full_letterplace_wrapper_rel11068.patch

-Depends on #11068
+Depends on #11068 #11268
simon-king-jena commented 13 years ago

Dependencies: #11068, #11268

simon-king-jena commented 13 years ago

Attachment: trac7797-letterplace_degree_weights.patch.gz

Positive integral degree weights for letterplace. UniqueFactory for free algebras.

simon-king-jena commented 13 years ago

Changed keywords from singular to singular, free algebra, letterplace

simon-king-jena commented 13 years ago

Description changed:

--- 
+++ 
@@ -13,6 +13,10 @@

 Examples are below, in the comments.

-Apply trac7797-full_letterplace_wrapper_rel11068.patch
+Apply
+
+[attachment: trac7797-full_letterplace_wrapper_rel11068.patch](https://github.com/sagemath/sage-prod/files/10647356/trac7797-full_letterplace_wrapper_rel11068.patch.gz)
+
+[attachment: trac7797-letterplace_degree_weights.patch](https://github.com/sagemath/sage-prod/files/10647355/trac7797-letterplace_degree_weights.patch.gz)

 Depends on #11068 #11268
simon-king-jena commented 13 years ago
comment:47

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

simon-king-jena commented 13 years ago
comment:48

I noticed that I forgot one detail: Latex!

With the latest patch, we also get

sage: K.<z> = GF(25)
sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace', degrees=[1,2,3])
sage: -(a*b*(z+1)-c)^2
(2*z + 1)*a*b*a*b + (z + 1)*a*b*c + (z + 1)*c*a*b - c*c
sage: latex(-(a*b*(z+1)-c)^2)
\left(2 z + 1\right) a b a b + \left(z + 1\right) a b c + \left(z + 1\right) c a b - c c

Apply trac7797-full_letterplace_wrapper_rel11068.patch trac7797-letterplace_degree_weights.patch trac7797-latex_letterplace.patch

Depends on #11068, #11268

simon-king-jena commented 13 years ago

Description changed:

--- 
+++ 
@@ -19,4 +19,6 @@

 [attachment: trac7797-letterplace_degree_weights.patch](https://github.com/sagemath/sage-prod/files/10647355/trac7797-letterplace_degree_weights.patch.gz)

+[attachment: trac7797-latex_letterplace.patch](https://github.com/sagemath/sage-prod/files/10647357/trac7797-latex_letterplace.patch.gz)
+
 Depends on #11068 #11268
simon-king-jena commented 13 years ago
comment:49

... or also

sage: F.<bla,alpha,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[1,2,3])
sage: latex(-3*alpha*bla-z)
-3 \alpha \mbox{bla} - z
simon-king-jena commented 13 years ago
comment:50

Odd. The documentation for letterplace used to build fine. But now, it does not build at all! The output are three empty html pages (empty except for the title and the navigation) - the doc strings do not appear.

Any idea where that might come from?

simon-king-jena commented 13 years ago
comment:51

I don't know where it came from. But after deleting doc/output/html/en/reference and doc/output/doctrees/, building the documentation finally succeeded.

So, problem vanished.

simon-king-jena commented 13 years ago
comment:52

Apparently I had changed the milestone by accident...

simon-king-jena commented 13 years ago
comment:53

In my application, I also need conversion from graded sub-algebras. Hence, I implemented it in the new patch.

To be precise: If we have free graded algebras A and B in letterplace implementation, then there is a coercion from A to B if and only if there is a coercion from the base ring of A to the base ring of B, and the set of generator names of A is a subset of the generator names of B, and the degrees of equally named generators of A and B are equal.

The coercion is always name and degree preserving.

Example:

sage: F.<t,y,z> = FreeAlgebra(ZZ, implementation='letterplace', degrees=[4,2,3])
sage: G = FreeAlgebra(GF(5), implementation='letterplace', names=['x','y','z','t'], degrees=[1,2,3,4])
sage: t*G.0       # indirect doctest
t*x
sage: (t*G.0 + G.1*G.2)*y
y*z*y + t*x*y

Apply trac7797-full_letterplace_wrapper_rel11068.patch trac7797-letterplace_degree_weights.patch trac7797-latex_letterplace.patch trac7797-letterplace_coercion.patch

simon-king-jena commented 13 years ago

Description changed:

--- 
+++ 
@@ -21,4 +21,6 @@

 [attachment: trac7797-latex_letterplace.patch](https://github.com/sagemath/sage-prod/files/10647357/trac7797-latex_letterplace.patch.gz)

+[attachment: trac7797-letterplace_coercion.patch](https://github.com/sagemath/sage-prod/files/10647358/trac7797-letterplace_coercion.patch.gz)
+
 Depends on #11068 #11268
simon-king-jena commented 13 years ago

Attachment: trac7797-full_letterplace_wrapper_rel11068.patch.gz

A full wrapper for Singular's letterplace functionality, plus complete Groebner bases; based on top of 11068

simon-king-jena commented 13 years ago

Attachment: trac7797-latex_letterplace.patch.gz

Implement latex for letterplace polynomials and letterplace algebras

simon-king-jena commented 13 years ago

Implementing coercion for letterplace algebras

simon-king-jena commented 13 years ago
comment:54

Attachment: trac7797-letterplace_coercion.patch.gz

I had to rebase three of the four patches. Still needing review...

Apply trac7797-full_letterplace_wrapper_rel11068.patch trac7797-letterplace_degree_weights.patch trac7797-latex_letterplace.patch trac7797-letterplace_coercion.patch

kiwifb commented 13 years ago
comment:55

In attachment: trac7797-full_letterplace_wrapper_rel11068.patch please do not use SAGE_ROOT + local/include in module_list.py use SAGE_INC instead. I spent sometime cleaning all that up for 4.7.1 and would like to see it stay clean for a little while longer.

simon-king-jena commented 13 years ago
comment:56

Replying to @kiwifb:

In attachment: trac7797-full_letterplace_wrapper_rel11068.patch please do not use SAGE_ROOT + local/include in module_list.py use SAGE_INC instead.

I didn't know that SAGE_INC exists. It is certainly a good idea to use such variables whenever possible.

simon-king-jena commented 13 years ago
comment:57

I'm now using SAGE_INC, and I used the occasion to create a combined patch.

Apply trac7797-full_letterplace_wrapper_combined.patch

simon-king-jena commented 13 years ago

Description changed:

--- 
+++ 
@@ -1,12 +1,10 @@
-The new aim of this ticket is to add an interface to the [letterplace](http://www.singular.uni-kl.de/Manual/latest/sing_427.htm#SEC480) component of Singular, namely providing
+The new aim of this ticket is to add an interface to the [letterplace](http://www.singular.uni-kl.de/Manual/latest/sing_427.htm#SEC480) component of Singular, that actually goes beyond what Singular offers.

-* A new implementation of free algebras with fast arithmetic.
-* Degree-wise Gröbner basis computation for twosided homogeneous ideals of free algebras.
+The patch provides
+
+* A new implementation of free algebras with fast arithmetic, but  restricted to weighted homogeneous elements, with positive integral degree weights.
+* Degree-wise Gröbner basis computation for twosided weighted homogeneous ideals of free algebras. If a finite complete Gröbner basis exists, it can be computed.
 * 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.)
@@ -15,12 +13,6 @@

 Apply

-[attachment: trac7797-full_letterplace_wrapper_rel11068.patch](https://github.com/sagemath/sage-prod/files/10647356/trac7797-full_letterplace_wrapper_rel11068.patch.gz)
-
-[attachment: trac7797-letterplace_degree_weights.patch](https://github.com/sagemath/sage-prod/files/10647355/trac7797-letterplace_degree_weights.patch.gz)
-
-[attachment: trac7797-latex_letterplace.patch](https://github.com/sagemath/sage-prod/files/10647357/trac7797-latex_letterplace.patch.gz)
-
-[attachment: trac7797-letterplace_coercion.patch](https://github.com/sagemath/sage-prod/files/10647358/trac7797-letterplace_coercion.patch.gz)
+[attachment: trac7797-full_letterplace_wrapper_combined.patch](https://github.com/sagemath/sage-prod/files/10647360/trac7797-full_letterplace_wrapper_combined.patch.gz)

 Depends on #11068 #11268
simon-king-jena commented 13 years ago
comment:58

I had to rebase my patch: Some trivial changes in the doc tests were needed, since block orders are now displayed differently.

Apply trac7797-full_letterplace_wrapper_combined.patch

d46d2cb1-860f-484d-8329-8ebfc9f5d004 commented 13 years ago
comment:59

sage-4.7.2alpha3-prerelease with the following patches applies:

trac11815_format_must_preserve_embedding.patch
trac11115-cached_cython.patch
trac11115_cached_function_pickling.patch
trac11068_nc_ideals_and_quotients.patch
trac11068_quotient_ring_without_names.patch
trac11068_lifting_map.patch
trac7797-full_letterplace_wrapper_combined.patch

compiles/installs and runs sage -testall successfully on a SuSE Enterprise 11.1. This is close to a positive review, but I'll check out another platform before and have a look at the patch.

d46d2cb1-860f-484d-8329-8ebfc9f5d004 commented 13 years ago

Reviewer: Alexander Dreyer

d46d2cb1-860f-484d-8329-8ebfc9f5d004 commented 13 years ago
comment:61

Also compiles/installs and runs sage -testall successfully on Mac OSX ppc (32bit). So I can give a positive review for the technical part. Somebody needs to look for the Maths.

simon-king-jena commented 13 years ago
comment:62

I think it makes sense to use #4539 (which already has a positive review, but is pending because of #9138) as a dependency. I have updated the patch accordingly. The doc tests pass (at least on my machine).

simon-king-jena commented 13 years ago

Changed dependencies from #11068, #11268 to #4539, #11268

simon-king-jena commented 13 years ago
comment:63

I forgot to notify the patch bot:

Apply trac7797-full_letterplace_wrapper_combined.patch

11d1fc49-71a1-44e1-869f-76be013245a0 commented 12 years ago

Changed dependencies from #4539, #11268 to #4539, #11268, #12461

11d1fc49-71a1-44e1-869f-76be013245a0 commented 12 years ago
comment:64

The patch fails to apply to 5.0.beta11 -- see patchbot logs. I suspect #12461 is the cause.

simon-king-jena commented 12 years ago
comment:65

Yes, #12641 was to blame. The reason was that apparently #12641 did remove four blank spaces. So, the change is trivial.

By the way: At the recent annual meeting of the German Science Foundation Priority Programme on computer algebra, I was talking to Viktor Levandovskii, who is responsible for Letterplace in Singular. He confirmed that my hacks for implementing degree weights and for computing complete Gröbner bases are correct.

Apply trac7797-full_letterplace_wrapper_combined.patch

simon-king-jena commented 12 years ago

Description changed:

--- 
+++ 
@@ -15,4 +15,4 @@

 [attachment: trac7797-full_letterplace_wrapper_combined.patch](https://github.com/sagemath/sage-prod/files/10647360/trac7797-full_letterplace_wrapper_combined.patch.gz)

-Depends on #11068 #11268
+Depends on #11068 #11268 #12641
simon-king-jena commented 12 years ago

Changed dependencies from #4539, #11268, #12461 to #4539, #11268, #12461, #12749

simon-king-jena commented 12 years ago
comment:66

It needs to be rebased wrt. #12749: This ticket adds doctests, but one hunk for sage/algebras/free_algebra.py adds some doctest as well...

simon-king-jena commented 12 years ago

Work Issues: rebase rel #12749

simon-king-jena commented 12 years ago

Changed work issues from rebase rel #12749 to none

simon-king-jena commented 12 years ago
comment:67

Done. And please please find someone for a review!

Apply trac7797-full_letterplace_wrapper_combined.patch

simon-king-jena commented 12 years ago

Description changed:

--- 
+++ 
@@ -15,4 +15,4 @@

 [attachment: trac7797-full_letterplace_wrapper_combined.patch](https://github.com/sagemath/sage-prod/files/10647360/trac7797-full_letterplace_wrapper_combined.patch.gz)

-Depends on #11068 #11268 #12641
+Depends on #11068 #11268 #12641 #12749
simon-king-jena commented 12 years ago
comment:68

It is now 4 months ago that I last asked if someone could review the patch, so that we would have Gröbner bases of two-sided homogeneous ideals in free associative algebras. Which other CAS has those? So: BUMP!

simon-king-jena commented 12 years ago

Changed dependencies from #4539, #11268, #12461, #12749 to #4539, #11268, #12461, #12749, #12988

simon-king-jena commented 12 years ago
comment:69

I had to modify one doctest, due to a new test in the category of rings - see #12988.

Apply trac7797-full_letterplace_wrapper_combined.patch