#25490 closed defect (fixed)

Fix Matrix_gfpn_dense.rescale_row_c

Reported by: SimonKing Owned by:
Priority: major Milestone: sage-8.3
Component: packages: optional Keywords: MeatAxe rescale row, days94
Cc: tscrim Merged in:
Authors: Simon King Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 1a97f39 (Commits) Commit: 1a97f39ec01d45fb9a59fe9512689e3e35245d52
Dependencies: #25518 Stopgaps:

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.

Change History (25)

comment:1 Changed 23 months ago by SimonKing

  • Dependencies set to #25476

comment:2 Changed 23 months 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.

comment:3 Changed 23 months ago by tscrim

Sounds good.

comment:4 Changed 23 months ago by SimonKing

  • Branch set to u/SimonKing/fix_matrix_gfpn_dense_rescale_row_c

comment:5 Changed 23 months 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:

4eae803Making matrices use the new _echelon_in_place method.
9792b53Matrix_gfpn_dense: Fix field and row size assignments; use start_col argument

comment:6 follow-up: Changed 23 months 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 23 months ago by SimonKing (previous) (diff)

comment:7 Changed 22 months ago by jdemeyer

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

comment:8 Changed 22 months 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 22 months ago by jdemeyer

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

New commits:

e2f0550Specify that _echelon_in_place shall return the pivots
3c4a06dEnable _mul_long for matrices
1eaed37More stuff in the meataxe interface, and a meataxe helper function
8a06c0fFix docstring formatting
cef13b8Matrix_gfpn_dense: Fix field and row size assignments; use start_col argument

comment:10 in reply to: ↑ 6 Changed 22 months ago by jdemeyer

Replying to SimonKing:

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: Changed 22 months 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 22 months ago by jdemeyer

  • Status changed from needs_review to needs_work

Replying to tscrim:

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: Changed 22 months ago by SimonKing

Replying to 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

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: Changed 22 months ago by tscrim

Replying to SimonKing:

Replying to 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: Changed 22 months ago by jdemeyer

Replying to 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.

comment:16 in reply to: ↑ 15 ; follow-up: Changed 22 months ago by tscrim

Replying to jdemeyer:

Replying to 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 22 months 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 22 months 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:

b59c597Merge 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
1a97f39Removing duplicate FfSetField.

comment:19 in reply to: ↑ 16 ; follow-up: Changed 22 months ago by jdemeyer

Replying to tscrim:

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 22 months ago by jdemeyer (previous) (diff)

comment:20 in reply to: ↑ 19 Changed 22 months ago by tscrim

Replying to jdemeyer:

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: Changed 22 months 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 22 months ago by SimonKing

Replying to tscrim:

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 22 months ago by tscrim

  • Status changed from needs_review to positive_review

Yep, that was it.

comment:24 Changed 22 months ago by tscrim

  • Keywords days94 added

comment:25 Changed 22 months ago by vbraun

  • Branch changed from u/tscrim/fix_matrix_gfpn_dense_rescale_row_c-25490 to 1a97f39ec01d45fb9a59fe9512689e3e35245d52
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.