search

sagemath / sage

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

Refactor symmetric functions and k-bounded subspace #5457

Closed nthiery closed 12 years ago

nthiery commented 15 years ago

This patch restructures the implementation of symmetric functions in sage

The new implementation makes use of multiple realizations and the category framework. The new access to symmetric functions is via

sage: Sym = SymmetricFunctions(QQ)

Further new features that are implemented:

sage: SymmetricFunctions??

This patch gained tremendously by the tutorial on symmetric functions written by Jason Bandlow, a draft on the k-bounded subspace by Jason Bandlow, and code multiple realizations written by Franco Saliola.

See also http://groups.google.com/group/sage-devel/msg/a49f3288fca1b75c

Apply

Depends on #11563 Depends on #13109 Depends on #12969

CC: @sagetrac-sage-combinat @saliola @dwbump @sagetrac-chrisjamesberg @zabrocki @simon-king-jena

Component: combinatorics

Keywords: symmetric functions, days38, sd40

Author: Mike Zabrocki, Anne Schilling, Jason Bandlow

Reviewer: Dan Bump, Nicolas M. Thiéry, Jeroen Demeyer

Merged: sage-5.4.beta0

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

nthiery commented 15 years ago

Description changed:

--- 
+++ 
@@ -1,10 +1,10 @@
 Refactor symmetric functions to:
 - use a single entry point, as in MuPAD-Combinat. Something like:
-       S = SymmetricFunctions(field)
-       S.schur
-       S.jack(t).P
-       S.macdonald(t,q).Q
-       S.kSchur(3).H
+     -  S = SymmetricFunctions(field)
+     -  S.schur
+     -  S.jack(t).P
+     -  S.macdonald(t,q).Q
+     -  S.kSchur(3).H
 - use the coercion framework
 - use the category framework
anneschilling commented 12 years ago

Dependencies: 13109

anneschilling commented 12 years ago

Changed dependencies from 13109 to none

anneschilling commented 12 years ago

Reviewer: Dan Bump, Franco Saliola

anneschilling commented 12 years ago

Author: Mike Zabrocki, Anne Schilling

anneschilling commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,11 +1,38 @@
-Refactor symmetric functions to:
-- use a single entry point, as in MuPAD-Combinat. Something like:
-     -  S = SymmetricFunctions(field)
-     -  S.schur
-     -  S.jack(t).P
-     -  S.macdonald(t,q).Q
-     -  S.kSchur(3).H
-- use the coercion framework
-- use the category framework
+This patch restructures the implementation of symmetric functions in sage
+
+The new implementation makes use of multiple realizations and the category
+framework. The new access to symmetric functions is via
+
+```
+sage: Sym = SymmetricFunctions(QQ)
+```
+
+Further new features that are implemented:
+
+- The ring of symmetric functions is now endowed with a Hopf algebra structure.
+  The coproduct and antipode are implemented (which were missing before).
+
+- A tutorial on how to use symmetric functions in sage is included at the
+  beginning of sf.py which is also accessible via
+
+```
+sage: SymmetricFunctions??
+```
+
+- Symmetric functions should now work a lot better with respect to 
+  specializing parameters like `q` and `t` for Hall-Littlewood, Jack
+  and Macdonald symmetric functions. Certain functionalities before
+  this change were broken or not possible.
+
+- Documentation was added to LLT polynomials (which had very sparse documentation
+  previously).
+
+- The `k`-bounded subspace of the ring of symmetric function was implemented.
+  The `k`-Schur functions now live in the `k`-bounded subspace rather than
+  in the ring of symmetric functions as before.
+
+This patch gained tremendously by the tutorial on symmetric functions written
+by Jason Bandlow and Nicolas Thiery, a draft on the `k`-bounded subspace by
+Jason Bandlow, and code multiple realizations written by Franco Saliola.

 See also:http://groups.google.com/group/sage-devel/msg/a49f3288fca1b75c
anneschilling commented 12 years ago

Changed keywords from none to symmetric functions, sd38, sd40

anneschilling commented 12 years ago
comment:10

Hi Mike,

I finished the doctests for the following files:

In particular, at the beginning of sf.py I incorporated the tutorial that Jason and Nicolas wrote (which was further down the queue) and updated it. I marked them there as coauthors in that file.

This leaves the doctests for

which I suppose you will do in the next couple of days? In particular, in the sfa.py the deprecation warnings need to be activated which I have not yet done.

Best,

Anne

anneschilling commented 12 years ago

Changed author from Mike Zabrocki, Anne Schilling to Mike Zabrocki, Anne Schilling, Jason Bandlow

vbraun commented 12 years ago

Dependencies: #11563

vbraun commented 12 years ago

Changed dependencies from #11563 to #11563, #13109

anneschilling commented 12 years ago

Description changed:

--- 
+++ 
@@ -36,3 +36,6 @@
 Jason Bandlow, and code multiple realizations written by Franco Saliola.

 See also:http://groups.google.com/group/sage-devel/msg/a49f3288fca1b75c
+
+Apply
+* [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
anneschilling commented 12 years ago
comment:15

Hi Mike,

I completed the doctests for sfa.py and also rebased everything on top of 13109. Please put your changes to

on top of the current patch trac_5457-symmetric_functions-mz.patch. Unfortunately we need to abandon the sage-combinat queue for the moment since it would be very cumbersome to keep it backward compatible with 13109. I will send you a separate e-mail on how to proceed.

Cheers,

Anne

anneschilling commented 12 years ago
comment:16

Ok, patch is ready for review! It should apply and run cleanly on sage.5.2.rc0!

Anne

anneschilling commented 12 years ago
comment:18

Apply attachment: trac_5457-symmetric_functions-mz.patch

anneschilling commented 12 years ago
comment:20

Hi Dan!

Thank you very much for your comments on the failing doctests in

They are fixed in the updated version of the patch. I do not get failures for

on my machine.

lolita-4:sandpiles anne$ sage -t sandpile.py sage -t "devel/sage-sf/sage/sandpiles/sandpile.py"
[19.0 s]

All tests passed! Total time for all tests: 19.0 seconds

Anne

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 12 years ago
comment:21

Replying to @anneschilling:

Hi Dan!

Thank you very much for your comments on the failing doctests in

  • devel/sage/sage/algebras/nil_coxeter_algebra.py

  • devel/sage/sage/categories/realizations.py

They are fixed in the updated version of the patch. I do not get failures for

  • devel/sage/sage/sandpiles/sandpile.py

on my machine.

I also get a doctest failure in sandpile.py with unpatched sage-5.2.rc0 so this failure is not caused by the patch.

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 12 years ago
comment:22

Applies cleanly to sage-5.2 and passes all tests.

anneschilling commented 12 years ago

Description changed:

--- 
+++ 
@@ -39,3 +39,4 @@

 Apply
 * [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
+* [attachment: trac_5457-review-as.patch](https://github.com/sagemath/sage/files/ticket5457/trac_5457-review-as.patch.gz)
anneschilling commented 12 years ago
comment:24

The attached review patch trac_5457-review-as.patch incorporates most of the comments that Dan Bump raised in e-mail conversations.

Anne

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 12 years ago

Description changed:

--- 
+++ 
@@ -35,7 +35,7 @@
 by Jason Bandlow and Nicolas Thiery, a draft on the `k`-bounded subspace by
 Jason Bandlow, and code multiple realizations written by Franco Saliola.

-See also:http://groups.google.com/group/sage-devel/msg/a49f3288fca1b75c
+See also http://groups.google.com/group/sage-devel/msg/a49f3288fca1b75c

 Apply
 * [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
6bbcde06-8197-41f1-b9a3-c998bb839000 commented 12 years ago
comment:25

This patch is a huge step forward for symmetric functions.

In addition to normal testing I spent quite a bit of time and privately sent comments (mainly on documentation) that have been taken into account in trac_5457-review-as.patch. I'm changing the status to positive review.

anneschilling commented 12 years ago
comment:26

Replying to @dwbump:

This patch is a huge step forward for symmetric functions.

In addition to normal testing I spent quite a bit of time and privately sent comments (mainly on documentation) that have been taken into account in trac_5457-review-as.patch. I'm changing the status to positive review.

Dear Dan, Thank you so much for your thorough and quick review of this huge patch! Mike and I just finished the review patch. Tests pass on both of our machines.

Anne

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 12 years ago
comment:27

I have reviewed the latest version of the patch and it still has positive review.

anneschilling commented 12 years ago
comment:28

Since https://github.com/sagemath/sage-prod/issues/12969 just got merged into sage-5.3.beta0, please also apply the attachment trac12969_rel_5457.patch on the ticket 12969 to this patch. Otherwise there will be doctest failures.

Thanks,

Anne

anneschilling commented 12 years ago

Changed dependencies from #11563, #13109 to #11563, #13109, #12969

anneschilling commented 12 years ago

Description changed:

--- 
+++ 
@@ -40,3 +40,4 @@
 Apply
 * [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
 * [attachment: trac_5457-review-as.patch](https://github.com/sagemath/sage/files/ticket5457/trac_5457-review-as.patch.gz)
+* [attachment: trac12969_rel_5457.patch](https://github.com/sagemath/sage/files/ticket5457/trac12969_rel_5457.patch.gz)
jdemeyer commented 12 years ago
comment:31

This needs to be rebased to sage-5.3.beta0 (not yet released):

patching file sage/categories/realizations.py
Hunk #1 FAILED at 74
1 out of 1 hunks FAILED -- saving rejects to file sage/categories/realizations.py.rej
patching file sage/combinat/sf/classical.py
Hunk #3 FAILED at 88
1 out of 9 hunks FAILED -- saving rejects to file sage/combinat/sf/classical.py.rej
patching file sage/combinat/sf/sfa.py
Hunk #61 FAILED at 2589
1 out of 63 hunks FAILED -- saving rejects to file sage/combinat/sf/sfa.py.rej
abort: patch failed to apply
anneschilling commented 12 years ago

Description changed:

--- 
+++ 
@@ -39,5 +39,4 @@

 Apply
 * [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
-* [attachment: trac_5457-review-as.patch](https://github.com/sagemath/sage/files/ticket5457/trac_5457-review-as.patch.gz)
-* [attachment: trac12969_rel_5457.patch](https://github.com/sagemath/sage/files/ticket5457/trac12969_rel_5457.patch.gz)
+
anneschilling commented 12 years ago
comment:34

I rebased and folded the three patches with respect to sage-5.3.beta0 from yesterday. It should apply cleanly now.

Mike and I are still going to fix one math bug that someone at FPSAC found.

Anne

anneschilling commented 12 years ago
comment:35

Hi Dan,

Our new rebased patch is attached. You only need to apply trac_5457-symmetric_functions-mz.patch. Note that we did not fix apply_linear_morphism in /category/module_with_basis.py yet since Nicolas seems to have a review patch for this, but unfortunately his tests did not pass. Either he needs to fix his review patch or we will add your suggestion from the e-mail.

Anne

nthiery commented 12 years ago
comment:37

Note: I inserted in the queue the latest patch rebased for 5.3 beta0 from here. My review patch is also there, ready to be folded if you are happy with it.

anneschilling commented 12 years ago
comment:38

Dear Dan and Nicolas,

Thank you so much for your reviews and work on this patch! I incorporated the changes that Dan suggested by e-mail and folded Nicolas' review patch. In addition, Mike had some minor improvements in the documentation of llt.py which are incorporated.

The new patch should apply cleanly on sage-5.3.beta0.

Anne

anneschilling commented 12 years ago

Changed reviewer from Dan Bump, Franco Saliola to Dan Bump, Nicolas M. Thiery

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 12 years ago
comment:40

All tests pass with sage-5.3.beta0. The changes discussed over the last few days have all been incorporated. I think this is ready to go.

nthiery commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,42 +1,30 @@
 This patch restructures the implementation of symmetric functions in sage

-The new implementation makes use of multiple realizations and the category
-framework. The new access to symmetric functions is via
+The new implementation makes use of multiple realizations and the category framework. The new access to symmetric functions is via

sage: Sym = SymmetricFunctions(QQ)

-
 Further new features that are implemented:

-- The ring of symmetric functions is now endowed with a Hopf algebra structure.
-  The coproduct and antipode are implemented (which were missing before).
+* The ring of symmetric functions is now endowed with a Hopf algebra structure. The coproduct and antipode are implemented (which were missing before).

-- A tutorial on how to use symmetric functions in sage is included at the
-  beginning of sf.py which is also accessible via
+* A tutorial on how to use symmetric functions in sage is included at the beginning of sf.py which is also accessible via

sage: SymmetricFunctions??


-- Symmetric functions should now work a lot better with respect to 
-  specializing parameters like `q` and `t` for Hall-Littlewood, Jack
-  and Macdonald symmetric functions. Certain functionalities before
-  this change were broken or not possible.
+* Symmetric functions should now work a lot better with respect to  specializing parameters like `q` and `t` for Hall-Littlewood, Jack and Macdonald symmetric functions. Certain functionalities before this change were broken or not possible.

-- Documentation was added to LLT polynomials (which had very sparse documentation
-  previously).
+* Documentation was added to LLT polynomials (which had very sparse documentation previously).

-- The `k`-bounded subspace of the ring of symmetric function was implemented.
-  The `k`-Schur functions now live in the `k`-bounded subspace rather than
-  in the ring of symmetric functions as before.
+* The `k`-bounded subspace of the ring of symmetric function was implemented. The `k`-Schur functions now live in the `k`-bounded subspace rather than in the ring of symmetric functions as before.

-This patch gained tremendously by the tutorial on symmetric functions written
-by Jason Bandlow and Nicolas Thiery, a draft on the `k`-bounded subspace by
-Jason Bandlow, and code multiple realizations written by Franco Saliola.
+This patch gained tremendously by the tutorial on symmetric functions written by Jason Bandlow, a draft on the `k`-bounded subspace by Jason Bandlow, and code multiple realizations written by Franco Saliola.

 See also http://groups.google.com/group/sage-devel/msg/a49f3288fca1b75c

 Apply
+
 * [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
-
jdemeyer commented 12 years ago
comment:43

This fails on arando (32-bit i386 Linux):

sage -t --long "devel/sage/sage/combinat/sf/llt.py"
**********************************************************************
File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.3.beta1/devel/sage/sage/combinat/sf/llt.py", line 329:
    sage: cmp(L3Q, L3Z)
Expected:
    -1
Got:
    1
**********************************************************************
anneschilling commented 12 years ago

Description changed:

--- 
+++ 
@@ -28,3 +28,4 @@
 Apply

 * [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
+* [attachment: trac_5457_docfix-mz.patch](https://github.com/sagemath/sage/files/ticket5457/trac_5457_docfix-mz.patch.gz)
anneschilling commented 12 years ago
comment:45

Hi Jeroen,

Hmm, this is hard for us to check since we are not running our code on that operating system. We attached a patch which will hopefully fix the problem

Apply

Thanks,

Anne

jdemeyer commented 12 years ago

Changed reviewer from Dan Bump, Nicolas M. Thiery to Dan Bump, Nicolas M. Thiéry

jdemeyer commented 12 years ago
comment:48

I think one of the original reviewers should review this additional patch.

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 12 years ago
comment:49

I think one of the original reviewers should review this additional patch.

This adds a __cmp__ method for SymmetricFunctions, which was missing, and that was uncovered by the test in llt.py. Two SymmetricFunctions instances are compared equal if and only if they have the same base ring, which is as it should be.

Unless I'm missing something the patch is obviously correct. I ran --testall --long in the sf directory and all tests passed.

nthiery commented 12 years ago
comment:50

There is no compelling reason to have a cmp function for symmetric functions (nor its bases). The order has no meaning, and equality testing should be taken care of by UniqueRepresentation.

So altogether, I'd rather not add a cmp function, and instead would rather replace the failing test by:

sage: cmp(L3Q, L3Z) != 0

which is platform independent, and is all we care about. We could even just discard this test.

Now, I don't want to slow down the integration of this patch, so I am happy leaving this issue for a latter ticket, at the author's choice.

Cheers, Nicolas

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago
comment:51

As per Nicolas' suggestion, we are deleting the __cmp__ function from llt and moving and modifying the doctests elsewhere in the llt.py file.

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago
comment:52

This new patch deletes the function cmp from llt.py and inserts doctests into init in llt.py

d4d9e38a-6e64-40d7-a7f7-bd828eb9e0db commented 12 years ago

Description changed:

--- 
+++ 
@@ -28,4 +28,4 @@
 Apply

 * [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
-* [attachment: trac_5457_docfix-mz.patch](https://github.com/sagemath/sage/files/ticket5457/trac_5457_docfix-mz.patch.gz)
+* [attachment: trac_5457_docfix2-mz.patch](https://github.com/sagemath/sage/files/ticket5457/trac_5457_docfix2-mz.patch.gz)
anneschilling commented 12 years ago
comment:53

sage -testall passes on both mine and Mike's machine (both MacOS) with trac_5457-symmetric_functions-mz.patch and trac_5457_docfix2-mz.patch applied.

Dan and/or Nicolas, please set a positive review if you are happy with the changes.

Thanks!

Anne

6bbcde06-8197-41f1-b9a3-c998bb839000 commented 12 years ago
comment:54

Nicolas argued that there is no real reason for Sym to have a __cmp__ method and there is no reason for the test to be deterministic. We don't care if two rings or ring elements are > or < than each other, just whether they are distinct. Therefore the test that failed can be rewritten and the __cmp___ method is not needed.

This patch removes the __cmp__ method from llt polynomials instead of adding one for sf. In fact, SymmetricFunctions should not have had a __cmp__ method because it already inherits one from UniqueRepresentation. (Tested!) On the other hand, there is no reason for the test as previously written to be deterministic. So this is the correct approach.

anneschilling commented 12 years ago
comment:57

Thank you Dan for the review!

Anne

anneschilling commented 12 years ago

Description changed:

--- 
+++ 
@@ -28,4 +28,4 @@
 Apply

 * [attachment: trac_5457-symmetric_functions-mz.patch](https://github.com/sagemath/sage-prod/files/10643884/trac_5457-symmetric_functions-mz.patch.gz)
-* [attachment: trac_5457_docfix2-mz.patch](https://github.com/sagemath/sage/files/ticket5457/trac_5457_docfix2-mz.patch.gz)
+