Opened 10 years ago

# [with patch, needs work] Action of MatrixGroup on a MPolynomialRing — at Version 15

Reported by: Owned by: SimonKing SimonKing major sage-6.4 commutative algebra matrix group, action, polynomial ring wdj, malb N/A

A group of n by n matrices over a field K acts on a polynomial ring with n variables over K. However, this is not implemented yet.

The following should work:

```sage: M = Matrix(GF(3),[[1,2],[1,1]])
sage: N = Matrix(GF(3),[[2,2],[2,1]])
sage: G = MatrixGroup([M,N])
sage: m = G.0
sage: n = G.1
sage: R.<x,y> = GF(3)[]
sage: m*x
x + y
sage: x*m
x - y
sage: (n*m)*x == n*(m*x)
True
sage: x*(n*m) == (x*n)*m
True
```

On the other hand, we still want to have the usual action on vectors or matrices:

```sage: x = vector([1,1])
sage: x*m
(2, 0)
sage: m*x
(0, 2)
sage: (n*m)*x == n*(m*x)
True
sage: x*(n*m) == (x*n)*m
True
```
```sage: x = matrix([[1,2],[1,1]])
sage: x*m
[0 1]
[2 0]
sage: m*x
[0 1]
[2 0]
sage: (n*m)*x == n*(m*x)
True
sage: x*(n*m) == (x*n)*m
True
```

### comment:1 Changed 10 years ago by SimonKing

• Component changed from algebra to commutative algebra
• Owner changed from tbd to malb

Sorry, in the above code I forgot to copy/paste the line

```sage: R.<x,y> = GF(3)[]
```

Moreover, for the reasons above, the ticket should belong to *commutative* algebra, not just algebra (I was clicking on the wrong button).

### comment:2 Changed 10 years ago by SimonKing

• Summary changed from Action of MatrixGroup on a MPolynomialRing to [with patch, needs work] Action of MatrixGroup on a MPolynomialRing

The patch `matrixgroupCall.patch` is without doctests, and I am not sure if it couldn't be done better. So, it needs more work.

For example, Martin mentioned the possibility (off list) to create a pyx file with a Cython function, and then the call method would use that function. It might pay off here, since there are tight loops and since the method has to deal with tuples or lists. So Cdefining might speed things up.

Opinions?

At least, the following now works:

```sage: R.<x,y>=GF(3)[]
sage: M=Matrix(GF(3),[[1,2],[1,1]])
sage: G=MatrixGroup([M])
sage: g=G.0
sage: p=x*y^2
sage: g(p)
x^3 + x^2*y - x*y^2 - y^3
```

### comment:3 Changed 10 years ago by mabshoff

• Milestone set to sage-3.2.1

### Changed 10 years ago by SimonKing

call method for MatrixGroupelement? (this time with doc test) and left_matrix_action for MPolynomial

### comment:4 Changed 10 years ago by SimonKing

• Owner changed from malb to SimonKing
• Summary changed from [with patch, needs work] Action of MatrixGroup on a MPolynomialRing to [with patch, needs review] Action of MatrixGroup on a MPolynomialRing

Some changes:

Nicolas Thiéry suggested to implement the action of matrix groups by a method for polynomials (I call the method `left_matrix_action`), and, for convenience, also provide a `__call__` method for MatrixGroupElement? that refers to `left_matrix_action`.

• The `__call__` works for any class that has a `left_matrix_action` method, hence, it is not a-priori restricted to polynomials.
• I've put `left_matrix_action` into `multi_polynomial.pyx`, hence, I can use Cython.

I have two Cython concerns left:

1. The innerst loop is
```prod([Im[k]**X[k] for k in xrange(n)])
```
where `k` is c'defined as `int`. Should this better be done in a for-loop, rather then creating a list and calling `prod`?
2. The variable `X` is of type `polydict.ETuple`, so I can not directly c'define `X`. One could do
```   cdef tuple X
for i from 0<i<l:
X = tuple(Expo[i])
```
But would this be faster?

### Changed 10 years ago by SimonKing

Another version of left_matrix_action

### comment:5 follow-up: ↓ 6 Changed 10 years ago by SimonKing

In `matrixgroupCallNew.patch` (to be applied after the first patch), I modified the method according to my above concerns. In the example from my original post, the average running time improves from ~240 microseconds to 164 microseconds, and in a larger example it improved from 6.5s to 5.4s

Nevertheless, I made two separate patches, so that the reviewer (if there is any...) can compare by him- or herself.

Cheers

Simon

### comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 10 years ago by SimonKing

One observation: Reverse the outer loop

```        for i from l>i>=0:
X = tuple(Expo[i])
c = Coef[i]
for k from 0<=k<n:
if X[k]:
c *= Im[k]**X[k]
q += c
```

It results in a further improvement of computation time. Is this coincidence? Or is it since summation of polynomials should better start with the smallest summands?

Anyway, I didn't change the patch yet.

### Changed 10 years ago by SimonKing

Slight improvement; extended functionality

### comment:7 in reply to: ↑ 6 Changed 10 years ago by SimonKing

One observation: Reverse the outer loop

```        for i from l>i>=0:
X = tuple(Expo[i])
c = Coef[i]
for k from 0<=k<n:
if X[k]:
c *= Im[k]**X[k]
q += c
```

It results in a further improvement of computation time. Is this coincidence? Or is it since summation of polynomials should better start with the smallest summands?

I made a couple of tests, and there was a small but consistent improvement. So, in the third patch (to be applied after the other two) I did it in that way.

The `left_matrix_action` shall eventually be used for computing the Reynolds operator of a group action; moreover, the Reynolds operator should be applicable on a list of polynomials. Then, the function would repeatedly compute the image of the ring variables under the action of some group element. But then it would be better to compute that image only once and pass it to `left_matrix_action`. The new patch provides this functionality. Example (continuing the original example):

```sage: L=[X.left_matrix_action(g) for X in R.gens()]
sage: p.left_matrix_action(L)
x^3 + x^2*y - x*y^2 - y^3
```

### comment:8 Changed 10 years ago by wdj

I did confirm that the patches apply cleanly, that

```sage: M = Matrix(GF(3),[[1,2],[1,1]])
sage: G = MatrixGroup([M])
sage: g = G.0
sage: g

[1 2]
[1 1]
sage: P.<x,y> = PolynomialRing(GF(3),2)
sage: p = x*y^2
sage: g(p)
x^3 + x^2*y - x*y^2 - y^3
sage: (x+2*y)*(x+y)^2
x^3 + x^2*y - x*y^2 - y^3

```

works, and that the code seems well-documented.

However, I can't do testing on this machine (intrepid ubuntu) and some of the code is written in Cython, which I can't really 100% vouch for. Seems okay though and simple enough. Since speed was a topic of the comments above, my only question is that the segment

``` 	396	        for i from 0<=i<l:
397	            X = Expo[i]
398	            c = Coef[i]
399	            q += c*prod([Im[k]**X[k] for k in xrange(n)])
```

could probably be rewritten as a one-line sum, which might (or might not) be faster.

Maybe Martin Albrecht could comment on the Cython code?

If Martin (for example) passes the Cython code, and the docstrings pass sage -testall, I would give it a positive review.

### comment:9 Changed 10 years ago by malb

```cdef list Im
if isinstance(M,list):
Im = M
```

shouldn't Im = M take care of the type checking anyway, so that a try-except block is sufficient? Also, I think maybe the type of p should be checked in the `__call__` method and a friendly error message raised? Not sure though.

### comment:10 Changed 10 years ago by malb

Cython code looks good (just read it).

### comment:11 Changed 10 years ago by was

• Summary changed from [with patch, needs review] Action of MatrixGroup on a MPolynomialRing to [with patch, needs work] Action of MatrixGroup on a MPolynomialRing

REFEREE REPORT:

Check this out:

```sage: R.<x,y> = GF(3)[]
sage: M=Matrix(GF(3),[[1,2],[1,1]])
sage: M2=Matrix(GF(3),[[1,2],[1,0]])
sage: G=MatrixGroup([M, M2])
sage: (G.0*G.1)(p)
-x^2*y + x*y^2 - y^3
sage: G.0(G.1(p))
x^2*y + x*y^2 + y^3
```

Oops, your *left action* -- which it better be if you use that notation -- ain't a left action! Oops

-- William

### comment:12 follow-up: ↓ 13 Changed 10 years ago by SimonKing

Really Oops. Sorry.

I implemented it analogous to what is done in Singular. Perhaps I am mistaken in the sense that it is supposed to be a right action (which then would deserve another notation).

```sage: (G.0(G.1((p))))
-x^2*y + x*y^2 - y^3
sage: (G.1*G.0)(p)
-x^2*y + x*y^2 - y^3
```

However, I think it doesn't matter what Singular does. I will look up the literature whether one really wants a right or left action, and how the left action is supposed to be.

### comment:13 in reply to: ↑ 12 Changed 10 years ago by SimonKing

However, I think it doesn't matter what Singular does. I will look up the literature whether one really wants a right or left action...

I mean, something like "one has a left action on a variety, which gives rise to a right action on the coordinate ring". I have to sort it out.

If this is the case, then it should be better implemented in the `__mul__` method of polynomials, isn't it? Such as

```sage: p*G.1*G.0==p*(G.1*G.0)
True
```

### comment:14 Changed 10 years ago by was

Left actions should use call, right actions should use *exponentiation*.

Substitution is a right action. Substitution of the *inverse* is a left action.

### comment:15 Changed 9 years ago by SimonKing

• Description modified (diff)
• Report Upstream set to N/A

### Changed 9 years ago by SimonKing

Replaces the other patches

Note: See TracTickets for help on using tickets.