Implement wedge over a face of Polyhedron

[jipilab]

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.

[embray]

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

[gh-LaisRast]

New commits:

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

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

[git]

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

​049e27d

more examples and fix docstring

[gh-LaisRast]

Replying to jipilab:

Thanks. Done.

[jipilab]

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

[git]

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

​193e06b

tabs to spaces

[gh-kliem]

The description of the ticket is still only about facets.

[gh-kliem]

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

[gh-kliem]

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

Can you please check. Maybe add a doctest.

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

[jipilab]

Replying to gh-kliem:

The description of the ticket is still only about facets.

Nope. See last sentence of the description.

[gh-LaisRast]

Replying to gh-kliem:

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

Can you please check. Maybe add a doctest.

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.

[git]

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

​417bfac

add tests to check backend and basering

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

Replying to gh-LaisRast:

Replying to gh-kliem:

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

Can you please check. Maybe add a doctest.

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.

[gh-LaisRast]

Replying to gh-kliem:

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

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

Replying to gh-LaisRast:

Replying to gh-kliem:

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

[jipilab]

Replying to gh-kliem:

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.

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

Replying to jipilab:

Replying to gh-kliem:

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.

[jipilab]

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

Replying to jipilab:

Replying to gh-kliem:

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

[git]

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

[gh-LaisRast]

Replying to 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

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

[gh-kliem]

Replying to gh-LaisRast:

Replying to 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

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

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.

[gh-LaisRast]

Replying to 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().

[git]

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

​c77c1af

normaliz -> field in tests

[gh-LaisRast]

Replying to gh-LaisRast:

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

[gh-kliem]

Replying to gh-LaisRast:

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

[gh-kliem]

Replying to gh-LaisRast:

Replying to gh-LaisRast:

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

[gh-kliem]

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

[git]

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

​ccce5f2

python ints and floats can be used for width

[gh-LaisRast]

Replying to gh-kliem:

Replying to gh-LaisRast:

Replying to gh-LaisRast:

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

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

[git]

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

​6ba5594

width.base_ring().fraction_field() -> ZZ.one()/width

[jipilab]

Replying to gh-kliem:

Replying to gh-LaisRast:

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

This is definitely a bug.

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

[jipilab]

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

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

[jipilab]

Replying to gh-kliem:

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'

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

[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?

[gh-kliem]

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

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.

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

[jipilab]

Replying to gh-kliem:

Replying to 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?

[gh-kliem]

Replying to jipilab:

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

[jipilab]

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

[gh-kliem]

Replying to jipilab:

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

[jipilab]

Replying to gh-kliem:

Replying to jipilab:

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.

[gh-kliem]

Merged with newest develop.

---

New commits:

​73dac03

add wedge method in Polyhedron class in base.py

[git]

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

​38944ad

simplified construction of H, small changes mostly in the documentation

[gh-kliem]

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.

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

[gh-kliem]

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

This should be fixed...

The rest seems to be good.

[jipilab]

Replying to gh-kliem:

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

[gh-kliem]

Is this good to go now?