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:

Status badges

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

  • Branch set to public/29325
  • Commit set to 32708d4b75de2341bd9d809d40d60a2b46cf7027
  • Status changed from new to needs_review

New commits:

33e4490set up permutahedron with precomputed data
32708d4fixing failing doctests due to reordering

comment:2 Changed 12 months ago by mkoeppe

  • 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 gh-kliem

  • Branch changed from public/29325 to public/29325-reb2
  • Commit changed from 32708d4b75de2341bd9d809d40d60a2b46cf7027 to 3174e62c2d5b0a66eee1204303eb3d90191697bc

New commits:

24f2a4aset up permutahedron with precomputed data
3174e62fixing failing doctests due to reordering

comment:4 Changed 11 months ago by jipilab

  • 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 gh-kliem

  • Branch changed from public/29325-reb2 to public/29325-reb3
  • Commit changed from 3174e62c2d5b0a66eee1204303eb3d90191697bc to 37f8c0d29581cc5568925c9b1f567ef4b3463c81
  • Status changed from needs_work to needs_review

New commits:

ddb39afset up permutahedron with precomputed data
5d2e748fixing failing doctests due to reordering
dd259d7tuple -> generator
37f8c0ddocumentated that backend field is fast

comment:6 Changed 11 months ago by jipilab

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

  • Commit changed from 37f8c0d29581cc5568925c9b1f567ef4b3463c81 to 29bb85b913d6583327bef43bbfb8202fa71760b4

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

29bb85bfix doctests

comment:8 Changed 11 months ago by 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:

29bb85bfix doctests

comment:9 Changed 11 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:10 Changed 9 months ago by mkoeppe

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

comment:11 Changed 8 months ago by mkoeppe

Needs rebase

comment:12 Changed 8 months ago by mkoeppe

  • Status changed from needs_review to needs_work

comment:13 Changed 8 months ago by gh-kliem

  • Branch changed from public/29325-reb3 to public/29325-reb4
  • Commit changed from 29bb85b913d6583327bef43bbfb8202fa71760b4 to 577e73606401e23f2677ddf553ecf9dfbebf3a4a
  • Status changed from needs_work to needs_review

New commits:

56d95ebset up permutahedron with precomputed data
2325e66fixing failing doctests due to reordering
aa1afe8tuple -> generator
b28e980documentated that backend field is fast
1bfcf5dfix doctests
577e736use test suite to check precomputed data

comment:14 Changed 8 months ago by 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...?

comment:15 Changed 8 months ago by 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.

comment:16 Changed 8 months ago by 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).

comment:17 Changed 8 months ago by mkoeppe

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

Ok then

comment:19 Changed 8 months ago by gh-kliem

Thank you.

comment:20 Changed 8 months ago by vbraun

  • Branch changed from public/29325-reb4 to 577e73606401e23f2677ddf553ecf9dfbebf3a4a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.