Opened 3 years ago
Closed 3 years ago
#25490 closed defect (fixed)
Fix Matrix_gfpn_dense.rescale_row_c
Reported by:  SimonKing  Owned by:  

Priority:  major  Milestone:  sage8.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, GitHub, GitLab)  Commit:  1a97f39ec01d45fb9a59fe9512689e3e35245d52 
Dependencies:  #25518  Stopgaps: 
Description
There are two problems with Matrix_gfpn_dense.rescale_row_c
:
 The optional argument
start_col
is not supported  see also #25476.  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 3 years ago by
 Dependencies set to #25476
comment:2 Changed 3 years ago by
comment:3 Changed 3 years ago by
Sounds good.
comment:4 Changed 3 years ago by
 Branch set to u/SimonKing/fix_matrix_gfpn_dense_rescale_row_c
comment:5 Changed 3 years ago by
 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 followup: ↓ 10 Changed 3 years ago by
PS: I needed to import some additional stuff from SharedMeatAxe, which means that I needed to change sage/libs/meataxe.pxd as well.
comment:7 Changed 3 years ago by
 Dependencies changed from #25476 to #25518
 Status changed from needs_review to needs_work
comment:8 Changed 3 years ago by
 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
 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
comment:11 followups: ↓ 12 ↓ 13 Changed 3 years ago by
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
 Status changed from needs_review to needs_work
comment:13 in reply to: ↑ 11 ; followup: ↓ 14 Changed 3 years ago by
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 worthwhile in terms of speed. In the end, both approaches yield more or less the same C code.
comment:14 in reply to: ↑ 13 ; followup: ↓ 15 Changed 3 years ago by
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 worthwhile 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 ; followup: ↓ 16 Changed 3 years ago by
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 ; followup: ↓ 19 Changed 3 years ago by
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 3 years ago by
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
 Branch changed from u/jdemeyer/fix_matrix_gfpn_dense_rescale_row_c to u/tscrim/fix_matrix_gfpn_dense_rescale_row_c25490
 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 ; followup: ↓ 20 Changed 3 years ago by
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.
comment:20 in reply to: ↑ 19 Changed 3 years ago by
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 followup: ↓ 22 Changed 3 years ago by
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
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 3 years ago by
 Status changed from needs_review to positive_review
Yep, that was it.
comment:24 Changed 3 years ago by
 Keywords days94 added
comment:25 Changed 3 years ago by
 Branch changed from u/tscrim/fix_matrix_gfpn_dense_rescale_row_c25490 to 1a97f39ec01d45fb9a59fe9512689e3e35245d52
 Resolution set to fixed
 Status changed from positive_review to closed
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 anFf*
function for a matrix after calling aMat*
function from MeatAxe, because theMat*
functions all assign the correct field and row size.