#28625 closed enhancement (fixed)

Let CombinatorialPolyhedron handle f_vector of polyhedra

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.0
Component: geometry Keywords:
Cc: jipilab, gh-LaisRast 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:

Status badges

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 jipilab

  • Component changed from PLEASE CHANGE to geometry
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 18 months ago by gh-kliem

  • Status changed from new to needs_review

comment:3 Changed 18 months ago by gh-kliem

  • Branch set to public/28625
  • Commit set to acd671d2d21c0a2eda565d8f9281d88a1f046233

New commits:

b89610eadded combinatorial polyhedron as an attribute for polyhedra
326602cf_vector of CombinatorialPolyhedron is a vector
dfbe2adMerge branch 'public/28607' of git://trac.sagemath.org/sage into public/28621
ed5518bused CombinatorialPolyhedron to compute f_vector
9bdd005give an error message for polytopes in some cases; removed incorrect example
acd671dnow we get a precice error message for inexact truncated dodecahedron

comment:4 Changed 18 months ago by gh-LaisRast

  • 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 3-dimensional polyhedron in RDF^3 defined as the convex hull of 60 vertices

comment:5 Changed 18 months ago by git

  • Commit changed from acd671d2d21c0a2eda565d8f9281d88a1f046233 to bf85a62865c1a3da76857065169caa7754ba4cd8

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

bf85a62subsequent calls for f_vector fail if first attempt fails

comment:6 Changed 18 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:7 Changed 18 months ago by gh-LaisRast

  • Status changed from needs_review to positive_review

It looks good now.

comment:8 Changed 18 months ago by gh-LaisRast

  • Reviewers set to Laith Rastanawi

comment:9 Changed 18 months ago by chapoton

missing author name

comment:10 Changed 18 months ago by gh-kliem

  • Authors set to Jonathan Kliem

comment:11 follow-up: Changed 18 months ago by 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.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 18 months ago by gh-kliem

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 ; follow-up: Changed 18 months ago by jipilab

Replying to gh-kliem:

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

Replying to jipilab:

Replying to gh-kliem:

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.

Last edited 18 months ago by gh-kliem (previous) (diff)

comment:15 Changed 18 months ago by vbraun

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