Opened 2 years ago

Closed 2 years ago

#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 2 years ago by SimonKing

  • Dependencies set to #25476

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

comment:3 Changed 2 years ago by tscrim

Sounds good.

comment:4 Changed 2 years ago by SimonKing

  • Branch set to u/SimonKing/fix_matrix_gfpn_dense_rescale_row_c

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

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 2 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 2 years ago by SimonKing (previous) (diff)

comment:7 Changed 2 years ago by jdemeyer

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

comment:8 Changed 2 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 2 years 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 2 years 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 2 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 2 years 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 2 years 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 2 years 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 2 years 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 2 years 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 2 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 2 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:

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 2 years 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 2 years ago by jdemeyer (previous) (diff)

comment:20 in reply to: ↑ 19 Changed 2 years 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 2 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 2 years 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 2 years ago by tscrim

  • Status changed from needs_review to positive_review

Yep, that was it.

comment:24 Changed 2 years ago by tscrim

  • Keywords days94 added

comment:25 Changed 2 years 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.