Opened 3 years ago
Closed 2 years ago
#25079 closed defect (fixed)
Use _mul_long Matrix*int
Reported by:  SimonKing  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  coercion  Keywords:  Matrix _mul_long 
Cc:  Merged in:  
Authors:  Simon King  Reviewers:  Jeroen Demeyer 
Report Upstream:  N/A  Work issues:  
Branch:  3c4a06d (Commits)  Commit:  3c4a06d3080dd8528053be95b86154822d4d2b79 
Dependencies:  #25476  Stopgaps: 
Description
sage.structure.element does support the use of _mul_long for a multiplication of the form Element*int. However, the multiplication of Matrix*int does not use that shortcut.
In fact, currently only one matrix type implements _mul_long, namely Matrix_gfpn_dense. Unfortunately it uses a conversion that does not coincide with the coercion into the base ring.
So, this ticket is about fixing both issues.
Change History (34)
comment:1 Changed 3 years ago by
 Branch set to u/SimonKing/use__mul_long_matrix_int
comment:2 Changed 3 years ago by
 Commit set to e81581c9cbcb518b7eba0e91639a521015875cce
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
 Commit changed from e81581c9cbcb518b7eba0e91639a521015875cce to a6a63a9f70691d61ae964800c0ce00f0397769c5
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a6a63a9  Enable _mul_long for matrices

comment:4 Changed 3 years ago by
 Commit changed from a6a63a9f70691d61ae964800c0ce00f0397769c5 to 31f085e4c1ad2823bf30174781be12662192e573
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
31f085e  Enable _mul_long for matrices

comment:5 Changed 3 years ago by
Sorry, I had forgotten to add a test. So, I changed the last commit (sorry for the forced push, but nobody was using the old commit yet).
Here is what happens for other matrix types: With the branch:
sage: M = random_matrix(GF(3,'x'), 64,51) sage: %timeit c*M The slowest run took 52.64 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 26 µs per loop
Without the branch:
sage: M = random_matrix(GF(3,'x'), 64,51) sage: %timeit c*M The slowest run took 123.98 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 24.4 µs per loop
So, it seems that enabling _mul_long (which basically means: Using the existing default _mul_long) seems to not slow down the old code substantially.
comment:6 Changed 3 years ago by
All tests pass (with meataxe installed)...
comment:7 Changed 3 years ago by
I might review this, but I would rather do that after the dependencies have been merged.
comment:8 followup: ↓ 10 Changed 3 years ago by
 Status changed from needs_review to needs_work
Already this comment is wrong:
Multiply an MTX matrix with a field element represented by a Python integer.
It's certainly not a Python integer, it's a C long
. It would be fine for me to keep the old wording ("an integer").
comment:9 followup: ↓ 12 Changed 3 years ago by
The code in src/sage/structure/element.pyx
looks strange. It's certainly inefficient because have_same_parent()
calls classify_elements
so you're effectively calling classify_elements
twice. It's also missing the typical return NotImplemented
fallback that other operators have.
comment:10 in reply to: ↑ 8 ; followup: ↓ 11 Changed 3 years ago by
Replying to jdemeyer:
Already this comment is wrong:
Multiply an MTX matrix with a field element represented by a Python integer.It's certainly not a Python integer, it's a C
long
. It would be fine for me to keep the old wording ("an integer").
This ticket is related with an error that was actually solved (but not via _mul_long_
) and was of the form M*int(1)
. That's why I wrote "Python integer".
But if you prefer "C long", I'm fine with it.
comment:11 in reply to: ↑ 10 Changed 3 years ago by
Replying to SimonKing:
This ticket is related with an error that was actually solved (but not via
_mul_long_
) and was of the formM*int(1)
. That's why I wrote "Python integer".
Right, this ticket fixes a problem involving a Python integer. But the function _mul_long
itself has nothing to do with Python integers.
But if you prefer "C long", I'm fine with it.
Either that or revert to the old wording.
comment:12 in reply to: ↑ 9 Changed 3 years ago by
Replying to jdemeyer:
The code in
src/sage/structure/element.pyx
looks strange. It's certainly inefficient becausehave_same_parent()
callsclassify_elements
so you're effectively callingclassify_elements
twice. It's also missing the typicalreturn NotImplemented
fallback that other operators have.
I copied it from some other place of element.pyx
and it may very well be that I did wrong. So, I should call classify_elements
in the beginning and then call HAVE_SAME_PARENT(cl)
instead of have_same_parents
.
And I'll return to the original wording.
comment:13 Changed 3 years ago by
 Commit changed from 31f085e4c1ad2823bf30174781be12662192e573 to 1103493866985a869f2a64d8a2c3b5ab4a74332d
Branch pushed to git repo; I updated commit sha1. New commits:
1103493  Use classify_elements more efficiently

comment:15 Changed 3 years ago by
PS: I repeated the timings that I provided in comment:2 and comment:5.
sage: M = random_matrix(GF(9,'x'), 64,51) sage: type(M) <type 'sage.matrix.matrix_gfpn_dense.Matrix_gfpn_dense'> sage: c = int(4) sage: %timeit M*c The slowest run took 29.39 times longer than the fastest. This could mean that an intermediate result is being cached. 1000000 loops, best of 3: 1.26 µs per loop sage: %timeit c*M The slowest run took 15.87 times longer than the fastest. This could mean that an intermediate result is being cached. 1000000 loops, best of 3: 1.26 µs per loop sage: M = random_matrix(GF(3,'x'), 64,51) sage: type(M) <type 'sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float'> sage: %timeit M*c The slowest run took 53.27 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 20.7 µs per loop sage: %timeit c*M 10000 loops, best of 3: 21 µs per loop
Hence, there is now a slight improvement for Matrix_modn_dense_float (with the old branch, there was a small deterioration), and the improvement for Matrix_gfpn_dense is now even better. So, thank you for spotting the issue with classify_elements
 it had a noticeable effect.
comment:16 followup: ↓ 18 Changed 2 years ago by
 Reviewers set to Jeroen Demeyer
 Status changed from needs_review to needs_work
Can you also add the except TypeError: return NotImplemented
fallback from Element.__mul__
comment:17 Changed 2 years ago by
 Commit changed from 1103493866985a869f2a64d8a2c3b5ab4a74332d to 236024890ba6a7667006f073bd414904d8c22ba9
Branch pushed to git repo; I updated commit sha1. New commits:
2360248  Return NotImplemented when a TypeError occurs in matrix times long

comment:18 in reply to: ↑ 16 Changed 2 years ago by
 Status changed from needs_work to needs_review
Replying to jdemeyer:
Can you also add the
except TypeError: return NotImplemented
fallback fromElement.__mul__
Done, I think.
comment:19 Changed 2 years ago by
Do you have any idea why the patchbot reports failing tests? I don't get those failures.
comment:20 Changed 2 years ago by
 Dependencies #25076 deleted
 Milestone changed from sage8.2 to sage8.3
comment:21 Changed 2 years ago by
Please add tests for multiplying with a negative integer.
comment:22 followup: ↓ 23 Changed 2 years ago by
 Status changed from needs_review to needs_work
Code looks good to me. So once you add the negative integer tests for meataxe, I will run full doctests. If that passes => positive review
comment:23 in reply to: ↑ 22 Changed 2 years ago by
Replying to jdemeyer:
Code looks good to me. So once you add the negative integer tests for meataxe, I will run full doctests. If that passes => positive review
Good catch  there is in fact a bug for multiplication with a negative Python long.
comment:24 Changed 2 years ago by
Problem: Apparently 1%3
evaluates to 1
, not 2
. Is there an easy way to get a nonnegative remainder?
comment:25 followup: ↓ 26 Changed 2 years ago by
Strange enough: I just tried to create cython code in which 1%3
evaluates to 1
, but I failed  but in the MeatAxe wrapper it does evaluate to 1
. Why?
comment:26 in reply to: ↑ 25 ; followup: ↓ 27 Changed 2 years ago by
Replying to SimonKing:
Strange enough: I just tried to create cython code in which
1%3
evaluates to1
, but I failed  but in the MeatAxe wrapper it does evaluate to1
. Why?
The Python convention is rounding down, so 1 divided by 3 gives quotient 1 and remainder 2.
The C convention is truncating, so 1 divided by 3 gives quotient 0 and remainder 1.
Cython always uses the Python convention, unless the cdivision=True
directive is set (which is not the default, but it is set in Sage) and one of the arguments is a C integer.
Examples:
Python integers, always Python convention:
sage: cython(''' ....: print((1) % 3) ....: ''') 2
C integers, result depends on cdivision
:
sage: cython(''' ....: print(<int>(1) % <int>3) ....: ''') 2
sage: cython(''' ....: cimport cython ....: ....: with cython.cdivision(True): ....: print(<int>(1) % <int>3) ....: ''') 1
In fact, it suffices that one of the arguments is a C integer:
sage: cython(''' ....: cimport cython ....: ....: with cython.cdivision(True): ....: print(<int>(1) % 3) ....: ''') 1 sage: cython(''' ....: cimport cython ....: ....: with cython.cdivision(True): ....: print((1) % <int>3) ....: ''') 1
Sage is compiled with cdivision=True
for historical reasons and for efficiency (cdivision=False
adds a bit of overhead for every division of signed C integers).
comment:27 in reply to: ↑ 26 ; followup: ↓ 28 Changed 2 years ago by
Replying to jdemeyer:
Sage is compiled with
cdivision=True
for historical reasons and for efficiency (cdivision=False
adds a bit of overhead for every division of signed C integers).
So, the easiest way out is to use with cython.cdivision(False)
in this single line of code, right?
comment:28 in reply to: ↑ 27 Changed 2 years ago by
Replying to SimonKing:
So, the easiest way out is to use
with cython.cdivision(False)
in this single line of code, right?
Sure.
comment:29 Changed 2 years ago by
 Commit changed from 236024890ba6a7667006f073bd414904d8c22ba9 to 6b17d582db337fab1c87fd3bf0b28e11370ef013
Branch pushed to git repo; I updated commit sha1. New commits:
6b17d58  Fix 'Matrix_gfpn_dense times negative int'

comment:30 Changed 2 years ago by
 Status changed from needs_work to needs_review
Thank you for pointing me to the cdivision directive.
I added a test showing that multiplication with a negative int works, and with that make ptest
passes on my laptop. So, needs review.
comment:31 Changed 2 years ago by
 Branch changed from u/SimonKing/use__mul_long_matrix_int to u/jdemeyer/use__mul_long_matrix_int
comment:32 Changed 2 years ago by
 Commit changed from 6b17d582db337fab1c87fd3bf0b28e11370ef013 to 3c4a06d3080dd8528053be95b86154822d4d2b79
 Dependencies set to #25476
comment:33 Changed 2 years ago by
 Status changed from needs_review to positive_review
comment:34 Changed 2 years ago by
 Branch changed from u/jdemeyer/use__mul_long_matrix_int to 3c4a06d3080dd8528053be95b86154822d4d2b79
 Resolution set to fixed
 Status changed from positive_review to closed
In the current branch, I am basically copying relevant parts of
Element.__mul__
intoMatrix.__mul__
. The timings improve considerably, at least for Matrix_gfpn_dense.Without the branch:
With the branch:
I didn't run the test suite yet, but for now I am asking for review...
New commits:
New MatrixArgs object to deal with constructing matrices
Merge branch 'u/jdemeyer/new_matrixinput_object_to_deal_with_constructing_matrices' of git://trac.sagemath.org/sage into t/25076/fix_matrix_gfpn_dense___int
Add a test ensuring that #24742 remains fixed
Modify the test that ensures that #24742 remains fixed
Enable _mul_long for matrices