Implement wedge over a face of Polyhedron

[jplab]

From ​​https://www.csun.edu/~ctoth/Handbook/chap15.pdf:

The wedge over a facet F of a polytope P is defined as:

(P \times \mathbb{R}) \cap \{a^\top x +|x_{d+1}| \leq b\}

where F is a facet defined by a^\top x leq b.

It has dimension d+1, m+1 facets, and 2n-n_F vertices, if F has n_F vertices. More generally, the wedge construction can be performed (defined by the same formula) for a face F.

CC: @jplab @LaisRast @kliem

Component: geometry

Keywords: polytopes, days100, wedge, facet

Author: Laith Rastanawi, Jonathan Kliem

Branch/Commit: 38944ad

Reviewer: Jean-Philippe Labbé

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

[embray]

comment:2

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).

[jplab]

Changed keywords from polytopes to polytopes, days100

[LaisRast]

New commits:

d0be5c6	add wedge method in Polyhedron class in base.py
45bd312	NotImplementedError -> ValueError

[LaisRast]

Commit: 45bd312

[LaisRast]

Author: Laith Rastanawi

[LaisRast]

Changed keywords from polytopes, days100 to polytopes, days100, wedge, facet

[LaisRast]

Branch: public/27973

[jplab]

comment:6

Hi,

• In the docstring, it usually starts with 1 sentence, and empty line and then further information about the method.

• I would say that the width is a "indication of how wide the wedge is taken around the face". Said the current way, it makes it confusing about other potential notions around polytopes (lattice polytopes have widths...) So I would say: "indication of how wide the resulted wedge should be".

• The doctests are not using the function as a method.

• Replace the backtick by single quotes in the error messages.

• L = Polyhedron(rays=[[1],[-1]]) could be Polyhedron(lines=[[1]])

• I would write F_Hrep = list(F_Hrep) after the for loop and replace in the creation of the polytope.

• It would be good to test and show in examples combinatorial isomorphism type with a known polytope which is a wedge. For example the prism over a triangle is a wedge over a triangle. And the duals to cyclic 3-polytopes are wedges.

[sagetrac-git]

Changed commit from 45bd312 to 049e27d

[sagetrac-git]

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

049e27d

more examples and fix docstring

[LaisRast]

comment:9

Replying to @jplab:

Thanks. Done.

[jplab]

comment:10

Seems like there are tab character in reference/index.rst There seems to be many errors in the bot too...

[sagetrac-git]

Changed commit from 049e27d to 193e06b

[sagetrac-git]

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

193e06b

tabs to spaces

[kliem]

comment:12

The description of the ticket is still only about facets.

[kliem]

comment:13

Please preserve the backend and base ring as in #27926.

[kliem]

comment:45

The problem is not float. A float is going to change backend to cdd, which is fine.

Let P with parent Polyhedra_normaliz_ZZ and Q with parent Polyhedra_ppl_QQ then coercion will lead the intersection to be an element of Polyhedra_ppl_QQ, because there is a map in exactly one direction.

Hence, intersection might change the backend (it might prefer backend of self or other depending on the involved rings).
However, I would expect a user to create all polyhedra with his preferred backend, so that shouldn't cause issues.

Now, if we create a polyhedron H with default backend (and not what the user chose as backend of self) this might cause the backend to change. I think one could only prevent this by not using coercion for intersection.

[jplab]

comment:46

Now, if we create a polyhedron H with default backend (and not what the user chose as backend of self) this might cause the backend to change. I think one could only prevent this by not using coercion for intersection.

I thought that the solution since the beginning is to query the backend of selfand apply it to H. If it fails, well this is a bad day for the user, because the backend will have to change whatsoever, due to the type of input, which we should trust is what the user wants.

Hence, try to create H with the backend of self, it is fails, just create H using the type of the given width.

I would let intersection alone here and still trust it to do what is right when the time comes.

In the end, that the backend is not preserved by an operation which is not intended to, is not the end of the world. Is it?

[kliem]

comment:47

Replying to @jplab:

Now, if we create a polyhedron H with default backend (and not what the user chose as backend of self) this might cause the backend to change. I think one could only prevent this by not using coercion for intersection.

I thought that the solution since the beginning is to query the backend of selfand apply it to H. If it fails, well this is a bad day for the user, because the backend will have to change whatsoever, due to the type of input, which we should trust is what the user wants.

Hence, try to create H with the backend of self, it is fails, just create H using the type of the given width.

This is exactly what base_extend does. It changes the parent as little as possible. Of course you can also use the constructor with try and except, which is what base_extend does (but cached).

I would let intersection alone here and still trust it to do what is right when the time comes.

It will always prefer the backend of the polyhedron with larger ring due to coercion.

In the end, that the backend is not preserved by an operation which is not intended to, is not the end of the world. Is it?

It is a pain, if it could have been prevented. If working with large polyhedra, which are manageable with normaliz and take forever with ppl you don't want the backend to change.

To ask a user to to base_extend before wedge over face is very sudle.

[kliem]

comment:48

By the way, I don't really care how one initialized H. I just think it should have the backend of self if width admits it.

[jplab]

comment:49

Replying to @kliem:

Replying to @jplab:

Now, if we create a polyhedron H with default backend (and not what the user chose as backend of self) this might cause the backend to change. I think one could only prevent this by not using coercion for intersection.

I thought that the solution since the beginning is to query the backend of selfand apply it to H. If it fails, well this is a bad day for the user, because the backend will have to change whatsoever, due to the type of input, which we should trust is what the user wants.

Hence, try to create H with the backend of self, it is fails, just create H using the type of the given width.

This is exactly what base_extend does. It changes the parent as little as possible. Of course you can also use the constructor with try and except, which is what base_extend does (but cached).

Ok, fine. But I would not do this business with 1/width, etc.

I would let intersection alone here and still trust it to do what is right when the time comes.

It will always prefer the backend of the polyhedron with larger ring due to coercion.

In the end, that the backend is not preserved by an operation which is not intended to, is not the end of the world. Is it?

It is a pain, if it could have been prevented. If working with large polyhedra, which are manageable with normaliz and take forever with ppl you don't want the backend to change.

Obviously.

To ask a user to to base_extend before wedge over face is very sudle.

Sudle? I am not sure to understand what you mean. Do you have any concrete suggestion for the code now?

[kliem]

comment:50

Replying to @jplab:

Replying to @kliem:

Replying to @jplab:
To ask a user to to base_extend before wedge over face is very sudle.

Sudle? I am not sure to understand what you mean. Do you have any concrete suggestion for the code now?

In many cases polyhedra will by default be set up with base ring ZZ like in

sage: P = polytopes.simplex(backend='normaliz'); type(P)
<class 'sage.geometry.polyhedron.parent.Polyhedra_ZZ_normaliz_with_category.element_class'>

If a user wants to keep his backend and we ask him to change the base ring to QQ before doing wedge over face, this is confusing.

[jplab]

comment:51

A few comments:

• In the docstring indicates how wide the resulted wedge should be: I would say: This parameter specifies how wide the wedge will be.

• A (bounded) Polyhedron object -> A (bounded) polyhedron

• Please provide me a simple argument as to why the field of fraction of the base ring should be used "by default" (i.e. when the width is 1). I would say that the resulting base ring should be determined by the constructor. Yes, this will depend on the input polytope, which is fine. Further, yes, the backend should be preserved if possible, which simply means that one should pass it to the constructor. What do I see wrong?

Because we are using Q.intersection(H), on top of what is done before, it is going to do a coercion to find the appropriate thing to do. I do not really understand why we force the parent of H to be the fraction field if it might not be necessary.

• The text inside of the TEST is misleading since even if we give a different value to width, the base ring will change. ... so again, I am confused about how this is done. Further, the tests should provide a bit more demonstration as to how it preserves the backend (please show at least how it preserves 2 backends, with appropriate base rings).

[kliem]

comment:52

Replying to @jplab:

A few comments:

• In the docstring indicates how wide the resulted wedge should be: I would say: This parameter specifies how wide the wedge will be.

• A (bounded) Polyhedron object -> A (bounded) polyhedron

• Please provide me a simple argument as to why the field of fraction of the base ring should be used "by default" (i.e. when the width is 1). I would say that the resulting base ring should be determined by the constructor. Yes, this will depend on the input polytope, which is fine. Further, yes, the backend should be preserved if possible, which simply means that one should pass it to the constructor. What do I see wrong?

I agree that is makes no sense to use the field of fractions, when width is 1. I guess we should use the field of fractions whenever width is not a unit.

If we just pass the backend to the constructor, we get an error if the value of width is not handled by the current backend. Is this the desired behavior? If you don't like the current setup, we can also just use does_backend_handle_base_ring from parent.py (its basically a cached version of doing try ... except for the constructor).

[jplab]

comment:53

Replying to @kliem:

Replying to @jplab:

A few comments:

• In the docstring indicates how wide the resulted wedge should be: I would say: This parameter specifies how wide the wedge will be.

• A (bounded) Polyhedron object -> A (bounded) polyhedron

• Please provide me a simple argument as to why the field of fraction of the base ring should be used "by default" (i.e. when the width is 1). I would say that the resulting base ring should be determined by the constructor. Yes, this will depend on the input polytope, which is fine. Further, yes, the backend should be preserved if possible, which simply means that one should pass it to the constructor. What do I see wrong?

I agree that is makes no sense to use the field of fractions, when width is 1. I guess we should use the field of fractions whenever width is not a unit.

If we just pass the backend to the constructor, we get an error if the value of width is not handled by the current backend. Is this the desired behavior?

I guess not.

If you don't like the current setup, we can also just use does_backend_handle_base_ring from parent.py (its basically a cached version of doing try ... except for the constructor).

Yes, to me that's probably the best intermediate to proceed this way and let the intersection deal with the rest.

[kliem]

comment:54

Merged with newest develop.

---

New commits:

73dac03

add wedge method in Polyhedron class in base.py

[kliem]

Changed branch from public/27973 to public/27973-new

[kliem]

Changed commit from 6ba5594 to 73dac03

[sagetrac-git]

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

38944ad

simplified construction of H, small changes mostly in the documentation

[sagetrac-git]

Changed commit from 73dac03 to 38944ad

[kliem]

comment:56

Tried to simplify construction of H.

Btw, I also tried to preserve the base_ring (when width is 1), but this did not work for the test in line 4205.

[jplab]

comment:57

The sentence:

+        The base_ring will change to the field of fractions of the current
+        base_ring, unless width forces a different ring.

is still confusing as it says that the base ring always will change to the field of fractions. What if it stays as ZZ? (which is possible). This should be fixed...

The rest seems to be good.

[kliem]

comment:58

Replying to @jplab:

The sentence:

+        The base_ring will change to the field of fractions of the current
+        base_ring, unless width forces a different ring.

is still confusing as it says that the base ring always will change to the field of fractions. What if it stays as ZZ? (which is

I don't think so. H is constructed from inequalities without specifying the basering. In this case the constructor coerces the base rings of all values and then takes the fraction field. If you want ZZ as basering when constructing a polyhedron from inequalities, you need to specify it for the constructor.

This should be fixed...

The rest seems to be good.

[jplab]

comment:59

Replying to @kliem:

Replying to @jplab:

The sentence:

+        The base_ring will change to the field of fractions of the current
+        base_ring, unless width forces a different ring.

is still confusing as it says that the base ring always will change to the field of fractions. What if it stays as ZZ? (which is

I don't think so. H is constructed from inequalities without specifying the basering. In this case the constructor coerces the base rings of all values and then takes the fraction field. If you want ZZ as basering when constructing a polyhedron from inequalities, you need to specify it for the constructor.

Ok... fine.

[kliem]

comment:60

Is this good to go now?

[jplab]

Changed author from Laith Rastanawi to Laith Rastanawi, Jonathan Kliem

[jplab]

Reviewer: Jean-Philippe Labbé

[vbraun]

Changed branch from public/27973-new to 38944ad