Opened 3 years ago

Closed 3 years ago

#28724 closed enhancement (fixed)

Polyhedron._acted_upon_ should handle left multiplication by matrices, linear transformations

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polytopes
Cc: Jean-Philippe Labbé, Jiawei Wang Merged in:
Authors: Jean-Philippe Labbé, Jonathan Kliem Reviewers: Jonathan Kliem, Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: a1072ee (Commits, GitHub, GitLab) Commit: a1072eea4beeb9da56c418c7aeb264a2b587376f
Dependencies: #28770 Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

sage: b3 = polytopes.Birkhoff_polytope(3)
sage: b3.ambient_dim()
9
sage: proj_mat=matrix([[0,1,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0],[0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,1,0]])
b3_proj = proj_mat * b3
Traceback (most recent call last)
.....
.... sage/geometry/polyhedron/base.pyc in _acted_upon_(self, actor, self_on_left)
   3687             return self.translation(actor)
   3688         else:
-> 3689             return self.dilation(actor)
   3690 
   3691     def __neg__(self):
.....
ValueError: V-representation data requires a list of length ambient_dim

Change History (18)

comment:1 Changed 3 years ago by Matthias Köppe

Description: modified (diff)

comment:2 Changed 3 years ago by Jean-Philippe Labbé

Agreed, that would be nice to add this in the coercion.

comment:3 Changed 3 years ago by Jean-Philippe Labbé

Are you on it? I could come up with something.

comment:4 Changed 3 years ago by Jean-Philippe Labbé

Authors: Jean-Philippe Labbé
Branch: public/28724
Commit: 755d5c45caa4ddbc310447272fea325d3026a059
Status: newneeds_review

Here's a first version.

I wanted to have a linear_transformation method for a while... That was a good timing to add it.


New commits:

755d5c4First version of linear transformation

comment:5 Changed 3 years ago by Travis Scrimshaw

What happens when the linear transformation moves the polyhedron outside of the fields the backend can handle? Can you add such a doctest?

comment:6 Changed 3 years ago by gh-kliem

Can you just initialize the new parent like this?

new_parent = par.base_extend(linear_transf.base_ring(), ambient_dim=new_dim)

This should automatically keep the backend if possible, but change it, if not possible.

comment:7 Changed 3 years ago by gh-kliem

Status: needs_reviewneeds_work

This does not work, when the matrix consists of floats.

Please apply the change I suggested, which fixes this, and add a doctest with floats.

However, this still does not work with sqrt5 for example, even with backend field or normaliz.

This is because coercion of parents does not work in this case. I'm trying to figure out what's going on there.

comment:8 Changed 3 years ago by gh-kliem

Dependencies: #28770

I added #28770 as a dependency, because it would be nice to have doctest with a square root of something or so.

If you think this is unnecessary, feel free to remove it again.

comment:9 Changed 3 years ago by gh-kliem

Three more things.

  • is_zero catches too many matrices. A 2-by-2 zero-matrix should not change ambient dimension, if it acts on a Polyhedron in ambient dim 2. if it acts on a polyhedron of dimension 3 it should throw an error.
  • (Optional) Are you happy with the error message thrown, if the dimension of the matrix does not fit? If not you should take care of it.
  • Currently, you implemented left action (and I don't know, what a right action should be). You should probably check, whether self_on_left is False.

comment:10 Changed 3 years ago by gh-kliem

Branch: public/28724public/28724-reb
Commit: 755d5c45caa4ddbc310447272fea325d3026a0591e68f1eaa66e10c8848442d6e4e9b11d0dd17480
Status: needs_workneeds_review

I applied those small changes as suggested above.

The matrix acts on the right now, by action of the transpose on the left.


New commits:

0346231First version of linear transformation
e80556csmall changes
1e68f1emore consistent behaviour for empty matrix

comment:11 Changed 3 years ago by Erik Bray

Milestone: sage-9.0sage-9.1

Ticket retargeted after milestone closed

comment:12 Changed 3 years ago by gh-kliem

One probably should return anything, if self is on left.

Version 0, edited 3 years ago by gh-kliem (next)

comment:13 Changed 3 years ago by git

Commit: 1e68f1eaa66e10c8848442d6e4e9b11d0dd17480eca962b6f7f08f8e0770d0ac13452792ed82ca55

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

eca962bmatrix must act from the left; improved documentation

comment:14 Changed 3 years ago by gh-kliem

Branch: public/28724-rebpublic/28724-reb2
Commit: eca962b6f7f08f8e0770d0ac13452792ed82ca55a1072eea4beeb9da56c418c7aeb264a2b587376f

New commits:

a521ca7First version of linear transformation
9385b30small changes
1a01fe3more consistent behaviour for empty matrix
7a694a0matrix must act from the left; improved documentation
a1072eegive a error message if self on left; better error check for zero_matrix

comment:15 Changed 3 years ago by Jean-Philippe Labbé

Authors: Jean-Philippe LabbéJean-Philippe Labbé, Jonathan Kliem
Reviewers: Jonathan Kliem, Jean-Philippe Labbé

comment:16 Changed 3 years ago by gh-kliem

Bots are pretty much green. Some pyflakes warning, which I fixed in #28880 already (which is green botwise).

Last edited 3 years ago by gh-kliem (previous) (diff)

comment:17 Changed 3 years ago by Jean-Philippe Labbé

Status: needs_reviewpositive_review

Looks good to me.

comment:18 Changed 3 years ago by Volker Braun

Branch: public/28724-reb2a1072eea4beeb9da56c418c7aeb264a2b587376f
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.