Use _mul_long Matrix*int

[SimonKing]

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 short-cut.

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.

[SimonKing]

In the current branch, I am basically copying relevant parts of Element.__mul__ into Matrix.__mul__. The timings improve considerably, at least for Matrix_gfpn_dense.

Without the branch:

sage: M = random_matrix(GF(9,'x'), 64,51)
sage: c = int(4)
sage: %timeit M*c
The slowest run took 173.53 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 10.3 µs per loop
sage: %timeit c*M
The slowest run took 34.51 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 10.2 µs per loop

With the branch:

sage: M = random_matrix(GF(9,'x'), 64,51)
sage: c = int(4)
sage: %timeit M*c
The slowest run took 25.57 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.53 µs per loop
sage: %timeit c*M
The slowest run took 26.66 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.57 µs per loop

I didn't run the test suite yet, but for now I am asking for review...

---

New commits:

​bf9cefd	New MatrixArgs object to deal with constructing matrices
​cc82825	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
​bed63f0	Add a test ensuring that #24742 remains fixed
​f0e97af	Modify the test that ensures that #24742 remains fixed
​e81581c	Enable _mul_long for matrices

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a6a63a9

Enable _mul_long for matrices

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​31f085e

Enable _mul_long for matrices

[SimonKing]

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.

[SimonKing]

All tests pass (with meataxe installed)...

[jdemeyer]

I might review this, but I would rather do that after the dependencies have been merged.

[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").

[jdemeyer]

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.

[SimonKing]

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.

[jdemeyer]

Replying to SimonKing:

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".

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.

[SimonKing]

Replying to jdemeyer:

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.

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.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​1103493

Use classify_elements more efficiently

[SimonKing]

Done!

[SimonKing]

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.

[jdemeyer]

Can you also add the except TypeError: return NotImplemented fallback from Element.__mul__

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2360248

Return NotImplemented when a TypeError occurs in matrix times long

[SimonKing]

Replying to jdemeyer:

Can you also add the except TypeError: return NotImplemented fallback from Element.__mul__

Done, I think.

[SimonKing]

Do you have any idea why the patchbot reports failing tests? I don't get those failures.

[jdemeyer]

Please add tests for multiplying with a negative integer.

[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

[SimonKing]

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.

[SimonKing]

Problem: Apparently -1%3 evaluates to -1, not 2. Is there an easy way to get a non-negative remainder?

[SimonKing]

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?

[jdemeyer]

Replying to SimonKing:

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?

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).

[SimonKing]

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?

[jdemeyer]

Replying to SimonKing:

So, the easiest way out is to use with cython.cdivision(False) in this single line of code, right?

Sure.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6b17d58

Fix 'Matrix_gfpn_dense times negative int'

[SimonKing]

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.

[jdemeyer]

Rebased on top of #25476.

---

New commits:

​4eae803	Making matrices use the new _echelon_in_place method.
​e2f0550	Specify that _echelon_in_place shall return the pivots
​3c4a06d	Enable _mul_long for matrices