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

[gh-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.

[gh-kliem]

New commits:

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

[mkoeppe]

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.

[gh-kliem]

New commits:

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

[jipilab]

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.

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

[jipilab]

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

[git]

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

​29bb85b

fix doctests

[gh-kliem]

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]

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

[mkoeppe]

Needs rebase

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

[mkoeppe]

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

[gh-kliem]

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.

[gh-kliem]

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]

Ok then

[gh-kliem]

Thank you.