Opened 2 years ago
Closed 2 years ago
#29325 closed enhancement (fixed)
Set up permutahedron with both Vrep and Hrep (if backend supports it)
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  geometry  Keywords:  polytopes, precomputed data, permutahedron 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  JeanPhilippe 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 2 years ago by
 Branch set to public/29325
 Commit set to 32708d4b75de2341bd9d809d40d60a2b46cf7027
 Status changed from new to needs_review
comment:2 Changed 2 years ago by
 Milestone changed from sage9.1 to sage9.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 2 years ago by
 Branch changed from public/29325 to public/29325reb2
 Commit changed from 32708d4b75de2341bd9d809d40d60a2b46cf7027 to 3174e62c2d5b0a66eee1204303eb3d90191697bc
comment:4 Changed 2 years ago by
 Reviewers set to JeanPhilippe 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 2 years ago by
 Branch changed from public/29325reb2 to public/29325reb3
 Commit changed from 3174e62c2d5b0a66eee1204303eb3d90191697bc to 37f8c0d29581cc5568925c9b1f567ef4b3463c81
 Status changed from needs_work to needs_review
comment:6 Changed 2 years 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 2 years 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 2 years 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 2 years ago by
 Status changed from needs_work to needs_review
comment:10 Changed 2 years ago by
"not tested" seems like the right choice for this.
comment:11 Changed 2 years ago by
Needs rebase
comment:12 Changed 2 years ago by
 Status changed from needs_review to needs_work
comment:13 Changed 2 years ago by
 Branch changed from public/29325reb3 to public/29325reb4
 Commit changed from 29bb85b913d6583327bef43bbfb8202fa71760b4 to 577e73606401e23f2677ddf553ecf9dfbebf3a4a
 Status changed from needs_work to needs_review
comment:14 Changed 2 years 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 2 years 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 2 years 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 2 years ago by
 Reviewers changed from JeanPhilippe Labbé to JeanPhilippe Labbé, Matthias Koeppe
 Status changed from needs_review to positive_review
comment:18 Changed 2 years ago by
Ok then
comment:19 Changed 2 years ago by
Thank you.
comment:20 Changed 2 years ago by
 Branch changed from public/29325reb4 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