#13240: Give posets polynomials (order, characteristic, zeta, etc.)
------------------------------------------+-----------------------------
Reporter: csar | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.13
Component: combinatorics | Resolution:
Keywords: sd40, days45 | Merged in:
Authors: Alex Csar, Kevin Dilks | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
------------------------------------------+-----------------------------
Comment (by darij):
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...
--
Ticket URL: <http://trac.sagemath.org/ticket/13240#comment:33>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
