Set up permutahedron with both Vrep and Hrep (if backend supports it)

[kliem]

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.

CC: @jplab @LaisRast

Component: geometry

Keywords: polytopes, precomputed data, permutahedron

Author: Jonathan Kliem

Branch/Commit: 577e736

Reviewer: Jean-Philippe Labbé, Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/29325

[kliem]

New commits:

33e4490	set up permutahedron with precomputed data
32708d4	fixing failing doctests due to reordering

[kliem]

Commit: 32708d4

[kliem]

Branch: public/29325

[mkoeppe]

comment: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.

[kliem]

Changed commit from 32708d4 to 3174e62

[kliem]

New commits:

24f2a4a	set up permutahedron with precomputed data
3174e62	fixing failing doctests due to reordering

[kliem]

Changed branch from public/29325 to public/29325-reb2

[jplab]

Reviewer: Jean-Philippe Labbé

[jplab]

comment:4

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.

[kliem]

Changed branch from public/29325-reb2 to public/29325-reb3

[kliem]

New commits:

ddb39af	set up permutahedron with precomputed data
5d2e748	fixing failing doctests due to reordering
dd259d7	tuple -> generator
37f8c0d	documentated that backend field is fast

[kliem]

Changed commit from 3174e62 to 37f8c0d

[jplab]

comment:6

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
----------------------------------------------------------------------

[sagetrac-git]

Changed commit from 37f8c0d to 29bb85b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

29bb85b

fix doctests

[kliem]

comment:8

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

[mkoeppe]

comment:10

"not tested" seems like the right choice for this.

[mkoeppe]

comment:11

Needs rebase

[kliem]

Changed commit from 29bb85b to 577e736

[kliem]

New commits:

56d95eb	set up permutahedron with precomputed data
2325e66	fixing failing doctests due to reordering
aa1afe8	tuple -> generator
b28e980	documentated that backend field is fast
1bfcf5d	fix doctests
577e736	use test suite to check precomputed data

[kliem]

Changed branch from public/29325-reb3 to public/29325-reb4

[mkoeppe]

comment:14

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...?

[kliem]

comment:15

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.

[kliem]

comment:16

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).

[mkoeppe]

Changed reviewer from Jean-Philippe Labbé to Jean-Philippe Labbé, Matthias Koeppe

[mkoeppe]

comment:18

Ok then

[kliem]

comment:19

Thank you.

[vbraun]

Changed branch from public/29325-reb4 to 577e736