Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#27926 closed enhancement (fixed)

Preserve backend for polytopal constructions

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-8.9
Component: geometry Keywords: polytopes, backend, normaliz
Cc: jipilab, vdelecroix Merged in:
Authors: Jonathan Kliem Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: a3a96bc (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (24)

comment:1 Changed 2 years ago by gh-kliem

  • Description modified (diff)

comment:2 Changed 2 years ago by gh-kliem

  • Branch set to public/27926
  • Cc jipilab vdelecroix added
  • Commit set to 716fb6975472331688cc108b524b80bebaef2360
  • Status changed from new to needs_review

comment:3 Changed 2 years ago by git

  • Commit changed from 716fb6975472331688cc108b524b80bebaef2360 to 1635e50536aac0360a0cf40b7a99e95dbbba42a9

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

1635e50preserve backend for polytopal constructions

comment:4 Changed 2 years ago by vdelecroix

  • Status changed from needs_review to needs_work

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.

comment:5 follow-up: Changed 2 years ago by vdelecroix

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

comment:6 in reply to: ↑ 5 Changed 2 years ago by 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.

comment:7 Changed 2 years ago by git

  • Commit changed from 1635e50536aac0360a0cf40b7a99e95dbbba42a9 to 937891c8395e5905f2d2c5a074f79ffd0ff3e60e

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

937891cadded backend check in translation

comment:8 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:9 Changed 2 years ago by vdelecroix

  • Status changed from needs_review to needs_work

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.

comment:10 follow-up: Changed 2 years ago by 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.

Last edited 2 years ago by vdelecroix (previous) (diff)

comment:11 in reply to: ↑ 10 ; follow-up: Changed 2 years ago by 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.

comment:12 in reply to: ↑ 11 ; follow-ups: Changed 2 years ago by 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.

comment:13 in reply to: ↑ 12 Changed 2 years ago by 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.)
  1. Create a new parent only if needed.
  1. Change default behavior of None in change_ring to leave backend if possible.
  1. 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.

comment:14 Changed 2 years ago by git

  • Commit changed from 937891c8395e5905f2d2c5a074f79ffd0ff3e60e to cbffe2867da538199933d49d4549cf03e3931ce4

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

cbffe28moved changes of ring and backend to parent

comment:15 Changed 2 years ago by git

  • Commit changed from cbffe2867da538199933d49d4549cf03e3931ce4 to 970c142283df9b60fc57309b3b142bb782c4bcc6

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

970c142fixed inconsistent parenthesis

comment:16 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:17 Changed 2 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

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'

comment:18 in reply to: ↑ 12 Changed 2 years ago by 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).

comment:19 Changed 2 years ago by git

  • Commit changed from 970c142283df9b60fc57309b3b142bb782c4bcc6 to a3a96bc413727816c16705c4f03400429ee36445

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

a3a96bcsmall changes

comment:20 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:21 Changed 2 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:22 Changed 2 years ago by vbraun

  • Branch changed from public/27926 to a3a96bc413727816c16705c4f03400429ee36445
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:23 Changed 2 years ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

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.

comment:24 Changed 2 years ago by jipilab

  • Commit a3a96bc413727816c16705c4f03400429ee36445 deleted

Barycentric subdivision was forgotten... :-(

Note: See TracTickets for help on using tickets.