Opened 10 years ago
Closed 9 years ago
#14234 closed enhancement (fixed)
Restructuring Diagram/Partition Algebras to match category structure
Reported by: | George H. Seelinger | Owned by: | Alex Ghitza |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.12 |
Component: | algebra | Keywords: | Partition algebra, diagram algebra, days38, days40 |
Cc: | Aaron Lauve, Steve Doty, Franco Saliola | Merged in: | sage-5.12.beta3 |
Authors: | Stephen Doty, Aaron Lauve, George H. Seelinger | Reviewers: | Travis Scrimshaw, Darij Grinberg |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #10630 | Stopgaps: |
Description (last modified by )
Currently, the Partition/Diagram? Algebra implementations in Sage need to be redone. This problem was identified at Sage Days 38. The documentation is not very clear on how it should be used, and although it is supposed to be an algebra, it does not follow the standard form for algebras in Sage (most likely because these algebras have not been modified since 2007.)
This attached program seeks to provide an alternate implementation for, and eventually replace once dependencies are resolved, the existing PartionAlgebra package. More detail about these specific algebras can be found in a 2005 paper by Halverson and Ram titled "Partition Algebras." This new implementation restructures the Partition/Diagram? Algebras to use the category structure in Sage, so that they are actually implemented as Algebras_with_basis. The new implementation also provides much more detailed documentation on how to use the Partition Algebras, what they actually are, and provides an easier and more standard usage pattern (inherited from CombinatorialFreeModule.)
Apply:
Attachments (7)
Change History (36)
Changed 10 years ago by
Attachment: | 17710.patch added |
---|
comment:1 Changed 10 years ago by
Keywords: | days38 days40 added |
---|
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
I have a second revision on my computer that I am adding the finishing touches to. I will try to upload it in the following week. I have some ideas for pictorial representations using tikz, but the standard networkx and other drawing libraries are not powerful enough to make meaningful diagrams the same way sage does with other graphs. I wrote some code at one point in networkx to display them, but this ended up with issues when trying to create edges along the rows of diagrams, such as an edge between vertex 1 and vertex 3 (it looked the same as having edges {1,2},{2,3}). I will be sure to let you know when I need some formal review and I am glad your colleagues have found this patch useful. Thank you!
comment:4 Changed 10 years ago by
Even if the diagrams are not too clean pictorially in tikz, as long as the output is moderately easily parseable and the connectivity is there, I think that will be good. Anyways, just let me know when it's ready. Thanks.
Changed 10 years ago by
Attachment: | trac_14232_latexDrawing.patch added |
---|
comment:5 Changed 10 years ago by
I have added a new patch that I believe may need to be applied after the previous one has been. However, this patch *should* now allow for the generation of LaTeX code using TikZ to create diagrams for individual, basis diagrams. I have not changed any of the tests, however, so any tests that failed before will probably still fail.
comment:7 Changed 9 years ago by
I think the patch is ready for review. I'm sorry it took so long! Please let me know if more changes need to be made.
comment:8 Changed 9 years ago by
Reviewers: | → Travis Scrimshaw |
---|---|
Status: | new → needs_review |
I've set the ticket to needs_review and I'll write a review patch. I would like to know if there is a better name than IdealAlgebra
since that will likely cause some confusion (perhaps something that does not begin with Ideal
such as PartitionIdealAlgebra
)? I'll take care of this in the review patch as well. Also, you'll need to fill in your real names as the authors.
Thank you,
Travis
PS - No need to worry about the time delay. Thanks for getting this done.
comment:9 follow-up: 11 Changed 9 years ago by
Authors: | ghseeli, s.r.doty, alauve → Stephen Doty, Aaron Lauve, George H. Seelinger |
---|
Okay, here's my review patch. I changed IdealAlgebra
to IdealPartitionAlgebra
, which is (much) better but I'm not perfectly happy with. If you can think of a better name, then I'll change it. I've also reorganized the class structure to better use base classes and implemented a coercion up to the ambient space for the subalgebras. After that it's mostly docstring/doctest additions and corrections.
If you agree with my changes (and can't think of a better name), you can go ahead and set this to positive review. Thanks.
comment:10 Changed 9 years ago by
Description: | modified (diff) |
---|
For patchbot:
Apply: trac_14234_revision_for_5.10_compatibility.patch trac_14234-review-ts.patch
comment:11 Changed 9 years ago by
I talked to my co-authors and we seem to agree that "PropagatingIdeal?" might be a better name for a few reasons:
1) There are actually many ideals in the PartitionAlgebra?.
2) It is defined based on the propagating number of the diagrams.
3) It is technically a non-unital algebra, which makes calling it an algebra debatable amongst some circles.
Once this is done, I think this enhancement is good to go.
Replying to tscrim:
Okay, here's my review patch. I changed
IdealAlgebra
toIdealPartitionAlgebra
, which is (much) better but I'm not perfectly happy with. If you can think of a better name, then I'll change it. I've also reorganized the class structure to better use base classes and implemented a coercion up to the ambient space for the subalgebras. After that it's mostly docstring/doctest additions and corrections.If you agree with my changes (and can't think of a better name), you can go ahead and set this to positive review. Thanks.
comment:12 Changed 9 years ago by
Alright, the name has been changed (I like this one). Just needs one last lookover from you and you can set it to positive review. Thank you.
For patchbot:
Apply: trac_14234_revision_for_5.10_compatibility.patch trac_14234-review-ts.patch
comment:13 Changed 9 years ago by
Status: | needs_review → positive_review |
---|
comment:14 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:16 Changed 9 years ago by
Dependencies: | → #10630 |
---|
comment:18 Changed 9 years ago by
This is a very promising patch! Some errors I found:
An propogating ideal. A propogating ideal of rank `k` is a non-unital algebra with basis indexed by the collection of ideal set partitions of `\{1, \ldots, k, -1, \ldots, -k\}`. We say a set partition is ideal if its has propogating number is less than `k`. This algebra is thus a subalgebra of the partition algebra. For more information, see :class:`PartitionAlgebra`
I don't like this. First of all, it should be "propagating", not "propogating" (fortunately the method name is correct). Second, this should be "The", not "A", propagating ideal. Otherwise it sounds like some ideal generated by ideal partitions -- and there are many of those.
Actually I see the "propogating" typo elsewhere too. Also, a "with with" in the definition of ideal_diagrams
.
Also, typo: "ommitted".
I'm not very happy with the use of floats (as in "2.5") for the "intermediate" partition algebras. Is it safe to assume that, say, range(1,int(k+0.5))
always ends at k-0.5, or can it happen that k-0.5 is a tad smaller than an integer due to a rounding error and k-0.5 no longer falls in the interval?
There is a more serious issue with the intermediate algebras, and it's this (from your doctest):
sage: da.partition_diagrams(1.5) [{{2, -2}, {1, -1}}, {{-1}, {2, -2}, {1}}]
If I am to follow the Halverson-Ram conventions, this should contain three more partition diagrams, e. g., {{1, -1, 2, -2}}. Generally, they define a (k+1/2)-partition diagram, for k being an integer, to be any (k+1)-partition diagram in which k+1 and -k-1 lie in the same block (but don't need to be alone there). These are in bijections with set partitions of a fixed (2k+1)-element set. What you define, instead, bijects with set partitions of a 2k-element set, which is boring since these are already the k-partition diagrams.
Moreover, da.partition_diagrams(2)
returns a combinatorial class whereas da.partition_diagrams(1.5)
returns a list. I am a bit puzzled because this hardly intended behaviour is doctested for...
comment:19 Changed 9 years ago by
Status: | positive_review → needs_work |
---|
comment:20 Changed 9 years ago by
Another reason why floats are a bad thing:
sage: da.PartitionAlgebra(3+1/2, 1, QQ, 'part') == da.PartitionAlgebra(3+1/2, 1, QQ, 'part') True sage: da.PartitionAlgebra(3+1/2, 1, QQ, 'part') == da.PartitionAlgebra(3.5, 1, QQ, 'part') False
I think the code should use rationals, and floats in the input should be normalized to the nearest semi-integer.
Remove the word "with" from with propogating number less than
, since there is already a "with" on the preceding line.
There is a typo ("usualy") here:
Returns the product of two basis diagrams. Usually it is not called directly, but indirectly through usualy arithmetic operators.
but actually the word can be removed.
I think the docstrings should mention the fact that the partition-to-diagram correspondence is not 1-to-1, and diagrams are usually seen just as intuitive representations of set partitions, with several different diagrams corresponding to the same set partition.
Put "k" in backticks in The Brauer algebra of rank k
.
The docstring ambient returns the partition algebra the Brauer algebra is a sub-algebra of.
should be adjusted as it is defined not just for a Brauer algebra but for any subalgebra.
It seems to me that the SubPartitionAlgebra
docstring should say that the subalgebra is spanned by a subset of the basis of the partition algebra. Otherwise the code of the retract
method makes no sense.
comment:21 Changed 9 years ago by
There are two reasons why I left it as 0.5
instead of 1/2
, the first is that floor
is being called and it seemed somewhat troublesome to covert it to an integer, and the second is this what the old partition algebras used (which is why I didn't look too hard to getting around the first problem). Also IMO you're abusing the input with your ==
example, so it's an unfair test.
I think that da.partition_diagrams
is okay since its more of an internal helper function, but I'll change the output to be a list in both cases to match the output of the other such functions.
For the 0.5 +/- 0.5
, since there is no division being performed and they are specified floating points, their bit representations are the same and it's a power of two, so +/- are both okay (here). If it was say 0.1
added 10 times, then it's slightly more worrisome (but I think it's still okay...)
In any case, I'll look more deeply into seeing if I can convert this to using rationals, make sure the 1/2's are correct (and fix it if it's not), and fix those typos (including my spelling of propagate :P
).
Thanks for your comments Darij.
Best,
Travis
Changed 9 years ago by
Attachment: | trac_14234-review-ts.patch added |
---|
comment:22 Changed 9 years ago by
Status: | needs_work → needs_review |
---|
Hey Darij,
Here's the new version of the review patch with all of the changes. I wasn't very explicit/detailed with the docstring for SubPartitionAlgebra
since it's an internal (abstract) class. If you happy with my changes, go ahead and set this to positive review.
Best,
Travis
For patchbot:
Apply: trac_14234_revision_for_5.10_compatibility.patch, trac_14234-review-ts.patch
Changed 9 years ago by
Attachment: | trac_14234-microchange-dg.2.patch added |
---|
Changed 9 years ago by
Attachment: | trac_14234-microchange-dg.patch added |
---|
comment:23 Changed 9 years ago by
Hi Travis,
thanks, the issues are fixed. I've suggested a little improvement on the propagating ideal docstring in trac_14234-microchange-dg.patch which you're free to use or ignore. Basically I think it makes a lot more sense to think of it as an ideal than as a non-unital algebra.
Greets,
Darij
comment:24 Changed 9 years ago by
Status: | needs_review → positive_review |
---|
comment:25 Changed 9 years ago by
Reviewers: | Travis Scrimshaw → Travis Scrimshaw, Darij Grinberg |
---|
Thanks Darij.
Changed 9 years ago by
Attachment: | trac_14234_revision_for_5.10_compatibility.patch added |
---|
comment:26 Changed 9 years ago by
Description: | modified (diff) |
---|
Folded both patches since the folded patch is smaller than the original patch and smaller than the reviewer patch! Also added trac_14234-microchange-dg.patch which wasn't mentioned in the "Apply" block but I guess was meant to be merged anyway.
comment:27 Changed 9 years ago by
Status: | positive_review → needs_work |
---|
This AssertionError
should be fixed (you probably want to raise a ValueError
instead):
sage: sage.combinat.diagram_algebras.to_Brauer_partition([[1,2,3],[-1,-2]]) --------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-1-8bfe84be2a91> in <module>() ----> 1 sage.combinat.diagram_algebras.to_Brauer_partition([[Integer(1),Integer(2),Integer(3)],[-Integer(1),-Integer(2)]]) /mazur/release/merger/sage-5.12.beta1/local/lib/python2.7/site-packages/sage/combinat/diagram_algebras.pyc in to_Brauer_partition(l, k) 1419 L2.append(list(i)) 1420 for i in L2: -> 1421 assert len(i) < 3 1422 if (len(i) == 2): 1423 paired.append(i) AssertionError:
Changed 9 years ago by
Attachment: | trac_14234-folded-ts.patch added |
---|
comment:28 Changed 9 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → positive_review |
Here's the folded patch which replaces asserts with raising ValueError
s.
Sorry for not noticing that the microchange patch was not listed in the apply section.
For patchbot:
Apply: trac_14234-folded-ts.patch
comment:29 Changed 9 years ago by
Merged in: | → sage-5.12.beta3 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
This patch has been useful to some of my colleagues, and I would like to see it get into sage.
Currently I couldn't see how we could display the diagrams pictorially in latex, and I think it would be really cool if we could have the latex version of the elements as sums of the pictorial diagrams. There seemed to be a few functions missing some doctests. Let me know when this gets ready for a formal review. Thanks.