Opened 18 months ago
Closed 18 months ago
#28625 closed enhancement (fixed)
Let CombinatorialPolyhedron handle f_vector of polyhedra
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  geometry  Keywords:  
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Laith Rastanawi 
Report Upstream:  N/A  Work issues:  
Branch:  bf85a62 (Commits, GitHub, GitLab)  Commit:  bf85a62865c1a3da76857065169caa7754ba4cd8 
Dependencies:  #28621, #28607  Stopgaps: 
Description
CombinatorialPolyhedron
computes the f_vector
much faster than the current algorithm. In addition it is very memory efficient.
The goal of this ticket is to replace the method in Polyhedron_base
by the method in CombinatorialPolyedron
.
Here is a tiny example of the comparison:
sage: P = polytopes.permutahedron(6) sage: _ = P.incidence_matrix() sage: a = get_memory_usage() sage: %time P.f_vector() CPU times: user 8.19 s, sys: 4.46 ms, total: 8.19 s Wall time: 8.19 s (1, 720, 1800, 1560, 540, 62, 1) sage: get_memory_usage(a) 22.84765625 sage: a = get_memory_usage() sage: C = CombinatorialPolyhedron(P) sage: %time C.f_vector() CPU times: user 889 µs, sys: 14 µs, total: 903 µs Wall time: 905 µs (1, 720, 1800, 1560, 540, 62, 1) sage: get_memory_usage(a) 0.81640625
Change History (15)
comment:1 Changed 18 months ago by
 Component changed from PLEASE CHANGE to geometry
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 18 months ago by
 Status changed from new to needs_review
comment:3 Changed 18 months ago by
 Branch set to public/28625
 Commit set to acd671d2d21c0a2eda565d8f9281d88a1f046233
comment:4 Changed 18 months ago by
 Status changed from needs_review to needs_work
Running f_vector twice on truncated_dodecahedron will ignore the error and create a wrong f_vector
sage: tr = polytopes.truncated_dodecahedron(exact=False) warn("This polyhedron data is numerically complicated; cdd could not convert between the inexact V and H representation without loss of data. The resulting object might show inconsistencies.") sage: tr.f_vector()  ValueError Traceback (most recent call last) ... ValueError: not all vertices are intersections of facets sage: tr.f_vector() (1, 36, 57, 22, 1) sage: tr A 3dimensional polyhedron in RDF^3 defined as the convex hull of 60 vertices
comment:5 Changed 18 months ago by
 Commit changed from acd671d2d21c0a2eda565d8f9281d88a1f046233 to bf85a62865c1a3da76857065169caa7754ba4cd8
Branch pushed to git repo; I updated commit sha1. New commits:
bf85a62  subsequent calls for f_vector fail if first attempt fails

comment:6 Changed 18 months ago by
 Status changed from needs_work to needs_review
comment:7 Changed 18 months ago by
 Status changed from needs_review to positive_review
It looks good now.
comment:8 Changed 18 months ago by
 Reviewers set to Laith Rastanawi
comment:9 Changed 18 months ago by
missing author name
comment:10 Changed 18 months ago by
comment:11 followup: ↓ 12 Changed 18 months ago by
Just a comment. I have no idea where this was added due to the 1000 tickets:
raise ValueError("not all facets are joins of vertices")
This error message is very misleading. I would change this to something that does not use the word join. Usually, facet are convex hulls of vertices. Is this what fails here? If yes, then I would change it to that.
comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 18 months ago by
Replying to jipilab:
Just a comment. I have no idea where this was added due to the 1000 tickets:
raise ValueError("not all facets are joins of vertices")This error message is very misleading. I would change this to something that does not use the word join. Usually, facet are convex hulls of vertices. Is this what fails here? If yes, then I would change it to that.
give an error message for polytopes in some cases; removed incorrect example
It's an error message that was generated in CombinatorialPolyhedron
. Convex hull isn't really defined there. But I guess people get what it means.
Its a lot better than what we used to get. This was a very cryptic KeyError
in hasse diagram and it took me a while to figure out what the error message is supposed to tell us.
If you think it should be changed now, you can put this ticket, #28605, #28606 and #28614 on needs work, because there will be merge conflicts. Otherwise, we can always fix this later.
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 18 months ago by
Replying to ghkliem:
Replying to jipilab:
Just a comment. I have no idea where this was added due to the 1000 tickets:
raise ValueError("not all facets are joins of vertices")This error message is very misleading. I would change this to something that does not use the word join. Usually, facet are convex hulls of vertices. Is this what fails here? If yes, then I would change it to that.
give an error message for polytopes in some cases; removed incorrect example
It's an error message that was generated in
CombinatorialPolyhedron
. Convex hull isn't really defined there. But I guess people get what it means.Its a lot better than what we used to get. This was a very cryptic
KeyError
in hasse diagram and it took me a while to figure out what the error message is supposed to tell us.If you think it should be changed now, you can put this ticket, #28605, #28606 and #28614 on needs work, because there will be merge conflicts. Otherwise, we can always fix this later.
Please let the positively reviewed tickets get into a beta before trying to shove them all at once. It's simply impossible to review otherwise.
comment:14 in reply to: ↑ 13 Changed 18 months ago by
Replying to jipilab:
Replying to ghkliem:
Replying to jipilab:
Just a comment. I have no idea where this was added due to the 1000 tickets:
raise ValueError("not all facets are joins of vertices")This error message is very misleading. I would change this to something that does not use the word join. Usually, facet are convex hulls of vertices. Is this what fails here? If yes, then I would change it to that.
give an error message for polytopes in some cases; removed incorrect example
It's an error message that was generated in
CombinatorialPolyhedron
. Convex hull isn't really defined there. But I guess people get what it means.Its a lot better than what we used to get. This was a very cryptic
KeyError
in hasse diagram and it took me a while to figure out what the error message is supposed to tell us.If you think it should be changed now, you can put this ticket, #28605, #28606 and #28614 on needs work, because there will be merge conflicts. Otherwise, we can always fix this later.
Please let the positively reviewed tickets get into a beta before trying to shove them all at once. It's simply impossible to review otherwise.
I agree that it is a bit confusing. This ticket here has a total number of 7 commits and three of them belong to #28621 and #28607. I think this is doable.
As this ticket and #28605 conflict, we need to make one depend on the other. I just figured that this here is easier than #28605.
comment:15 Changed 18 months ago by
 Branch changed from public/28625 to bf85a62865c1a3da76857065169caa7754ba4cd8
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
added combinatorial polyhedron as an attribute for polyhedra
f_vector of CombinatorialPolyhedron is a vector
Merge branch 'public/28607' of git://trac.sagemath.org/sage into public/28621
used CombinatorialPolyhedron to compute f_vector
give an error message for polytopes in some cases; removed incorrect example
now we get a precice error message for inexact truncated dodecahedron