Preserve backend for polytopal constructions

[gh-kliem]

Currently constructions of new polyhedra in Polyhedron_base do not preserve the backend:

sage: Polyhedron(vertices=[[0]], backend='field').pyramid().backend()
'ppl'

This ticket fixes this.

This respects the users intentions, who might have chosen a specific backend for a good reason. Also, once #25097 is merged, this is needed to have the constructions work for polyhedra over number fields.

More precisely the constructions are:

• minkowski_sum (taken care of by @coerce_binop and constructing from self.parent().element_class)
• minkowski_difference (taken care of by @coerce_binop and constructing from self.parent().element_class)
• translation,
• product,
• join,
• subdirect_sum,
• direct_sum,
• dilation,
• convex_hull (taken care of by @coerce_binop and constructing from self.parent().element_class),
• intersection (taken care of by @coerce_binop and constructing from self.parent().element_class),
• truncation,
• face_truncation,
• stack,
• lawrence_extension,
• lawrence_polytope,
• polar (fixed already, #25081),
• pyramid,
• bipyramid,
• prism,
• face_split,
• affine_hull.

[git]

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

​1635e50

preserve backend for polytopal constructions

[vdelecroix]

This is not likely to be a good idea

+        return Polyhedron(vertices=new_vertices, rays=new_rays, lines=new_lines, base_ring=new_ring, backend=self.backend())

Backends do not support all base rings. For example if you have a polytope with backend PPL and then translate with sqrt(2) that would not work.

[vdelecroix]

You should add backend=self.backend() only if the base ring is identical.

[gh-kliem]

I missed this instance. I'll fix it like the other methods. There is a new function test_backend that tests if a combination of backend and base_ring will work.

Replying to vdelecroix:

You should add backend=self.backend() only if the base ring is identical.

[git]

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

​937891c

added backend check in translation

[vdelecroix]

test_backend is a terrible name. This function does not test the backend. It would better be does_backend_handle_base_ring.

The result of test_backend must be cached (with the decorator @cached_function).

If the new_ring is actually the same as before, you should avoid going through does_backend_handle_base_ring.

[vdelecroix]

I am not sure this is the right approach. The same code is copied in each single function. I think what is done with matrices is more sensible and the information about the backend is actually stored into the parents

sage: M1 = MatrixSpace(ZZ, 3, implementation='gap')
sage: M1
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_gap)
sage: M2 = MatrixSpace(ZZ, 3, implementation='generic')
sage: M2
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_generic_dense)

The rules about promotions such as

sage: parent(M1.an_element() * M2.an_element())
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring

are handled by the parents and this is what it should be done for polyhedra as well.

[gh-kliem]

I guess I should work with Polyhedra_base.base_extend.

Either I introduce a new option for backend, such as keep or a change the default behavior to attempt to keep the backend, if possible.

What do you think?

I find the default behavior to be strange at the moment. I have a Polyhedron, change the base ring and all the sudden I use a different backend, even though the old one would have worked.

Replying to vdelecroix:

I am not sure this is the right approach. The same code is copied in each single function. I think what is done with matrices is more sensible and the information about the backend is actually stored into the parents

sage: M1 = MatrixSpace(ZZ, 3, implementation='gap')
sage: M1
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_gap)
sage: M2 = MatrixSpace(ZZ, 3, implementation='generic')
sage: M2
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_generic_dense)

The rules about promotions such as

sage: parent(M1.an_element() * M2.an_element())
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring

are handled by the parents and this is what it should be done for polyhedra as well.

[vdelecroix]

There is no discussion about the fact that the current behavior is wrong. I tried to argue that your initial solution was not optimal. Namely, the parents already carry the backend information (Polyhedra_QQ_ppl, Polyhedra_ZZ_ppl, ...). Anytime a new polyhedra is constructed inside a method, the new parent should be chosen via a query to the parent.

Modifying Polyhedra_base.base_extend is a good idea. If the new base_ring supports the current backend, it should be kept.

Though at this point, I don't quite understand the difference between base_extend and change_ring... that would better be clarified.

Replying to gh-kliem:

I guess I should work with Polyhedra_base.base_extend.

Either I introduce a new option for backend, such as keep or a change the default behavior to attempt to keep the backend, if possible.

What do you think?

I find the default behavior to be strange at the moment. I have a Polyhedron, change the base ring and all the sudden I use a different backend, even though the old one would have worked.

Replying to vdelecroix:

I am not sure this is the right approach. The same code is copied in each single function. I think what is done with matrices is more sensible and the information about the backend is actually stored into the parents

sage: M1 = MatrixSpace(ZZ, 3, implementation='gap')
sage: M1
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_gap)
sage: M2 = MatrixSpace(ZZ, 3, implementation='generic')
sage: M2
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_generic_dense)

The rules about promotions such as

sage: parent(M1.an_element() * M2.an_element())
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring

are handled by the parents and this is what it should be done for polyhedra as well.

[gh-kliem]

I believe change_ring was created after base_extend as base_extend doesn't allow the ring to become smaller. Either way base_extend should just call change_ring with the coerced ring (and change_ring should return self if possible).

Ok. I will now proceed as follows:

1. Let change_ring call base_extend. (Btw. the error checking with regard to inexact rings in Polyhedron_base.change_ring really should be left to parent as well.)

2. Create a new parent only if needed.

3. Change default behavior of None in change_ring to leave backend if possible.

4. Simplify all the methods to obtain a parent with base_extend and then initialize from that parent.

Replying to vdelecroix:

There is no discussion about the fact that the current behavior is wrong. I tried to argue that your initial solution was not optimal. Namely, the parents already carry the backend information (Polyhedra_QQ_ppl, Polyhedra_ZZ_ppl, ...). Anytime a new polyhedra is constructed inside a method, the new parent should be chosen via a query to the parent.

Modifying Polyhedra_base.base_extend is a good idea. If the new base_ring supports the current backend, it should be kept.

Though at this point, I don't quite understand the difference between base_extend and change_ring... that would better be clarified.

Replying to gh-kliem:

I guess I should work with Polyhedra_base.base_extend.

Either I introduce a new option for backend, such as keep or a change the default behavior to attempt to keep the backend, if possible.

What do you think?

I find the default behavior to be strange at the moment. I have a Polyhedron, change the base ring and all the sudden I use a different backend, even though the old one would have worked.

Replying to vdelecroix:

I am not sure this is the right approach. The same code is copied in each single function. I think what is done with matrices is more sensible and the information about the backend is actually stored into the parents

sage: M1 = MatrixSpace(ZZ, 3, implementation='gap')
sage: M1
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_gap)
sage: M2 = MatrixSpace(ZZ, 3, implementation='generic')
sage: M2
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring (using Matrix_generic_dense)

The rules about promotions such as

sage: parent(M1.an_element() * M2.an_element())
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring

are handled by the parents and this is what it should be done for polyhedra as well.

[git]

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

​cbffe28

moved changes of ring and backend to parent

[git]

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

​970c142

fixed inconsistent parenthesis

[vdelecroix]

I think the logic in change_ring would better be simplified to

        if ambient_dim is None:
            ambient_dim = self.ambient_dim()

        if base_ring == self.base_ring() and \
           ambient_dim == self.ambient_dim() and \
           backend is None or backend == self.backend():
                return self

        # if not specified, try the same backend
        if backend is None and does_backend_handle_base_ring(base_ring, self.backend()):
            return Polyhedra(base_ring, ambient_dim, backend=self.backend())

        return Polyhedra(base_ring, ambient_dim, backend=backend)

Also, you should add more examples to change_ring. In particular when something has changed with respect to older versions such as

sage: Polyhedra(QQ, 3, backend='cdd').change_ring(RDF).backend()
'cdd'

[jipilab]

Replying to vdelecroix:

Though at this point, I don't quite understand the difference between base_extend and change_ring... that would better be clarified.

base_extend is a calque from the same function for example for matrices, that creates a new parent with an extended ring and coerces self into this new parent and returns it.

As Jonathan said, this can only go in one direction and was not really adapted to polyhedra objects. This led to introduce change_ring to have all the flexibility possible (and perhaps a more intuitive name than base_extend) and because you can't really change ring without caring about the backend, change_backend and change_ring are bound to have fuzzy differences and may even call eachother (hopefully in only 1 direction!).

So yes, it is subtle and I am all in favor of rationalizing base_extend, change_ring and change_backend (which is not all there yet).

[git]

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

​a3a96bc

small changes

[embray]

Not in Sage 8.8. Let's please to try keep tickets' milestones related to the release in which we actually intend to include them, and in particular the release in which they were actually included, especially when closing tickets.

[jipilab]

Barycentric subdivision was forgotten... :-(