Opened 13 months ago
Closed 8 months ago
#29325 closed enhancement (fixed)
Set up permutahedron with both Vrep and Hrep (if backend supports it)
Reported by: | gh-kliem | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.2 |
Component: | geometry | Keywords: | polytopes, precomputed data, permutahedron |
Cc: | jipilab, gh-LaisRast | Merged in: | |
Authors: | Jonathan Kliem | Reviewers: | Jean-Philippe Labbé, Matthias Koeppe |
Report Upstream: | N/A | Work issues: | |
Branch: | 577e736 (Commits, GitHub, GitLab) | Commit: | 577e73606401e23f2677ddf553ecf9dfbebf3a4a |
Dependencies: | Stopgaps: |
Description
We set up the permutahedron with both Vrepresenation and Hrepresentation, if the backend supports it.
If the backend supports precomputed data (currently field
) this is much faster. Otherwise, this is a bit faster, as the Hrepresentation seems to be the better choice.
Before this ticket:
sage: %timeit P = polytopes.permutahedron(6) # using ppl 10 loops, best of 5: 56.5 ms per loop sage: %timeit P = polytopes.permutahedron(7) # using ppl 1 loop, best of 5: 1.57 s per loop
With this ticket:
sage: %timeit P = polytopes.permutahedron(6) # using ppl 10 loops, best of 5: 34.2 ms per loop sage: %timeit P = polytopes.permutahedron(7) # using ppl 1 loop, best of 5: 1.04 s per loop sage: %time P = polytopes.permutahedron(8, backend='field') CPU times: user 587 ms, sys: 20 ms, total: 607 ms Wall time: 607 ms sage: %time P = polytopes.permutahedron(9, backend='field') CPU times: user 5.08 s, sys: 248 ms, total: 5.33 s Wall time: 5.33 s
Note that field
is much slower than ppl
before this ticket and the timings are therefore omitted.
As the order of Vrepresentation and Hrepresentation changes, a lot of tests need to be fixed.
Change History (20)
comment:1 Changed 13 months ago by
- Branch set to public/29325
- Commit set to 32708d4b75de2341bd9d809d40d60a2b46cf7027
- Status changed from new to needs_review
comment:2 Changed 12 months ago by
- Milestone changed from sage-9.1 to sage-9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:3 Changed 12 months ago by
- Branch changed from public/29325 to public/29325-reb2
- Commit changed from 32708d4b75de2341bd9d809d40d60a2b46cf7027 to 3174e62c2d5b0a66eee1204303eb3d90191697bc
comment:4 Changed 11 months ago by
- Reviewers set to Jean-Philippe Labbé
- Status changed from needs_review to needs_work
These timings are interesting. Perhaps it would be good to add them to the documentation of the function? Since the backend field
performs well but isn't the default, it would be good to give this information in the documentation.
comment:5 Changed 11 months ago by
- Branch changed from public/29325-reb2 to public/29325-reb3
- Commit changed from 3174e62c2d5b0a66eee1204303eb3d90191697bc to 37f8c0d29581cc5568925c9b1f567ef4b3463c81
- Status changed from needs_work to needs_review
comment:6 Changed 11 months ago by
- Status changed from needs_review to needs_work
Failing doctests, see patchbot:
sage -t --long src/doc/en/thematic_tutorials/geometry/tips.rst ********************************************************************** File "src/doc/en/thematic_tutorials/geometry/tips.rst", line 110, in doc.en.thematic_tutorials.geometry.tips Failed example: print(P.Hrepresentation_str(style='<=')) Expected: -x0 - x1 - x2 == -6 x1 + x2 <= 5 x2 <= 3 x1 <= 3 -x1 <= -1 -x1 - x2 <= -3 -x2 <= -1 Got: -x0 - x1 - x2 == -6 -x0 - x1 <= -3 x0 + x1 <= 5 -x1 <= -1 x0 <= 3 -x0 <= -1 x1 <= 3 ********************************************************************** File "src/doc/en/thematic_tutorials/geometry/tips.rst", line 118, in doc.en.thematic_tutorials.geometry.tips Failed example: print(P.Hrepresentation_str(style='positive')) Expected: x0 + x1 + x2 == 6 5 >= x1 + x2 3 >= x2 3 >= x1 x1 >= 1 x1 + x2 >= 3 x2 >= 1 Got: x0 + x1 + x2 == 6 x0 + x1 >= 3 5 >= x0 + x1 x1 >= 1 3 >= x0 x0 >= 1 3 >= x1 **********************************************************************
---------------------------------------------------------------------- sage -t --long src/sage/schemes/cyclic_covers/charpoly_frobenius.py # 1 doctest failed sage -t --long src/sage/geometry/polyhedron/library.py # Bad exit: 1 sage -t --long src/doc/en/thematic_tutorials/geometry/tips.rst # 2 doctests failed ----------------------------------------------------------------------
comment:7 Changed 11 months ago by
- Commit changed from 37f8c0d29581cc5568925c9b1f567ef4b3463c81 to 29bb85b913d6583327bef43bbfb8202fa71760b4
Branch pushed to git repo; I updated commit sha1. New commits:
29bb85b | fix doctests
|
comment:8 Changed 11 months ago by
As for the bad exit it appears that memory consumption is highly unstable during doctesting. I can make it pass with 2400 MB and default is 3300 MB, so I would expect this to work anywhere, but I guess this is not the case. (And 2400 MB is much over what causes a bad exit for Sébastien Labbé).
I guess I just mark it as not tested. The examples are more for documentation than for testing.
New commits:
29bb85b | fix doctests
|
comment:9 Changed 11 months ago by
- Status changed from needs_work to needs_review
comment:10 Changed 9 months ago by
"not tested" seems like the right choice for this.
comment:11 Changed 8 months ago by
Needs rebase
comment:12 Changed 8 months ago by
- Status changed from needs_review to needs_work
comment:13 Changed 8 months ago by
- Branch changed from public/29325-reb3 to public/29325-reb4
- Commit changed from 29bb85b913d6583327bef43bbfb8202fa71760b4 to 577e73606401e23f2677ddf553ecf9dfbebf3a4a
- Status changed from needs_work to needs_review
comment:14 Changed 8 months ago by
these doctests that seem to depend on an unspecified order of enumeration... is there not a better way of testing this, for example by sorting...?
comment:15 Changed 8 months ago by
There is only a few doctests that can be fixed by sorting. The face iterator really behaves different with different order and the indices are all shuffled.
comment:16 Changed 8 months ago by
And the first ones cannot be fixed by this either. Looks like ppl
picks a different representative for the inequalities (that are modulo an equation).
comment:17 Changed 8 months ago by
- Reviewers changed from Jean-Philippe Labbé to Jean-Philippe Labbé, Matthias Koeppe
- Status changed from needs_review to positive_review
comment:18 Changed 8 months ago by
Ok then
comment:19 Changed 8 months ago by
Thank you.
comment:20 Changed 8 months ago by
- Branch changed from public/29325-reb4 to 577e73606401e23f2677ddf553ecf9dfbebf3a4a
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
set up permutahedron with precomputed data
fixing failing doctests due to reordering