Opened 11 months ago

Closed 7 months ago

#27760 closed enhancement (fixed)

Generalized Permutohedra and type H4 4-uniform polytopes

Reported by: jipilab Owned by:
Priority: major Milestone: sage-8.9
Component: geometry Keywords: polytopes, non-rational, normaliz, days100
Cc: Winfried, jipilab, mkoeppe, vdelecroix, tscrim Merged in:
Authors: Jean-Philippe Labbé Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: bd1fd21 (Commits) Commit: bd1fd21ddaaafde8329f72d4cf5346ca62656429
Dependencies: #25097 Stopgaps:

Description

One sort of generalized permutahedra consists in putting the starting point, which is usually taken inside the fundamental chamber, on the boundary of the fundamental chamber.

See https://arxiv.org/abs/1904.11029 for a recent related paper.

This ticket implements the generalized permutahedra and on the way, adds the fifteen H4 4-uniform polytopes.

See https://en.wikipedia.org/wiki/H4_polytope for a list of them.

Many of them are quite large and can only be computed in reasonable time using the backend normaliz.

Change History (40)

comment:1 Changed 11 months ago by jipilab

  • Dependencies set to #25097

comment:2 Changed 11 months ago by git

  • Commit changed from 1c7f84829ad8a935c604c5ffca4c9853d345d7b3 to a546fba42858cf107d3ac8222bb344ba5b87e354

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

a546fbaAdded names on top

comment:3 Changed 11 months ago by git

  • Commit changed from a546fba42858cf107d3ac8222bb344ba5b87e354 to 91c43a6d4d5a6754f68b3545f7607eeecabec217

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

91c43a6Made the H4 types regular

comment:4 Changed 11 months ago by git

  • Commit changed from 91c43a6d4d5a6754f68b3545f7607eeecabec217 to ef9faa917285478733b83c55955c70e63dd5c5a8

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

57d9b7dStarted fixing regularity
ef9faa9Fixed the regular construction

comment:5 Changed 11 months ago by git

  • Commit changed from ef9faa917285478733b83c55955c70e63dd5c5a8 to 8056264544948bd04c28a8c309d0b4647f784022

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

8056264Fixed typo in docstring

comment:6 Changed 10 months ago by embray

  • Milestone sage-8.8 deleted

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

comment:7 Changed 9 months ago by git

  • Commit changed from 8056264544948bd04c28a8c309d0b4647f784022 to a6a545236166505c1094ca49500e6f2ba85b66ac

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

cce2590Merge branch 'develop' into h4_polytopes
0c5b8d9Fix py3 code and tests for Sage8.9beta3
d66f7e2pep8
a6a5452fixed some doctests

comment:8 Changed 9 months ago by git

  • Commit changed from a6a545236166505c1094ca49500e6f2ba85b66ac to 71fbfdf8df8a66fbe7d7a9431be7097f1006a2ae

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

71fbfdfFixed a test

comment:9 Changed 9 months ago by jipilab

  • Keywords days100 added
  • Status changed from new to needs_review

comment:10 follow-up: Changed 9 months ago by chapoton

apparemment, la doc ne compile pas, voir patchbot

comment:11 in reply to: ↑ 10 Changed 9 months ago by jipilab

Replying to chapoton:

apparemment, la doc ne compile pas, voir patchbot

Hm, all right. I'm on it!

comment:12 Changed 9 months ago by git

  • Commit changed from 71fbfdf8df8a66fbe7d7a9431be7097f1006a2ae to d4260a6749d6ccd7e6a30266dfc1fbbbd00c91c3

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

d4260a6trivial doc fix

comment:13 Changed 9 months ago by jipilab

  • Milestone set to sage-8.9

comment:14 Changed 9 months ago by git

  • Commit changed from d4260a6749d6ccd7e6a30266dfc1fbbbd00c91c3 to 95d6bdad88dac7435d6a1df890a8420fd70c9e47

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

95d6bdafix coding in library

comment:15 Changed 9 months ago by chapoton

  • missing the word 'polytope' here, I think:
    The runcitruncated 600-cell is a 4-dimensional 4-uniform in the `H_4`
    

and the same in all the examples.

  • Here, you could remove the []
    sum([adjusted_col[j]**2 for j in range(n) if j != i])
    

apart from that, ready to go..

comment:16 Changed 9 months ago by git

  • Commit changed from 95d6bdad88dac7435d6a1df890a8420fd70c9e47 to 5971228039a778b2ad7bc697ead1e30215f8c76c

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

5971228Added 'polytope' and fixed sum

comment:17 Changed 9 months ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, good to go

comment:18 Changed 9 months ago by jipilab

Merci!

comment:19 Changed 8 months ago by vbraun

  • Status changed from positive_review to needs_work

This dies on most 32-bit buildbots:

sage: perm_b3 = polytopes.generalized_permutahedron(['B',3]); perm_b3 ## line 2324 ##
A 3-dimensional polyhedron in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3 defined as the convex hull of 48 vertices
sage: perm_b3_reg = polytopes.generalized_permutahedron(['B',3],regular=True); perm_b3_reg # long time - 12sec. ## line 2326 ##
------------------------------------------------------------------------
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x5f22)[0xf5fbdf22]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x5fc6)[0xf5fbdfc6]
/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/cysignals/signals.so(+0x76e5)[0xf5fbf6e5]
linux-gate.so.1(__kernel_sigreturn+0x0)[0xf77b6ca0]
/home/buildbot/slave/sage_git/build/local/lib/libgmp.so.23(__gmpn_mul_basecase+0x83)[0xf6cabd4b]
------------------------------------------------------------------------
Attaching gdb to process id 20319.
Cannot find gdb installed
GDB is not installed.
Install gdb for enhanced tracebacks.
------------------------------------------------------------------------
**********************************************************************
----------------------------------------------------------------------
sage -t --long src/sage/geometry/polyhedron/library.py  # Timed out
----------------------------------------------------------------------

comment:20 Changed 8 months ago by git

  • Commit changed from 5971228039a778b2ad7bc697ead1e30215f8c76c to a1ad959ee22b50880c56165c4a140f7861b92e1d

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

a1ad959Made a doctest not tested due to time

comment:21 Changed 8 months ago by jipilab

  • Status changed from needs_work to needs_review

comment:22 Changed 8 months ago by chapoton

  • Status changed from needs_review to positive_review

ok, let us try again

comment:23 follow-up: Changed 8 months ago by vbraun

  • Status changed from positive_review to needs_work
**********************************************************************
File "src/sage/geometry/polyhedron/library.py", line 2324, in sage.geometry.polyhedron.library.Polytopes.generalized_permutahedron
Failed example:
    perm_b3 = polytopes.generalized_permutahedron(['B',3]); perm_b3
Expected:
    A 3-dimensional polyhedron in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3 defined as the convex hull of 48 vertices
    A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices
Got:
    A 3-dimensional polyhedron in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3 defined as the convex hull of 48 vertices
**********************************************************************
1 item had failures:
   1 of  21 in sage.geometry.polyhedron.library.Polytopes.generalized_permutahedron
    [240 tests, 1 failure, 156.68 s]
----------------------------------------------------------------------
sage -t --long src/sage/geometry/polyhedron/library.py  # 1 doctest failed
----------------------------------------------------------------------

comment:24 in reply to: ↑ 23 Changed 8 months ago by jipilab

Replying to vbraun:

**********************************************************************
File "src/sage/geometry/polyhedron/library.py", line 2324, in sage.geometry.polyhedron.library.Polytopes.generalized_permutahedron
Failed example:
    perm_b3 = polytopes.generalized_permutahedron(['B',3]); perm_b3
Expected:
    A 3-dimensional polyhedron in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3 defined as the convex hull of 48 vertices
    A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices
Got:
    A 3-dimensional polyhedron in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3 defined as the convex hull of 48 vertices
**********************************************************************
1 item had failures:
   1 of  21 in sage.geometry.polyhedron.library.Polytopes.generalized_permutahedron
    [240 tests, 1 failure, 156.68 s]
----------------------------------------------------------------------
sage -t --long src/sage/geometry/polyhedron/library.py  # 1 doctest failed
----------------------------------------------------------------------

I have trouble figuring out how this failure occurred.

The expected block is not as the attached branch would predict. Namely, the second line is absent. I merged the last version of develop into this ticket and made a test on my machine and I got:

jplabbe@blackbomb:~/sage/src/sage/geometry/polyhedron$ sage -t library.py 
Using --optional=4ti2,bliss,build,dochtml,e_antic,gfortran,latte_int,lidia,lrslib,memlimit,ninja_build,normaliz,pynormaliz,python2,sage,topcom
Doctesting 1 file.
sage -t library.py
    [305 tests, 77.99 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 78.1 seconds
    cpu time: 78.0 seconds
    cumulative wall time: 78.0 seconds

I get 305 tests in total. Would it be possible to get more feedback on how this failing doctest occurred? (which optional packages were used?)

comment:25 Changed 8 months ago by git

  • Commit changed from a1ad959ee22b50880c56165c4a140f7861b92e1d to cc1a6ab69c73e33d31bc161b487f909e33cd7921

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

cc1a6abMerge branch 'develop' into h4_polytopes

comment:26 Changed 8 months ago by jipilab

  • Status changed from needs_work to needs_review

comment:27 Changed 8 months ago by jipilab

Let's have another run of bots to see if the problem still occurs. This failure is strange.

comment:28 Changed 8 months ago by chapoton

patchbot reports another failure

comment:29 Changed 8 months ago by git

  • Commit changed from cc1a6ab69c73e33d31bc161b487f909e33cd7921 to b67e0c53e5afa3d1ed36deddc44ce78743c6bc0a

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

b67e0c5Added missing not tested tag

comment:30 Changed 8 months ago by jipilab

Found it.

It was a missing tag from fixing comment 19. Should be good to go now...

comment:31 follow-ups: Changed 7 months ago by chapoton

Adding tags on the results of doctests make no sense.

This does not fix the patchbot failure.

comment:32 in reply to: ↑ 31 Changed 7 months ago by jipilab

Replying to chapoton:

Adding tags on the results of doctests make no sense.

This does not fix the patchbot failure.

That's what I thought at first too!

But then, that's the only way I can make sense of seeing

Expected:
    A 3-dimensional polyhedron in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3 defined as the convex hull of 48 vertices
    A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices

which are two distinct consecutive outputs of test, the second of which is not tested. I was thinking that it might preparse the string and remove the not tested things and thus the expected block would now consist of two lines.

Otherwise, I have no clue how come the expected block would consist of two lines, it is simply not as the source entails!?

Puzzled.

comment:33 in reply to: ↑ 31 Changed 7 months ago by jipilab

Replying to chapoton:

Adding tags on the results of doctests make no sense.

This does not fix the patchbot failure.

From the patch bot shortog, the following information is a bit obscure:

Expected:
    There are 7 tests in sage/combinat/finite_state_machine.py that are not being run
    There are 3 unexpected tests being run in sage/doctest/parsing.py
    There are 1 unexpected tests being run in sage/doctest/reporting.py
    There are 3 tests in sage/rings/invariants/invariant_theory.py that are not being run
Got:
    There are 7 tests in sage/combinat/finite_state_machine.py that are not being run
    There are 3 unexpected tests being run in sage/doctest/parsing.py
    There are 1 unexpected tests being run in sage/doctest/reporting.py
    There are 1 unexpected tests being run in sage/geometry/polyhedron/library.py
    There are 3 tests in sage/rings/invariants/invariant_theory.py that are not being run
**********************************************************************

I guess it is the same test that causes a problem, but I have no output to inspect. Also, I am curious, what is an "unexpected test"? It's the first time I see such a thing.

comment:34 follow-up: Changed 7 months ago by git

  • Commit changed from b67e0c53e5afa3d1ed36deddc44ce78743c6bc0a to cc1a6ab69c73e33d31bc161b487f909e33cd7921

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

comment:35 in reply to: ↑ 34 Changed 7 months ago by jipilab

Replying to git:

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

I removed the unless tag on the doctest result...

comment:36 follow-up: Changed 7 months ago by chapoton

Apparemment, ce qui pose problème est le fait que l'annotation contienne "64-bits".

comment:37 Changed 7 months ago by git

  • Commit changed from cc1a6ab69c73e33d31bc161b487f909e33cd7921 to bd1fd21ddaaafde8329f72d4cf5346ca62656429

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

bd1fd21fix details

comment:38 Changed 7 months ago by chapoton

  • Status changed from needs_review to positive_review

ok, let us try again

comment:39 in reply to: ↑ 36 Changed 7 months ago by jipilab

Replying to chapoton:

Apparemment, ce qui pose problème est le fait que l'annotation contienne "64-bits".

Wow. I see. Good to know. It looks like it's passing the test now at least.

comment:40 Changed 7 months ago by vbraun

  • Branch changed from public/uniform_H4_polytopes to bd1fd21ddaaafde8329f72d4cf5346ca62656429
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.