Let CombinatorialPolyhedron handle f_vector of polyhedra

[kliem]

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

Depends on #28621
Depends on #28607

CC: @jplab @LaisRast

Component: geometry

Author: Jonathan Kliem

Branch/Commit: bf85a62

Reviewer: Laith Rastanawi

Issue created by migration from https://trac.sagemath.org/ticket/28625

[kliem]

Branch: public/28625

[kliem]

New commits:

b89610e	added combinatorial polyhedron as an attribute for polyhedra
326602c	f_vector of CombinatorialPolyhedron is a vector
dfbe2ad	Merge branch 'public/28607' of git://trac.sagemath.org/sage into public/28621
ed5518b	used CombinatorialPolyhedron to compute f_vector
9bdd005	give an error message for polytopes in some cases; removed incorrect example
acd671d	now we get a precice error message for inexact truncated dodecahedron

[kliem]

Commit: acd671d

[LaisRast]

comment:4

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

[sagetrac-git]

Changed commit from acd671d to bf85a62

[sagetrac-git]

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

bf85a62

subsequent calls for f_vector fail if first attempt fails

[LaisRast]

comment:7

It looks good now.

[LaisRast]

Reviewer: Laith Rastanawi

[fchapoton]

comment:9

missing author name

[kliem]

Author: Jonathan Kliem

[jplab]

comment:11

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.

[kliem]

comment:12

Replying to @jplab:

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.

[jplab]

comment:13

Replying to @kliem:

Replying to @jplab:

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.

[kliem]

comment:14

Replying to @jplab:

Replying to @kliem:

Replying to @jplab:

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.

[vbraun]

Changed branch from public/28625 to bf85a62