Opened 9 years ago
Closed 9 years ago
#14141 closed enhancement (fixed)
Implementation of Knutson-Tao puzzles
Reported by: | aschilling | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.10 |
Component: | combinatorics | Keywords: | puzzles, Littlewood-Richardson coefficiens, days45 |
Cc: | sage-combinat, saliola | Merged in: | sage-5.10.beta4 |
Authors: | Franco Saliola, Avinash Dalal, Anne Schilling | Reviewers: | Allen Knutson, Liz Beazley, Ed Richmond |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #14299 | Stopgaps: |
Description (last modified by )
This patch implements Knutson-Tao puzzles in various settings (Grassmannian, equivariant Grassmannian, K theoretic, Belkale-Kumar puzzles).
This code was written during Sage Days 45 at ICERM with Franco Saliola, Anne Schilling, and Avinash Dalal in discussions with Allen Knutson. The code was tested afterwards by Liz Beazley and Ed Richmond.
Apply:
Attachments (6)
Change History (45)
comment:1 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Allen Knutson, Liz Beazley, Ed Richmond
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 9 years ago by
comment:3 in reply to: ↑ 2 Changed 9 years ago by
Added documentation to rst file.
Anne
comment:4 follow-up: ↓ 5 Changed 9 years ago by
What version is this patch based on ? (It doesn't apply to sage-5.8.)
comment:5 in reply to: ↑ 4 Changed 9 years ago by
Replying to saliola:
What version is this patch based on ? (It doesn't apply to sage-5.8.)
For me it applies to sage-5.9.beta2.
comment:6 follow-up: ↓ 7 Changed 9 years ago by
some stupid suggestions:
- use .. TODO instead of just todo
- use the role
:arxiv:`xxxx.xxxx`
when citing a paper on arxiv
comment:7 in reply to: ↑ 6 Changed 9 years ago by
Frédéric, thank you for the comments. They should be fixed now. Currently, a more serious issue is the following that Liz observed:
sage: Hps = PuzzleSolver("H") sage: Hsolns = Hps('001001', '001010') sage: Puzz = Hsolns[0] sage: Puzz.LR_tab_from_puzzle() --------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-39-2284d874276b> in <module>() ----> 1 Puzz.LR_tab_from_puzzle() /Applications/sage-5.9.beta2/local/lib/python2.7/site-packages/sage/combinat/knutson_tao_puzzles.pyc in LR_tab_from_puzzle(self) 1629 for j in range(0,lam[k-1]): 1630 LRrow.append(None) -> 1631 LRrow.extend(self.path_thru_puzzle(i+1)) 1632 LRtableaux.append(LRrow) 1633 return SkewTableau(LRtableaux) /Applications/sage-5.9.beta2/local/lib/python2.7/site-packages/sage/combinat/knutson_tao_puzzles.pyc in path_thru_puzzle(self, coord) 1565 """ 1566 i = coord -> 1567 assert self._ne_labels[coord-1] == '1', "The coordinate needs to be a coordinate of a 1 on the north east boundary" 1568 j = self._n 1569 k = 0 AssertionError: The coordinate needs to be a coordinate of a 1 on the north east boundary
comment:8 follow-up: ↓ 9 Changed 9 years ago by
By the way, it would be better to avoid the use of assert.
comment:9 in reply to: ↑ 8 Changed 9 years ago by
Replying to chapoton:
By the way, it would be better to avoid the use of assert.
Well, it depends. If it's about checking the internal state of the program, asserts are *good*; we want more of them! If it's about checking the arguments provided directly by a user that's more arguable. See the discussion we had on sage-combinat-devel.
comment:10 follow-up: ↓ 16 Changed 9 years ago by
General comments on the patch:
- This patch has not been rebased: it fails to apply on 5.9.beta5 (and on 5.9.rc0 according to the patchbot).
- All tests pass on 5.9.beta5.
- some methods are missing
INPUT
blocks, some do not describe all the possible input arguments, some do not test all the possible input options
Comments on the interface:
- I don't think that
PuzzlePiece, PuzzlePieces, PuzzleSolver
should be imported into the global namespace. These names are too generic to apply to only KT puzzles. - Is it expected that the average user will create new puzzle pieces? or is it that
PuzzleSolver
will be the most used command? - I think it would be preferable to have one entry point to the module, from which users import what they need.
- And this entry point should have appropriate documentation describing all the features (kind of like the current documentation to the module, but with some enhancements).
- Perhaps
KnutsonTaoPuzzleSolver
?
Comments on documentation to the module (top of the file):
- If I do
import knutson_tao_puzzles
followed byknutson_tao_puzzles?
, I see1/0 0/1
as a puzzle piece. I don't know what this piece is. Is this a problem with the documentation rendering system? - The string representations should be explained: most people won't know what
1/0 0\1
means. - The
TODO
section describes a possible speed up. Isn't this what_fill_strip
and_fill_puzzle_by_strips
does?
Comments on PartialPuzzle
:
LR_tab_from_puzzle
is not a good name. Perhaps just call itskew_lr_tableau
.plot_thru_puzzle
is not a good name.thru
is not an English word.- the error from comment 7 above should be included as a doctest.
assert
should be avoided.partition_from_string
: I don't know what this method does. The documentation is not descriptive. What is the "string data" of a partition? If this is a standard partition constructor, then should it be inPartition
instead?
Comments on PuzzleSolver
:
- "Initialize the puzzle solver" is not a sufficient 1-line description since it doesn't mention the kind of puzzles dealt with.
- there is an option called 'maxLetter' in the INPUT section, but the init doesn't take maxLetter as an argument ... oh wait, it's in
__classcall_private__
. Why is__classcall_private__
needed here? - there should be doctests that show how to use "maxLetter"
- The output is not a function (but instances of the class happen to be callable).
- several methods are missing the mandatory 1-line string documentation and instead just include examples / tests.
Comments on SchubertCalculusAlgebra
:
- should this really be in this module? it seems to experimental (there is also some commented out code that shouldn't be included)
- it was implemented as a proof of concept and has no special features; perhaps it should be deleted and further developed in a separate patch?
- in the doctest for
product_on_basis
, the base ring of the algebra isQQ
, but the coefficients belong to a different ring:sage: from sage.combinat.knutson_tao_puzzles import SchubertCalculusAlgebra sage: Sc = SchubertCalculusAlgebra(QQ, (3,3)).basis() sage: x = Sc[Word('001011')] * Sc[Word('010101')] sage: x.parent().base_ring() Rational Field sage: x.coefficients()[0].parent() Multivariate Polynomial Ring in y0, y1, y2, y3, y4, y5, y6 over Integer Ring
Changed 9 years ago by
comment:11 follow-up: ↓ 14 Changed 9 years ago by
Oh, and I've attached a file that fixes plotting by colouring only the edges. Fold it if you like it.
comment:12 Changed 9 years ago by
I don't have the time to address my comments myself this week with a proper review patch, but I can at some point over the next week. There are a few things to decide beforehand, so we can at least discuss these here in the meantime.
comment:13 Changed 9 years ago by
- Description modified (diff)
comment:14 in reply to: ↑ 11 Changed 9 years ago by
Replying to saliola:
Oh, and I've attached a file that fixes plotting by colouring only the edges. Fold it if you like it.
Thanks, Franco! Up to a little tweak, I folded the patch and uploaded the new version on trac!
Anne
comment:15 Changed 9 years ago by
- Dependencies set to #14299
comment:16 in reply to: ↑ 10 Changed 9 years ago by
Replying to saliola:
General comments on the patch:
- This patch has not been rebased: it fails to apply on 5.9.beta5 (and on 5.9.rc0 according to the patchbot).
I think it depends trivially on #14299 which was merged in sage-5.10.beta0.
Comments on the interface:
- I don't think that
PuzzlePiece, PuzzlePieces, PuzzleSolver
should be imported into the global namespace. These names are too generic to apply to only KT puzzles.
How would the user then find information about puzzles? If we do not import anything in the namespace, then there is no entry point via tab completion.
- Is it expected that the average user will create new puzzle pieces? or is it that
PuzzleSolver
will be the most used command?
I think PuzzleSolver
will be the most common command. And currently the user does not have to create his/her own puzzle pieces since PuzzleSolver("H")
is an option. That's also why I think PuzzleSolver
should be in the global namespace.
- I think it would be preferable to have one entry point to the module, from which users import what they need.
- And this entry point should have appropriate documentation describing all the features (kind of like the current documentation to the module, but with some enhancements).
- Perhaps
KnutsonTaoPuzzleSolver
?
Sure, we could rename it this way.
Comments on documentation to the module (top of the file):
- If I do
import knutson_tao_puzzles
followed byknutson_tao_puzzles?
, I see1/0 0/1
as a puzzle piece. I don't know what this piece is. Is this a problem with the documentation rendering system?
I do not seem to see this!?
- The string representations should be explained: most people won't know what
1/0 0\1
means.- The
TODO
section describes a possible speed up. Isn't this what_fill_strip
and_fill_puzzle_by_strips
does?
Ok, then please remove this comment!
Comments on
PartialPuzzle
:
LR_tab_from_puzzle
is not a good name. Perhaps just call itskew_lr_tableau
.plot_thru_puzzle
is not a good name.thru
is not an English word.
Ok, feel free to change the names.
- the error from comment 7 above should be included as a doctest.
assert
should be avoided.partition_from_string
: I don't know what this method does. The documentation is not descriptive. What is the "string data" of a partition? If this is a standard partition constructor, then should it be inPartition
instead?
Yes, in fact you can do
sage: Partitions().from_zero_one([1, 1, 1, 1, 0, 1, 0]) [5, 4]
But I think the only problem is that one needs the partition to be padded by 0s.
Comments on
PuzzleSolver
:
- "Initialize the puzzle solver" is not a sufficient 1-line description since it doesn't mention the kind of puzzles dealt with.
- there is an option called 'maxLetter' in the INPUT section, but the init doesn't take maxLetter as an argument ... oh wait, it's in
__classcall_private__
. Why is__classcall_private__
needed here?
To mend the input, so that UniqueRepresentation? works!
- there should be doctests that show how to use "maxLetter"
- The output is not a function (but instances of the class happen to be callable).
- several methods are missing the mandatory 1-line string documentation and instead just include examples / tests.
I think private methods are not required to have the one line description.
Comments on
SchubertCalculusAlgebra
:
- should this really be in this module? it seems to experimental (there is also some commented out code that shouldn't be included)
Ed and Liz really liked this feature, to be able to compute structure coefficients in an easy way.
- it was implemented as a proof of concept and has no special features; perhaps it should be deleted and further developed in a separate patch?
- in the doctest for
product_on_basis
, the base ring of the algebra issage: from sage.combinat.knutson_tao_puzzles import SchubertCalculusAlgebra sage: Sc = SchubertCalculusAlgebra(QQ, (3,3)).basis() sage: x = Sc[Word('001011')] * Sc[Word('010101')] sage: x.parent().base_ring() Rational Field sage: x.coefficients()[0].parent() Multivariate Polynomial Ring in y0, y1, y2, y3, y4, y5, y6 over Integer Ring
That is indeed a problem!
I don't have the time to address my comments myself this week with a proper review patch, but I can at some point over the next week. There are a few things to decide beforehand, so we can at least discuss these here in the meantime.
I am looking forward to your review patch next week! I am moving back to Davis tomorrow, so won't have time either to work on this before your review patch.
comment:17 follow-up: ↓ 18 Changed 9 years ago by
I just pushed a micro review patch on the queue that fixes a documentation building error (an itemize which was improperly layed out). Feel free to fold or whatever, I won't touch it further.
comment:18 in reply to: ↑ 17 Changed 9 years ago by
Thanks, Nicolas! I folded the patch. Franco, could you post the review patch that you announced?
Changed 9 years ago by
comment:19 Changed 9 years ago by
- Description modified (diff)
comment:20 Changed 9 years ago by
Here is a patch that addresses almost all of the issues I raised above. The big changes are as follows:
- renamed
PuzzleSolver
toKnutsonTaoPuzzleSolver
- improved documentation for
KnutsonTaoPuzzleSolver
- renamed
PartialPuzzle
toPuzzleFilling
- moved
cohomology_product
toPuzzleSolver.structure_contstants
(this way it is more readily available to the user) - deleted
LR_tab_from_puzzle
(will be implemented in a future patch) - deleted
SchubertCalculusAlgebra
(will be implemented in a future patch)
Apply: trac_14141-knutson_tao_puzzles-as.patch, trac_14141-review-fs.patch
comment:21 follow-up: ↓ 22 Changed 9 years ago by
I just found a doctest that passes, but should fail:
sage: from sage.combinat.knutson_tao_puzzles import BK_pieces sage: BK_pieces(3) Nablas : [0\0/0, 1\1/1, 2\2/2, 3\3/3] Deltas : [0/0\0, 1/1\1, 2/2\2, 3/3\3]
Whoever added this code and doctest should explain what is going on.
And I included a doctest that fails: we need an example of a puzzle with BK pieces.
sage: ps = KnutsonTaoPuzzleSolver("BK", 3) sage: solns = ps('10212', '12012') sage: sorted(solns, key=str)
comment:22 in reply to: ↑ 21 Changed 9 years ago by
Hi Franco!
Thanks for your work on this!
I currently get one doctest failure
sage -t knutson_tao_puzzles.py ********************************************************************** File "knutson_tao_puzzles.py", line 1485, in sage.combinat.knutson_tao_puzzles.KnutsonTaoPuzzleSolver.__init__ Failed example: sorted(solns, key=str) Expected nothing Got: [] ********************************************************************** 1 item had failures: 1 of 40 in sage.combinat.knutson_tao_puzzles.KnutsonTaoPuzzleSolver.__init__ [342 tests, 1 failure, 0.42 s] ---------------------------------------------------------------------- sage -t knutson_tao_puzzles.py # 1 doctest failed ---------------------------------------------------------------------- Total time for all tests: 0.6 seconds cpu time: 0.3 seconds cumulative wall time: 0.4 seconds
I will have a closer look soon.
Best,
Anne
Changed 9 years ago by
comment:23 Changed 9 years ago by
Attached a patch to fix the issues with the BK puzzle pieces. Essentially, a for loop was not indented properly, so puzzle some BK pieces were missing.
Apply: trac_14141-knutson_tao_puzzles-as.patch, trac_14141-review-fs.patch, trac_14141-BK-fix-fs.patch
comment:24 follow-up: ↓ 25 Changed 9 years ago by
- Description modified (diff)
comment:25 in reply to: ↑ 24 ; follow-up: ↓ 26 Changed 9 years ago by
Hi Franco!
Thanks for the patches. I folded them and looked them over. One "major" change I made is to put the documentation that was in the init method of KnutsonTaoPuzzleSolver? in its header, so that it actually shows up in the documentation! Before it was invisible to the user from the documentation, but contained the explanation about the main use cases of the code. I also fixed some small issues with the referencing.
If you are happy with the changes, I am happy to set a positive review!
Anne
comment:26 in reply to: ↑ 25 Changed 9 years ago by
Fixed some issues with the documentation. Franco, are we ready to go?
Changed 9 years ago by
comment:27 follow-up: ↓ 28 Changed 9 years ago by
One more small patch that puts some examples of plotting in the documentation string for KnutsonTaoPuzzleSolver
.
I'm happy with the patch otherwise. Anne, if you accept my changes, fold it and set this to positive review.
Apply: trac_14141-knutson_tao_puzzles-as.patch, trac_14141-documentation-for-plotting-fs.patch
comment:28 in reply to: ↑ 27 Changed 9 years ago by
Great! I folded the patches and added one more item to the TODO list with a link to the (broken) implementation of the bijection from puzzles to tableaux on the misc server.
comment:29 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:30 follow-up: ↓ 31 Changed 9 years ago by
- Status changed from positive_review to needs_work
! Emergency stop. ... l.110743 .../2, 10\PYGZob{}/0, 10\PYGZcb{}(10)/2,} ! ==> Fatal error occurred, no output PDF file produced! Transcript written on combinat.log. ]] LaTeX Warning: Hyper reference `sage/modules/free_module_element:sage.modules.f ree_module_element.FreeModuleElement.nintegrate' on page 72 undefined on input line 6250. [72]make[1]: *** [combinat.pdf] Error 1
comment:31 in reply to: ↑ 30 ; follow-up: ↓ 32 Changed 9 years ago by
Replying to jdemeyer:
LaTeX Warning: Hyper reference `sage/modules/free_module_element:sage.modules.f ree_module_element.FreeModuleElement.nintegrate' on page 72 undefined on input line 6250. [72]make[1]: *** [combinat.pdf] Error 1
Just in case this can help: I was struck by this two days ago elsewhere, and it was just because I had forgotten to put a r in front of a documentation string containing '\'.
comment:32 in reply to: ↑ 31 ; follow-up: ↓ 34 Changed 9 years ago by
Just in case this can help: I was struck by this two days ago elsewhere, and it was just because I had forgotten to put a r in front of a documentation string containing '\'.
Ok, thanks! I added r""" in front of most documentation and removed a link to http which might have caused the problem.
Without more specific instructions on how to debug this, I am not sure what else to do.
Anne
comment:33 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:34 in reply to: ↑ 32 ; follow-up: ↓ 35 Changed 9 years ago by
Replying to aschilling:
Just in case this can help: I was struck by this two days ago elsewhere, and it was just because I had forgotten to put a r in front of a documentation string containing '\'.
Ok, thanks! I added r""" in front of most documentation and removed a link to http which might have caused the problem.
Without more specific instructions on how to debug this, I am not sure what else to do.
sage -docbuild all html sage -docbuild reference/combinat pdf
The first one resolves the various links. The second one should reproduce the error reported by Jeroen; or nothing if it has been fixed.
Cheers,
Nicolas
comment:35 in reply to: ↑ 34 Changed 9 years ago by
My changes did not fix the problem. What is the usual way to debug this?
comment:36 follow-up: ↓ 37 Changed 9 years ago by
I added r"""
to every documentation string and it worked for me. (Almost all of our documentation strings contain a \
.)
Thanks for your help, Nicolas.
I've attached the patch. It's ready for review. Anne, can you test it? Apply the patch and then run the following commands:
sage -b sage -docbuild all html sage -docbuild reference/combinat pdf
Changed 9 years ago by
Changed 9 years ago by
comment:37 in reply to: ↑ 36 Changed 9 years ago by
Thanks, Franco! I had to make one more change to make it all work!
Anne
comment:38 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:39 Changed 9 years ago by
- Merged in set to sage-5.10.beta4
- Resolution set to fixed
- Status changed from positive_review to closed
Hi Franco,
The patch is basically ready to go now. Could you please look over my changes? Also, there is one method which is currently broken (namely _plot_color_edges), which would still be good to have around.
Thanks!
Anne