# Implement wedge over a face of Polyhedron

Reported by: Owned by: jipilab major sage-8.9 geometry polytopes, days100, wedge, facet jipilab, gh-LaisRast, gh-kliem Laith Rastanawi, Jonathan Kliem Jean-Philippe Labbé N/A 38944ad 38944ad77e0a7ca760e97fcef85f2b957fe83eba

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.

### comment:1 Changed 22 months ago by gh-kliem

• Description modified (diff)

### comment:2 Changed 22 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:4 Changed 21 months ago by gh-LaisRast

• Authors set to Laith Rastanawi
• Branch set to public/27973
• Commit set to 45bd3123afcafe3ef142e19bbb04f0d6ebda849e
• Status changed from new to needs_info

New commits:

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

### comment:5 Changed 21 months ago by gh-LaisRast

• Status changed from needs_info to needs_review

### comment:6 Changed 21 months ago by jipilab

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.

### comment:7 follow-up: ↓ 9 Changed 21 months ago by jipilab

• Status changed from needs_review to needs_work

### comment:8 Changed 21 months ago by git

• Commit changed from 45bd3123afcafe3ef142e19bbb04f0d6ebda849e to 049e27d49147ebf269a0d3267ae0dd32c1637e42

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

 ​049e27d more examples and fix docstring

### comment:9 in reply to: ↑ 7 Changed 21 months ago by gh-LaisRast

• Status changed from needs_work to needs_review

Thanks. Done.

### comment:10 Changed 21 months ago by jipilab

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

### comment:11 Changed 21 months ago by git

• Commit changed from 049e27d49147ebf269a0d3267ae0dd32c1637e42 to 193e06bd91b8cd16d8ec796fcae0ac91ee8b592a

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

 ​193e06b tabs to spaces

### comment:12 follow-up: ↓ 15 Changed 21 months ago by gh-kliem

The description of the ticket is still only about facets.

### comment:13 Changed 21 months ago by gh-kliem

• Status changed from needs_review to needs_work

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

### comment:14 follow-up: ↓ 16 Changed 21 months ago by gh-kliem

Actually, I think the backend might be preserved. (product and intersection might behave this way).

However, in the intermediate steps you don't preserve the backend. This might cause issues with algebraic polyhedra.

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

### comment:15 in reply to: ↑ 12 Changed 21 months ago by jipilab

The description of the ticket is still only about facets.

Nope. See last sentence of the description.

### comment:16 in reply to: ↑ 14 ; follow-up: ↓ 18 Changed 21 months ago by gh-LaisRast

Actually, I think the backend might be preserved. (product and intersection might behave this way).

However, in the intermediate steps you don't preserve the backend. This might cause issues with algebraic polyhedra.

The backend and the basering are preserved as long as the value of width belongs to the basering of self. This is the case when width takes the default value. Otherwise, we have the following behavior

sage: P = polytopes.cyclic_polytope(3,7); P
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 7 vertices
sage: P.backend()
'ppl'
sage: P.wedge(P.faces(2)[0]).backend()
'ppl'
sage: P.wedge(P.faces(2)[0]).base_ring()
Rational Field
sage: P.wedge(P.faces(2)[0], width=RDF(1)).backend()
cdd
sage: P.wedge(P.faces(2)[0], width=RDF(1)).base_ring()
Real Double Field


which I think is an acceptable behavior.

### comment:17 Changed 21 months ago by git

• Commit changed from 193e06bd91b8cd16d8ec796fcae0ac91ee8b592a to 417bfac337f17e93494d8f31b9031f9311cee423

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

 ​417bfac add tests to check backend and basering

### comment:18 in reply to: ↑ 16 ; follow-ups: ↓ 19 ↓ 21 Changed 21 months ago by gh-kliem

The examples you gave are not meaningful. ppl and cdd are the standard backends for the given ring.

What about normaliz with base ring ZZ and width 5/2 (even worse 4/2)? (I suspect backend will not be preserved).

What about the examples of #25097. Do they work?

(Sorry, still can't test it myself).

Actually, I think the backend might be preserved. (product and intersection might behave this way).

However, in the intermediate steps you don't preserve the backend. This might cause issues with algebraic polyhedra.

The backend and the basering are preserved as long as the value of width belongs to the basering of self. This is the case when width takes the default value. Otherwise, we have the following behavior

sage: P = polytopes.cyclic_polytope(3,7); P
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 7 vertices
sage: P.backend()
'ppl'
sage: P.wedge(P.faces(2)[0]).backend()
'ppl'
sage: P.wedge(P.faces(2)[0]).base_ring()
Rational Field
sage: P.wedge(P.faces(2)[0], width=RDF(1)).backend()
cdd
sage: P.wedge(P.faces(2)[0], width=RDF(1)).base_ring()
Real Double Field


which I think is an acceptable behavior.

### comment:19 in reply to: ↑ 18 ; follow-up: ↓ 20 Changed 21 months ago by gh-LaisRast

What about normaliz with base ring ZZ and width 5/2 (even worse 4/2)? (I suspect backend will not be preserved).

What about the examples of #25097. Do they work?

(Sorry, still can't test it myself).

The polyhedron H is the responsible for changing the base ring and the backend. The following should fix the problem (up to change of base ring form ZZ to QQ, see W2 below):

-    def wedge(self, face, width=1):
+    def wedge(self, face, width=None):
r"""
Return the wedge over a face of the polytope self.

@@ -4205,6 +4205,10 @@ class Polyhedron_base(Element):
sage: P.wedge(P.faces(2)[0], width=RDF(1)).base_ring()
Real Double Field
"""
+        if width is None:
+            width = ZZ.one()
+
if not self.is_compact():
raise ValueError("polyhedron 'self' must be a polytope")

@@ -4223,7 +4227,11 @@ class Polyhedron_base(Element):

L = Polyhedron(lines=[[1]])
Q = self.product(L)
-        H = Polyhedron(ieqs=[F_Hrep + [width], F_Hrep + [-width]])
+
+        parent = self.parent().base_extend(width, ambient_dim=self.ambient_dim()+1)
+        ieqs = [F_Hrep + [width], F_Hrep + [-width]]
+        H = parent.element_class(parent, None, [ieqs, None])
return Q.intersection(H)



Some examples:

sage: P = polytopes.cyclic_polytope(3,7, base_ring=ZZ, backend='normaliz')
sage: W1 = P.wedge(P.faces(2)[0]); W1.base_ring(); W1.backend()
Integer Ring
'normaliz'
sage: W2 = P.wedge(P.faces(2)[0], width=5/2); W2.base_ring(); W2.backend()
Rational Field
'normaliz'
sage: W2 = P.wedge(P.faces(2)[0], width=4/2); W2.base_ring(); W2.backend()
Rational Field
'normaliz'
sage: W2.vertices()
(A vertex at (0, 0, 0, 0),
A vertex at (1, 1, 1, 0),
A vertex at (2, 4, 8, 0),
A vertex at (3, 9, 27, -3),
A vertex at (3, 9, 27, 3),
A vertex at (4, 16, 64, -12),
A vertex at (4, 16, 64, 12),
A vertex at (5, 25, 125, -30),
A vertex at (5, 25, 125, 30),
A vertex at (6, 36, 216, -60),
A vertex at (6, 36, 216, 60))


W2 has vertices with integer coordinates

### comment:20 in reply to: ↑ 19 ; follow-up: ↓ 25 Changed 21 months ago by gh-kliem

Is this ZZ.one() really needed? Base extend should work recognize 1 as well.

Can you add base_ring=self.base_ring() and same for backend to initialization of L. (Setting up the correct base ring right away, avoids coercion for the product to my understanding.)

What about normaliz with base ring ZZ and width 5/2 (even worse 4/2)? (I suspect backend will not be preserved).

What about the examples of #25097. Do they work?

(Sorry, still can't test it myself).

The polyhedron H is the responsible for changing the base ring and the backend. The following should fix the problem (up to change of base ring form ZZ to QQ, see W2 below):

-    def wedge(self, face, width=1):
+    def wedge(self, face, width=None):
r"""
Return the wedge over a face of the polytope self.

@@ -4205,6 +4205,10 @@ class Polyhedron_base(Element):
sage: P.wedge(P.faces(2)[0], width=RDF(1)).base_ring()
Real Double Field
"""
+        if width is None:
+            width = ZZ.one()
+
if not self.is_compact():
raise ValueError("polyhedron 'self' must be a polytope")

@@ -4223,7 +4227,11 @@ class Polyhedron_base(Element):

L = Polyhedron(lines=[[1]])
Q = self.product(L)
-        H = Polyhedron(ieqs=[F_Hrep + [width], F_Hrep + [-width]])
+
+        parent = self.parent().base_extend(width, ambient_dim=self.ambient_dim()+1)
+        ieqs = [F_Hrep + [width], F_Hrep + [-width]]
+        H = parent.element_class(parent, None, [ieqs, None])
return Q.intersection(H)



Some examples:

sage: P = polytopes.cyclic_polytope(3,7, base_ring=ZZ, backend='normaliz')
sage: W1 = P.wedge(P.faces(2)[0]); W1.base_ring(); W1.backend()
Integer Ring
'normaliz'
sage: W2 = P.wedge(P.faces(2)[0], width=5/2); W2.base_ring(); W2.backend()
Rational Field
'normaliz'
sage: W2 = P.wedge(P.faces(2)[0], width=4/2); W2.base_ring(); W2.backend()
Rational Field
'normaliz'
sage: W2.vertices()
(A vertex at (0, 0, 0, 0),
A vertex at (1, 1, 1, 0),
A vertex at (2, 4, 8, 0),
A vertex at (3, 9, 27, -3),
A vertex at (3, 9, 27, 3),
A vertex at (4, 16, 64, -12),
A vertex at (4, 16, 64, 12),
A vertex at (5, 25, 125, -30),
A vertex at (5, 25, 125, 30),
A vertex at (6, 36, 216, -60),
A vertex at (6, 36, 216, 60))


W2 has vertices with integer coordinates

### comment:21 in reply to: ↑ 18 ; follow-up: ↓ 22 Changed 21 months ago by jipilab

What about normaliz with base ring ZZ and width 5/2 (even worse 4/2)? (I suspect backend will not be preserved).

A note: in Sage 4/2 is rational:

sage: type(4/2)
<class 'sage.rings.rational.Rational'>


and it should be like that, not to create nightmares.

Hence, taking width=4/2, the expected behavior is really to change the base ring to rational numbers.

In Sage dividing two Integers yields an element in the FractionField?, i.e. the rationals. It is the users responsibility to know these things. Just like 2.0 is not an integer.

That said, it is completely fine to have base_ring=QQ but integral vertices. The goal of base ring is not to steadily represent the smallest ring in which the vertices lay in.

### comment:22 in reply to: ↑ 21 ; follow-up: ↓ 23 Changed 21 months ago by gh-kliem

I was aware of 4/2 being rational. I just find it awful to change the backend when you enter rational width. The backend should never change unintentionally unless necessary (so if you enter width=2.0 the backend will change to cdd, which I would consider the expected behavior.)

It's just annoying when you want to use normaliz and every operation ignores your preference and you have to change backend over and over (and even worse calculations might take longer time with ppl, which you decided not to use in the first place).

What about normaliz with base ring ZZ and width 5/2 (even worse 4/2)? (I suspect backend will not be preserved).

A note: in Sage 4/2 is rational:

sage: type(4/2) <class 'sage.rings.rational.Rational'> }}}

and it should be like that, not to create nightmares.

Hence, taking width=4/2, the expected behavior is really to change the base ring to rational numbers.

In Sage dividing two Integers yields an element in the FractionField?, i.e. the rationals. It is the users responsibility to know these things. Just like 2.0 is not an integer.

That said, it is completely fine to have base_ring=QQ but integral vertices. The goal of base ring is not to steadily represent the smallest ring in which the vertices lay in.

### comment:23 in reply to: ↑ 22 Changed 21 months ago by jipilab

I was aware of 4/2 being rational. I just find it awful to change the backend when you enter rational width. The backend should never change unintentionally unless necessary (so if you enter width=2.0 the backend will change to cdd, which I would consider the expected behavior.)

It's just annoying when you want to use normaliz and every operation ignores your preference and you have to change backend over and over (and even worse calculations might take longer time with ppl, which you decided not to use in the first place).

What about normaliz with base ring ZZ and width 5/2 (even worse 4/2)? (I suspect backend will not be preserved).

A note: in Sage 4/2 is rational:

sage: type(4/2) <class 'sage.rings.rational.Rational'> }}}

and it should be like that, not to create nightmares.

Hence, taking width=4/2, the expected behavior is really to change the base ring to rational numbers.

In Sage dividing two Integers yields an element in the FractionField?, i.e. the rationals. It is the users responsibility to know these things. Just like 2.0 is not an integer.

That said, it is completely fine to have base_ring=QQ but integral vertices. The goal of base ring is not to steadily represent the smallest ring in which the vertices lay in.

Of course, of course. The only thing to do is to carry the backend to the wedge, no big deal...

### comment:24 Changed 21 months ago by git

• Commit changed from 417bfac337f17e93494d8f31b9031f9311cee423 to 7653fb8d21fc31d7ab34ff2c1c6da050934adef9

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

 ​00f2253 polyhedron H now preserves backend now ​09597bd backend should be preserved now ​7653fb8 Now should work if width is in RDF

### comment:25 in reply to: ↑ 20 ; follow-up: ↓ 27 Changed 21 months ago by gh-LaisRast

Base extend should work recognize 1 as well.

Not anymore after the last commit I did. ZZ.one() is really needed now. The width should have a base_ringmethod in order for the wedge to work.

Can you add base_ring=self.base_ring() and same for backend to initialization of L. (Setting up the correct base ring right away, avoids coercion for the product to my understanding.)

This might produce problems due to the following behavior:

sage: Polyhedron(lines=[[1]])
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 1 vertex and 1 line
sage: Polyhedron(lines=[[1]], base_ring=AA)
The empty polyhedron in AA^1
sage: Polyhedron(lines=[[1]], base_ring=AA, backend='normaliz')
A 1-dimensional polyhedron in AA^1 defined as the convex hull of 1 vertex and 1 line


The backend should now be preserved as long as this is possible. The base ring will change to the field of fractions of the current base ring, if width takes the default value 1. This is really needed because the base ring for the vertices is either the base ring for the ieqs or its field of fractions

New commits:

 ​00f2253 polyhedron H now preserves backend now ​09597bd backend should be preserved now ​7653fb8 Now should work if width is in RDF

### comment:26 Changed 21 months ago by gh-LaisRast

• Status changed from needs_work to needs_review

### comment:27 in reply to: ↑ 25 ; follow-up: ↓ 40 Changed 21 months ago by gh-kliem

Base extend should work recognize 1 as well.

Not anymore after the last commit I did. ZZ.one() is really needed now. The width should have a base_ringmethod in order for the wedge to work.

Can you add base_ring=self.base_ring() and same for backend to initialization of L. (Setting up the correct base ring right away, avoids coercion for the product to my understanding.)

This might produce problems due to the following behavior:

sage: Polyhedron(lines=[[1]])
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 1 vertex and 1 line
sage: Polyhedron(lines=[[1]], base_ring=AA)
The empty polyhedron in AA^1
sage: Polyhedron(lines=[[1]], base_ring=AA, backend='normaliz')
A 1-dimensional polyhedron in AA^1 defined as the convex hull of 1 vertex and 1 line


I think that's a bug.

The backend should now be preserved as long as this is possible. The base ring will change to the field of fractions of the current base ring, if width takes the default value 1. This is really needed because the base ring for the vertices is either the base ring for the ieqs or its field of fractions

New commits:

 ​00f2253 polyhedron H now preserves backend now ​09597bd backend should be preserved now ​7653fb8 Now should work if width is in RDF

### comment:28 follow-up: ↓ 29 Changed 21 months ago by gh-kliem

• Status changed from needs_review to needs_work

Most importantly the normaliz tests should be marked optional as pynormaliz cannot be assumed to be installed. Alternatively, you can switch to backend field for the tests, this demonstrates as well that the backend is preserved.

The current code does not work with width a python integer ect. How about parent = self.parent().base_extend(width/1, …, I believe this works as well. Then a default width=1 would be fine as well. As of #27926 parent.base_extend works with elements of rings and numbers that can be interpreted as such.

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

### comment:29 in reply to: ↑ 28 ; follow-ups: ↓ 31 ↓ 32 Changed 21 months ago by gh-LaisRast

Most importantly the normaliz tests should be marked optional as pynormaliz cannot be assumed to be installed. Alternatively, you can switch to backend field for the tests, this demonstrates as well that the backend is preserved.

I switched to field.

The current code does not work with width a python integer ect. How about parent = self.parent().base_extend(width/1, …, I believe this works as well. Then a default width=1 would be fine as well. As of #27926 parent.base_extend works with elements of rings and numbers that can be interpreted as such.

In python3 (resp. python2), x = 1/1; type(x) gives <class 'float'> (resp. <type 'int'>), which does not have a .base_ring(). I need .base_ring() so I can find its .fraction_field().

### comment:30 Changed 21 months ago by git

• Commit changed from 7653fb8d21fc31d7ab34ff2c1c6da050934adef9 to c77c1af1ff8732512b3cd25fe6bdc4a138041c34

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

 ​c77c1af normaliz -> field in tests

### comment:31 in reply to: ↑ 29 ; follow-up: ↓ 33 Changed 21 months ago by gh-LaisRast

• Status changed from needs_work to needs_review

Most importantly the normaliz tests should be marked optional as pynormaliz cannot be assumed to be installed. Alternatively, you can switch to backend field for the tests, this demonstrates as well that the backend is preserved.

I switched to field.

The current code does not work with width a python integer ect. How about parent = self.parent().base_extend(width/1, …, I believe this works as well. Then a default width=1 would be fine as well. As of #27926 parent.base_extend works with elements of rings and numbers that can be interpreted as such.

In python3 (resp. python2), x = 1/1; type(x) gives <class 'float'> (resp. <type 'int'>), which does not have a .base_ring(). I need .base_ring() so I can find its .fraction_field().

Having ZZ.one() as default instead of python 1 solves the problem for the default value. If the value of width is not the default value, then it is a sage ring element. This solves the problem for non-default values.

### comment:32 in reply to: ↑ 29 Changed 21 months ago by gh-kliem

Most importantly the normaliz tests should be marked optional as pynormaliz cannot be assumed to be installed. Alternatively, you can switch to backend field for the tests, this demonstrates as well that the backend is preserved.

I switched to field.

The current code does not work with width a python integer ect. How about parent = self.parent().base_extend(width/1, …, I believe this works as well. Then a default width=1 would be fine as well. As of #27926 parent.base_extend works with elements of rings and numbers that can be interpreted as such.

In python3 (resp. python2), x = 1/1; type(x) gives <class 'float'> (resp. <type 'int'>), which does not have a .base_ring(). I need .base_ring() so I can find its .fraction_field().

parent._coerce_base_ring(1/1) gives rational field, which tells me that base extend works fine. Don't worry about passing a ring to Polyhedra.base_extend. Probably you should pass 1/width as argument base_ring:

-        parent = self.parent().base_extend(width.base_ring().fraction_field(),\
+        parent = self.parent().base_extend(1/width,\
ambient_dim=self.ambient_dim()+1)


This extends the ring of parent, such that 1/width is an element. There is a number of occasions, where I used base_extend this way to have polyhedral operations respect the base ring.

### comment:33 in reply to: ↑ 31 ; follow-ups: ↓ 36 ↓ 41 Changed 21 months ago by gh-kliem

Most importantly the normaliz tests should be marked optional as pynormaliz cannot be assumed to be installed. Alternatively, you can switch to backend field for the tests, this demonstrates as well that the backend is preserved.

I switched to field.

The current code does not work with width a python integer ect. How about parent = self.parent().base_extend(width/1, …, I believe this works as well. Then a default width=1 would be fine as well. As of #27926 parent.base_extend works with elements of rings and numbers that can be interpreted as such.

In python3 (resp. python2), x = 1/1; type(x) gives <class 'float'> (resp. <type 'int'>), which does not have a .base_ring(). I need .base_ring() so I can find its .fraction_field().

Having ZZ.one() as default instead of python 1 solves the problem for the default value. If the value of width is not the default value, then it is a sage ring element. This solves the problem for non-default values.

No. If you write a python script that uses this method, you will have to import Integer from sage as well to be able to pass width. Something as 1l or 1L or float(0.9) should work as well.

Actually you need to use ZZ.one()/width (not 1/width), which should do the trick. Sorry about the confusion. Alternatively, you find a method to map width to a sage ring element and then still do the fraction field.

### comment:34 Changed 21 months ago by gh-kliem

• Status changed from needs_review to needs_work

Please allow python integers (and floats) as input for width.

### comment:35 Changed 21 months ago by git

• Commit changed from c77c1af1ff8732512b3cd25fe6bdc4a138041c34 to ccce5f2c2fc9c63d307e799572fcce581079a569

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

 ​ccce5f2 python ints and floats can be used for width

### comment:36 in reply to: ↑ 33 Changed 21 months ago by gh-LaisRast

• Status changed from needs_work to needs_review

Most importantly the normaliz tests should be marked optional as pynormaliz cannot be assumed to be installed. Alternatively, you can switch to backend field for the tests, this demonstrates as well that the backend is preserved.

I switched to field.

The current code does not work with width a python integer ect. How about parent = self.parent().base_extend(width/1, …, I believe this works as well. Then a default width=1 would be fine as well. As of #27926 parent.base_extend works with elements of rings and numbers that can be interpreted as such.

In python3 (resp. python2), x = 1/1; type(x) gives <class 'float'> (resp. <type 'int'>), which does not have a .base_ring(). I need .base_ring() so I can find its .fraction_field().

Having ZZ.one() as default instead of python 1 solves the problem for the default value. If the value of width is not the default value, then it is a sage ring element. This solves the problem for non-default values.

No. If you write a python script that uses this method, you will have to import Integer from sage as well to be able to pass width. Something as 1l or 1L or float(0.9) should work as well.

Actually you need to use ZZ.one()/width (not 1/width), which should do the trick. Sorry about the confusion. Alternatively, you find a method to map width to a sage ring element and then still do the fraction field.

This is actually a good trick to deal with python numbers.

### comment:37 Changed 21 months ago by git

• Commit changed from ccce5f2c2fc9c63d307e799572fcce581079a569 to 6ba559456a3770c5517956db2d7ae1ed44a8d717

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

 ​6ba5594 width.base_ring().fraction_field() -> ZZ.one()/width

### comment:38 Changed 21 months ago by gh-LaisRast

• Description modified (diff)

### comment:39 Changed 21 months ago by jipilab

• Milestone set to sage-8.9

### comment:40 in reply to: ↑ 27 Changed 21 months ago by jipilab

Base extend should work recognize 1 as well.

Not anymore after the last commit I did. ZZ.one() is really needed now. The width should have a base_ringmethod in order for the wedge to work.

Can you add base_ring=self.base_ring() and same for backend to initialization of L. (Setting up the correct base ring right away, avoids coercion for the product to my understanding.)

This might produce problems due to the following behavior:

sage: Polyhedron(lines=[[1]])
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 1 vertex and 1 line
sage: Polyhedron(lines=[[1]], base_ring=AA)
The empty polyhedron in AA^1
sage: Polyhedron(lines=[[1]], base_ring=AA, backend='normaliz')
A 1-dimensional polyhedron in AA^1 defined as the convex hull of 1 vertex and 1 line


I think that's a bug.

This is definitely a bug.

### comment:41 in reply to: ↑ 33 Changed 21 months ago by jipilab

Actually you need to use ZZ.one()/width (not 1/width), which should do the trick. Sorry about the confusion. Alternatively, you find a method to map width to a sage ring element and then still do the fraction field.

I do not get at all all this fuss.

The default of width should be set to None. If no value is given, the algorithm will fetch the base ring of the object and take .one() of that base ring and continue with that value.

If the user gives a weird value for the width, that's the user's problem (the whole Polyhedron class is based on this principle). It is not at all expected that the base ring is preserved. Only if possible (which is handled by the intersection method...

The only thing that matters is the backend. Thus the returned polyhedron should have the right backend...

I fail to see the issue here.

### comment:42 Changed 21 months ago by jipilab

... in particular, I do not see at all why a base_extend would be necessary.

### comment:43 follow-up: ↓ 44 Changed 21 months ago by gh-kliem

H should be well-defined and with correct backend. This is what we need base_extend for. I didn't check if we really need the value 1/width. I don't find a python integer to be a overly strange input. Especially, since we already put in the effort to make our default work.

Using standard constructor for H with backend argument can result in an error, when the backend doesn't support width. Standard constructor without backend argument, will not preserve backend, e.g. with self being integral.

base_extend does preserve backend whenever possible, which is exactly what we want.

Btw, can't we just write down all equations and inequalities right away. This saves the time of calculating double description for two (possibly large) intermediate polyhedra.

### comment:44 in reply to: ↑ 43 Changed 21 months ago by jipilab

H should be well-defined and with correct backend. This is what we need base_extend for.

H is a totally well defined object on whatever reasonable given value of width that is given by the user. There is no such thing as correct backend at this stage. All you would do is try to do a good guess before intersection will proceed to do exactly the same, but with the help of coercion. So why try to do things twice?

If the user doesn't say a word, then for sure we should just take a width from the same base ring. Then, the story with backend is irrelevant since this should be taken care of in the intersection method, and not in this specific place.

I didn't check if we really need the value 1/width. I don't find a python integer to be a overly strange input. Especially, since we already put in the effort to make our default work.

The code is barely 15 lines long... ;-)

Using standard constructor for H with backend argument can result in an error, when the backend doesn't support width.

Now I see what you mean. But again that business should be taken care of by intersection, and not here.

Standard constructor without backend argument, will not preserve backend, e.g. with self being integral.

base_extend does preserve backend whenever possible, which is exactly what we want.

Agreed. But this is a hack, and I do not like that solution. Further, one line after H is defined it is passed right away to intersection.

Btw, can't we just write down all equations and inequalities right away. This saves the time of calculating double description for two (possibly large) intermediate polyhedra.

Yes, and the long term idea is to have intersection do this kind of redundancy checks using normaliz tools. (long term...) Once adding inequalities dynamically will be readily available in Sage, we can talk about it again. For now, I don't think we have to deal with this in this ticket.

In the end, the wedge is the intersection of an infinite prism over the given polyhedron (trivial to keep base ring and backend) and an infinite keil defined by two inequalities. The base ring of this keil is decided by the type of width, and the backend should also be decided from the type of width.

Then, the decision for the backend of the intersection should be delegated to .intersection method. Why all the fuss here in wedge? If the user gives a float width and had normaliz as a backend, why should it stay normaliz? It can't!

The coercion will just figure out the right object and backend... This is already taken care of in intersection.

The following illustrates exactly the behavior that I expect to happen in wedge:

sage: P = Polyhedron(rays=[[1,0],[0,1]],base_ring=RDF)
sage: Q = Polyhedron(rays=[[-1,0],[0,1]],vertices=[[1,0]],backend='normaliz')
sage: P & Q
A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices and 1 ray
sage: P.backend()
'cdd'
sage: Q.backend()
'normaliz'


### comment:45 follow-up: ↓ 46 Changed 21 months ago by gh-kliem

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.

### comment:46 in reply to: ↑ 45 ; follow-up: ↓ 47 Changed 21 months ago by jipilab

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?

### comment:47 in reply to: ↑ 46 ; follow-up: ↓ 49 Changed 21 months ago by gh-kliem

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.

### comment:48 Changed 21 months ago by gh-kliem

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.

### comment:49 in reply to: ↑ 47 ; follow-up: ↓ 50 Changed 21 months ago by jipilab

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?

### comment:50 in reply to: ↑ 49 Changed 21 months ago by gh-kliem

Replying to jipilab: 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.

### comment:51 follow-up: ↓ 52 Changed 20 months ago by jipilab

• Status changed from needs_review to needs_work

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

### comment:52 in reply to: ↑ 51 ; follow-up: ↓ 53 Changed 20 months ago by gh-kliem

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

### comment:53 in reply to: ↑ 52 Changed 20 months ago by jipilab

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

### comment:54 Changed 20 months ago by gh-kliem

• Branch changed from public/27973 to public/27973-new
• Commit changed from 6ba559456a3770c5517956db2d7ae1ed44a8d717 to 73dac038bb83c51824d02130c9d4f1930607b9f3

New commits:

 ​73dac03 add wedge method in Polyhedron class in base.py

### comment:55 Changed 20 months ago by git

• Commit changed from 73dac038bb83c51824d02130c9d4f1930607b9f3 to 38944ad77e0a7ca760e97fcef85f2b957fe83eba

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

 ​38944ad simplified construction of H, small changes mostly in the documentation

### comment:56 Changed 20 months ago by gh-kliem

• Status changed from needs_work to needs_review

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.

### comment:57 follow-up: ↓ 58 Changed 20 months ago by jipilab

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.

### comment:58 in reply to: ↑ 57 ; follow-up: ↓ 59 Changed 20 months ago by gh-kliem

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.

### comment:59 in reply to: ↑ 58 Changed 20 months ago by jipilab

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.

### comment:60 Changed 20 months ago by gh-kliem

Is this good to go now?

### comment:61 Changed 20 months ago by jipilab

• Authors changed from Laith Rastanawi to Laith Rastanawi, Jonathan Kliem
• Reviewers set to Jean-Philippe Labbé
• Status changed from needs_review to positive_review

### comment:62 Changed 20 months ago by vbraun

• Branch changed from public/27973-new to 38944ad77e0a7ca760e97fcef85f2b957fe83eba
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.