Opened 10 years ago
Closed 9 years ago
#13240 closed enhancement (fixed)
Give posets polynomials (order, characteristic, zeta, etc.)
Reported by: | csar | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | combinatorics | Keywords: | sd40, days45 |
Cc: | kdilks | Merged in: | sage-5.13.beta2 |
Authors: | Alex Csar, Kevin Dilks, Frédéric Chapoton | Reviewers: | Darij Grinberg, Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Adding some of the polynomials from Stembridge's Posets package for Maple (see http://www.math.lsa.umich.edu/~jrs/software/posetshelp.html), namely:
- characteristic polynomial (done)
- zeta polynomial (done)
- flag f-polynomial (done)
- flag h-polynomial (done)
- f-polynomial (done)
- h-polynomial (done)
- order polynomial (done)
- chain polynomial (done)
- W-polynomial
- antichain polynomial
apply:
Attachments (6)
Change History (47)
comment:1 Changed 10 years ago by
- Summary changed from Give posets polynomails (order, characteristic, zeta, etc.) to Give posets polynomials (order, characteristic, zeta, etc.)
comment:2 Changed 9 years ago by
- Keywords days45 added
comment:3 Changed 9 years ago by
comment:4 Changed 9 years ago by
I have added the flag f-vector
comment:5 Changed 9 years ago by
I have added the flag h-polynomial
comment:6 Changed 9 years ago by
I have added the characteristic polynomial
comment:7 Changed 9 years ago by
- Description modified (diff)
comment:8 Changed 9 years ago by
I think we have code from Sage Days 45 for the order polynomial (which is one line once you have zeta), the antichain polynomial and the chain polynomial.
comment:9 Changed 9 years ago by
great ! could you post it here as a patch on top of mine ?
comment:10 Changed 9 years ago by
Will do. I'm compiling sage at the moment, but I should be able to do it sometime this evening (GMT -6).
Note several hours later: compiling took way longer than expected. Will add to the patch tomorrow.
comment:11 Changed 9 years ago by
The patch didn't apply. I'm pretty sure it's a problem on my end and my installation is still messed up. I'll add things when I get it fixed.
comment:12 Changed 9 years ago by
Okay, I've added the chain polynomial and the order polynomial. We had something written for the antichain polynomial, but I didn't include it as I wanted to check with Kevin if he knew a better way of doing it like he worked out for the chain polynomial.
The chain polynomial is written so you can ask for it in terms of something other than q. So, for example, P.chain_polynomial(1)
would give you the chain polynomial evaluated at one. Obviously, things should be consistent as to whether you get to choose the variable, but it's a minor change to go either direction.
I made a second patch on top of yours because I wasn't sure if I should be making a separate one or just adding to the patch, and combining them shouldn't be hard.
comment:13 Changed 9 years ago by
- Description modified (diff)
Yes, it is better to upload a patch that applies on top of mine.
I will have a closer look at your code soon.
comment:14 Changed 9 years ago by
- Description modified (diff)
ok, here is a short review patch of your code.
I have removed trailing whitespaces that you had introduced, and made small changes to the code. I have also made sure that each method starts with a brief (one-line) description of what it does. Details are then given on other lines.
I would prefer not to propose the use of another variable in the code, but rather give no option. The user will get a polynomial, that he can then evaluate on whatever he wants. I think this keeps the code cleaner and shorter.
Combining patches is indeed easy, and can be done just once when everything is ready.
comment:15 Changed 9 years ago by
- Cc kdilks added
comment:16 Changed 9 years ago by
maybe we could stop here adding other polynomials, and try to let this set of polynomials enter sage ?
comment:17 Changed 9 years ago by
apply trac_1324O_first_step-fc.patch, trac_12340_poset_polynomials-csar.patch, trac_13240-review1-fc.patch
comment:18 Changed 9 years ago by
- Status changed from new to needs_review
comment:19 follow-up: ↓ 20 Changed 9 years ago by
- Status changed from needs_review to needs_work
Hello !
Would it be possible to add definitions of what these polynomials are, possibly as links toward wikipedia pages ?
I also think that you should cache minimal and maximal elements in the code of remove_top_and_bottom
, otherwise you compute the maximal and minimal elements for each vertex :
sage: def a(): ....: print "Hey" ....: return [1] ....: sage: [x for x in range(5) if x in a()] Hey Hey Hey Hey Hey [1]
Hence if you want to write this function, this really should not be computed so many times.
Besides : you only implement this method for bounded posets, which means that there is one max and one min elements. Hence this complicated line only checks that each vertex is different from two given vertices.
I personally do not think that this remove_top_and_bottom
method is useful, especially when it build a copy of the whole poset, which can be very costly. You would probably save yourself a lot of time if you worked on self
in each of your methods, and just ignored the top and bottom elements. No copies of the poset, no call to remove_to_and_bottom
either.
Oh, and Florent thinks that it would be nice to add "seealso" sections toward "is_bounded", or toward polynomials that are related with each other.
See youuuuuuuuuuuuuuuuUU !!
Nathann
comment:20 in reply to: ↑ 19 Changed 9 years ago by
I'm not actually sure there are definitions on Wikipedia for any/some/most of these (I took a quick look and didn't find any). But one could include references to EC1.
comment:21 Changed 9 years ago by
Here is a new patch
I have tried to adress some of the points raised by Nathan:
- I have got rid of remove_top_and_bottom, but introduced chains_with_bounds
There remains to explain the definition of every polynomial, and give the references to EC1
comment:22 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
Changed 9 years ago by
comment:23 Changed 9 years ago by
apply trac_1324O_first_step-fc.patch,trac_12340_poset_polynomials-csar.patch,trac_13240-review1-fc.patch
comment:24 Changed 9 years ago by
I have added a few more reference to Enum. Comb. 1
comment:25 Changed 9 years ago by
Maybe this ticket can be considered good enough ?
One patchbot has turned green, so there is an opportunity right now.
comment:26 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:27 Changed 9 years ago by
Helooooooo !
There still isn't any definition of what f_polynomial
and h_polynomial
return. Also, I personally do not think that a function named "chains with bounds" should exist (and so I will let somebody else give a positive review to this ticket), but in any case if you want to implement such a thing I'd think better to do it the following way :
- create a copy of the poset without the top/bottom element
- list its chains
- return each of them after adding the top and bottom element at each end of the chain.
Nathann
comment:28 follow-up: ↓ 29 Changed 9 years ago by
Hello Nathann,
well, chains_with_bounds
has been written to try to cope with your previous comments, that suggested to avoid copying the poset. And now you suggest to copy the poset..
Would it be better to make chains_with_bounds
a hidden method ?
comment:29 in reply to: ↑ 28 Changed 9 years ago by
well,
chains_with_bounds
has been written to try to cope with your previous comments, that suggested to avoid copying the poset. And now you suggest to copy the poset..
Well, yes. The best way out is to not copy the poset, to not call the .chains()
method, and to rewrite what chains()
does directly on this poset, ignoring the top/bottom elements on the fly. There's no need to copy.
Though if you want to call this chains()
method you will enumerate 4 times too many things chains, and you need *each time* to check if the two vertices belong to the list (by the way, you already know WHERE in the list they will appear if they do, so you can save time there too).
Would it be better to make
chains_with_bounds
a hidden method
What about making it an option of "chains" ?
Nathann
Changed 9 years ago by
comment:30 Changed 9 years ago by
Hello Nathann,
thanks for spending time on this ticket.
I have removed chains_with_bounds
, instead adding a parameter exclude
to the method chains
.
I have also added more documentation.
comment:31 Changed 9 years ago by
Wow ! It sure looks cleaner this way :-)
I don't see anything wrong in this patch right now... Though I'm a bit embarassed because I don't understand the maths at all, and it would be nice if somebody could just check that the polynomials are indeed what they should be ^^;
Nathann
comment:32 Changed 9 years ago by
The csar patch applied with fuzz for me (5.13beta0):
applying trac_12340_poset_polynomials-csar.patch patching file sage/combinat/posets/posets.py Hunk #1 succeeded at 28 with fuzz 1 (offset 0 lines). Hunk #2 succeeded at 84 with fuzz 2 (offset 5 lines).
The file I'm uploading in a few seconds is just a qfold so that I get a better view of the changes myself.
Changed 9 years ago by
UPDATED! everything reviewed, except for the two flag_* functions which I don't really understand nor can find a reference for.
comment:33 Changed 9 years ago by
Thanks, Nathan, for alerting me to this patch!
The file I just attached gives a review of everything but the two flag polynomials (f and h) which I couldn't find in literature. Please give a reference or a full definition (how exactly are those monomials built from the ranks etc.).
#13223 notwithstanding, I've replaced the hyperpolynomial-time is_graded
method by a polynomial-time (and memory) one. Speed comparisons:
before:
sage: B2 = Posets.BooleanLattice(2) sage: %timeit B2.is_graded() 10000 loops, best of 3: 84.9 us per loop sage: B3 = Posets.BooleanLattice(3) sage: %timeit B3.is_graded() 10000 loops, best of 3: 195 us per loop sage: B4 = Posets.BooleanLattice(4) sage: %timeit B4.is_graded() 1000 loops, best of 3: 663 us per loop sage: B5 = Posets.BooleanLattice(5) sage: %timeit B5.is_graded() 100 loops, best of 3: 2.86 ms per loop sage: B6 = Posets.BooleanLattice(6) sage: %timeit B6.is_graded() 100 loops, best of 3: 16 ms per loop sage: B7 = Posets.BooleanLattice(7) sage: %timeit B7.is_graded() 10 loops, best of 3: 109 ms per loop sage: P = Poset({1: [2, 3], 3: [4, 5], 2: [6]}) sage: %timeit P.is_graded() 10000 loops, best of 3: 103 us per loop sage: C = Poset([list(B7) + [1337], B7.cover_relations() + [[127, 1337]]]) sage: %timeit C.is_graded() 10 loops, best of 3: 146 ms per loop
after:
sage: B2 = Posets.BooleanLattice(2) sage: %timeit B2.is_graded() 10000 loops, best of 3: 82.3 us per loop sage: B3 = Posets.BooleanLattice(3) sage: %timeit B3.is_graded() 10000 loops, best of 3: 149 us per loop sage: B4 = Posets.BooleanLattice(4) sage: %timeit B4.is_graded() 1000 loops, best of 3: 290 us per loop sage: B5 = Posets.BooleanLattice(5) sage: %timeit B5.is_graded() 1000 loops, best of 3: 525 us per loop sage: B6 = Posets.BooleanLattice(6) sage: %timeit B6.is_graded() 1000 loops, best of 3: 1.02 ms per loop sage: B7 = Posets.BooleanLattice(7) sage: %timeit B7.is_graded() 100 loops, best of 3: 2.07 ms per loop sage: P = Poset({1: [2, 3], 3: [4, 5], 2: [6]}) sage: %timeit P.is_graded() 10000 loops, best of 3: 108 us per loop sage: C = Poset([list(B7) + [1337], B7.cover_relations() + [[127, 1337]]]) sage: %timeit C.is_graded() 100 loops, best of 3: 2.14 ms per loop
Also I have optimized the polynomial-computing methods (apart from the ones I don't understand) by letting them work with the _hasse_diagram
of the poset rather than the poset itself, because all methods that are used (minimal elements, top, Moebius etc.) currently work by calling the corresponding methods on the Hasse diagram and then relabelling vertices back. This also fixes the issue of chain_polynomial
throwing errors if the poset wasn't labelled 0,1,...,n (one of the doctests I made checks for this now).
Probably someone will have to review my review...
for the patchbots:
apply trac_13240-qfold.patch trac_13240-almost-review-dg.patch
comment:34 Changed 9 years ago by
Yooooooooooooooo !!
Well, all I can understand makes sense ! It was nice to merge these calls to is_bounded
and getting the top/bottom elements in particular. It could even become an optional argument eventually : p.is_bounded(if_it_is_bounded_return_top_and_bottom_not_true=True)
:-)
Thaaaaaaaanks Darij !
Nathann
comment:35 Changed 9 years ago by
Thanks Darij, for your review patch.
Your review looks good to me.
concerning flag f-vector and flag h-vector, there is something here : http://en.wikipedia.org/wiki/H-vector#Flag_h-vector_and_cd-index
It can also probably go through the hasse diagram.
comment:36 Changed 9 years ago by
Hi Frederic,
I've completed my review, editing again all four f/h-polynomials (flag and usual). Please check that:
1) the definitions I've added to the docstring are correct (I have deduced them from the implementation, except for the size-1 poset case which I just found had to give 1 for reasons of consistency);
2) all four methods return what they should in the case of a poset with 1 vertex (this is doctested, but I don't know if it's what you want);
3) you really want the flag h-polynomial to be returned as a polynomial over QQ, even if it has integer coefficients.
If these are fine, feel free to set this to positive review!
for the patchbot:
apply trac_13240-qfold.patch trac_13240-review2-dg.patch
comment:37 Changed 9 years ago by
- Description modified (diff)
comment:38 Changed 9 years ago by
- Reviewers set to Darij Grinberg, Nathann Cohen
comment:39 Changed 9 years ago by
Thanks Darij,
I will have a serious look later today.
for the patchbots (beware of invisible characters when copy pasting!)
apply trac_13240-qfold.patch trac_13240-review2-dg.patch
comment:40 Changed 9 years ago by
- Status changed from needs_review to positive_review
ok, I am happy enough with the current patch. Positive review !
:)
comment:41 Changed 9 years ago by
- Merged in set to sage-5.13.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
A first patch, with three of the simplest polynomials