Opened 3 years ago

Closed 3 years ago

# Fix Matrix_gfpn_dense.rescale_row_c

Reported by: Owned by: SimonKing major sage-8.3 packages: optional MeatAxe rescale row, days94 tscrim Simon King Travis Scrimshaw N/A 1a97f39 1a97f39ec01d45fb9a59fe9512689e3e35245d52 #25518

### Description

There are two problems with `Matrix_gfpn_dense.rescale_row_c`:

1. The optional argument `start_col` is not supported - see also #25476.
2. It is assumed that the field and the row size (which are global variables in MeatAxe) are correctly assigned to, but this assumption is easily violated:
```sage: K.<x> = GF(25)
sage: L.<y> = GF(81)
sage: M = MatrixSpace(K,1,25)(sorted(list(K)))
sage: N = MatrixSpace(L,5,5)(sorted(list(L))[:25])
sage: M.rescale_row(0,2)
sage: M
[      0       2       1   x + 1   x + 3       x   x + 1   x + 2   x + 3   x + 4     2*x 2*x + 1 2*x + 2 2*x + 3 2*x + 4     3*x 3*x + 1 3*x + 2 3*x + 3 3*x + 4     4*x 4*x + 1 4*x + 2 4*x + 3 4*x + 4]
sage: M = MatrixSpace(K,1,25)(sorted(list(K)))
sage: M.rescale_row(0,2)
sage: M
[      0       2       4       1       3     2*x 2*x + 2 2*x + 4 2*x + 1 2*x + 3     4*x 4*x + 2 4*x + 4 4*x + 1 4*x + 3       x   x + 2   x + 4   x + 1   x + 3     3*x 3*x + 2 3*x + 4 3*x + 1 3*x + 3]
```

So, in the first part of the example, creation of `N` makes MeatAxe believe that the current row size is 5 and the field has 81 elements, and therefore rescaling `M` is doomed.

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

• Dependencies set to #25476

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

As it turns out, there are several places in which I forgot to assign the field and/or row size before calling a `Ff*` function from MeatAxe. So, I am fixing these as well. Note that it is fine to call an `Ff*` function for a matrix after calling a `Mat*` function from MeatAxe, because the `Mat*` functions all assign the correct field and row size.

Sounds good.

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

• Branch set to u/SimonKing/fix_matrix_gfpn_dense_rescale_row_c

### comment:5 Changed 3 years ago by SimonKing

• Authors set to Simon King
• Commit set to 9792b5377bd5fa19b11eb797cd0bb2fd4035dcee
• Status changed from new to needs_review

I fixed a couple of places where field and row size are not assigned, and I enabled the use of the optional `start_col` argument of `add_multiple_of_row_c` and `rescale_row_c`. Tests in sage/matrix/ pass.

New commits:

 ​4eae803 `Making matrices use the new _echelon_in_place method.` ​9792b53 `Matrix_gfpn_dense: Fix field and row size assignments; use start_col argument`

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

PS: I needed to import some additional stuff from SharedMeatAxe, which means that I needed to change sage/libs/meataxe.pxd as well.

Last edited 3 years ago by SimonKing (previous) (diff)

### comment:7 Changed 3 years ago by jdemeyer

• Dependencies changed from #25476 to #25518
• Status changed from needs_review to needs_work

### comment:8 Changed 3 years ago by jdemeyer

• Branch changed from u/SimonKing/fix_matrix_gfpn_dense_rescale_row_c to u/jdemeyer/fix_matrix_gfpn_dense_rescale_row_c

### comment:9 Changed 3 years ago by jdemeyer

• Commit changed from 9792b5377bd5fa19b11eb797cd0bb2fd4035dcee to cef13b8f2aece9c723dfa10f221fc14ac67c22af
• Status changed from needs_work to needs_review

New commits:

 ​e2f0550 `Specify that _echelon_in_place shall return the pivots` ​3c4a06d `Enable _mul_long for matrices` ​1eaed37 `More stuff in the meataxe interface, and a meataxe helper function` ​8a06c0f `Fix docstring formatting` ​cef13b8 `Matrix_gfpn_dense: Fix field and row size assignments; use start_col argument`

### comment:10 in reply to: ↑ 6 Changed 3 years ago by jdemeyer

PS: I needed to import some additional stuff from SharedMeatAxe, which means that I needed to change sage/libs/meataxe.pxd as well.

This part has been moved to #25518.

### comment:11 follow-ups: ↓ 12 ↓ 13 Changed 3 years ago by tscrim

This looks like a mistake:

```@@ -1231,6 +1317,7 @@ cdef class Matrix_gfpn_dense(Matrix_dense):
"""
if self.Data == NULL:
raise ValueError("The matrix must not be empty")
+        FfSetField(self.Data.Field)
cdef Matrix_gfpn_dense left
FfSetField(self.Data.Field)
cdef FEL r
```

Also, have you noticed a speed regression by not doing it purely in MeatAxe? In particular, I am wondering if it might be worthwhile to patch MeatAxe instead of implementing it in Sage.

### comment:12 in reply to: ↑ 11 Changed 3 years ago by jdemeyer

• Status changed from needs_review to needs_work

This looks like a mistake

Yes, I guess the same patch was added on two different tickets (#25079 and #25490).

### comment:13 in reply to: ↑ 11 ; follow-up: ↓ 14 Changed 3 years ago by SimonKing

This looks like a mistake:

```@@ -1231,6 +1317,7 @@ cdef class Matrix_gfpn_dense(Matrix_dense):
"""
if self.Data == NULL:
raise ValueError("The matrix must not be empty")
+        FfSetField(self.Data.Field)
cdef Matrix_gfpn_dense left
FfSetField(self.Data.Field)
cdef FEL r
```

Right, setting the field twice is a mistake.

Also, have you noticed a speed regression by not doing it purely in MeatAxe? In particular, I am wondering if it might be worthwhile to patch MeatAxe instead of implementing it in Sage.

Patching wouldn't be needed, as I am upstream for SharedMeatAxe. But I don't expect that it would be really worth-while in terms of speed. In the end, both approaches yield more or less the same C code.

### comment:14 in reply to: ↑ 13 ; follow-up: ↓ 15 Changed 3 years ago by tscrim

Also, have you noticed a speed regression by not doing it purely in MeatAxe? In particular, I am wondering if it might be worthwhile to patch MeatAxe instead of implementing it in Sage.

Patching wouldn't be needed, as I am upstream for SharedMeatAxe. But I don't expect that it would be really worth-while in terms of speed. In the end, both approaches yield more or less the same C code.

It just seems to me everything I look into the Cython generated C code, it seems like there could be a bit of overhead (and this might be something the library might benefit from having internally). However, I am content with the current state here (modulo the double set).

### comment:15 in reply to: ↑ 14 ; follow-up: ↓ 16 Changed 3 years ago by jdemeyer

It just seems to me everything I look into the Cython generated C code, it seems like there could be a bit of overhead

If you have concrete examples of this, I'm sure that Cython upstream would be interested in fixing that.

### comment:16 in reply to: ↑ 15 ; follow-up: ↓ 19 Changed 3 years ago by tscrim

It just seems to me everything I look into the Cython generated C code, it seems like there could be a bit of overhead

If you have concrete examples of this, I'm sure that Cython upstream would be interested in fixing that.

I am just referring to some of the unnecessary extra variables that are used or extra error checks. For instance, things like

```  /* "sage/groups/perm_gps/permgroup_element.pyx":244
*     if isinstance(g, Permutation):
*         return g.cycle_tuples()
*     if isinstance(g, PermutationGroupElement):             # <<<<<<<<<<<<<<
*         g = g.cycle_tuples()
*     if isinstance(g, str):
*/
__pyx_t_3 = __Pyx_TypeCheck(__pyx_v_g, __pyx_ptype_4sage_6groups_8perm_gps_17permgroup_element_PermutationGroupElement);
__pyx_t_4 = (__pyx_t_3 != 0);
if (__pyx_t_4) {
```

Granted, I suspect the compiler will optimize `__pyx_t_3` and `__pyx_t_4` away, but I still wonder if takes up a few extra CPU cycles, which multiplied by times they occur could result in faster code.

### comment:17 Changed 3 years ago by tscrim

I should make it clear I do not have any concrete example where I could write C code that would be definitely faster than Cython's version. Although I have not currently tried such a comparison.

### comment:18 Changed 3 years ago by tscrim

• Branch changed from u/jdemeyer/fix_matrix_gfpn_dense_rescale_row_c to u/tscrim/fix_matrix_gfpn_dense_rescale_row_c-25490
• Commit changed from cef13b8f2aece9c723dfa10f221fc14ac67c22af to 1a97f39ec01d45fb9a59fe9512689e3e35245d52
• Reviewers set to Travis Scrimshaw
• Status changed from needs_work to needs_review

From looking at the C code of the added here, the Cython really should not have any real overhead.

I just removed the duplicate mentioned above. I suppose the proper thing is to have someone else check this rather than simply setting it to a positive review.

New commits:

 ​b59c597 `Merge branch 'u/jdemeyer/fix_matrix_gfpn_dense_rescale_row_c' of git://trac.sagemath.org/sage into u/jdemeyer/fix_matrix_gfpn_dense_rescale_row_c` ​1a97f39 `Removing duplicate FfSetField.`

### comment:19 in reply to: ↑ 16 ; follow-up: ↓ 20 Changed 3 years ago by jdemeyer

Granted, I suspect the compiler will optimize `__pyx_t_3` and `__pyx_t_4` away

I'm pretty sure that this is the case indeed. Recent compilers are very good at this.

Anyway, I thought that you were referring to "pure C" code in Cython. When Python objects are involved, there is always some overhead because of refcounting for example.

Last edited 3 years ago by jdemeyer (previous) (diff)

### comment:20 in reply to: ↑ 19 Changed 3 years ago by tscrim

Anyway, I thought that you were referring to "pure C" code in Cython. When Python objects are involved, there is always some overhead because of refcounting for example.

Only in a very small part. Although it is nice to see with proper typing for everything that it basically is a straight translation to C.

### comment:21 follow-up: ↓ 22 Changed 3 years ago by tscrim

Can someone verify my change? That is the only thing missing from a positive review here.

### comment:22 in reply to: ↑ 21 Changed 3 years ago by SimonKing

Can someone verify my change? That is the only thing missing from a positive review here.

Are you only talking about commit:1a97f39? That's of course totally fine, FfSetField was called twice where it should only be called once.

So, if that's the only issue, it is "positive review".

### comment:23 Changed 3 years ago by tscrim

• Status changed from needs_review to positive_review

Yep, that was it.