Use _mul_long Matrix*int

[simon-king-jena]

sage.structure.element does support the use of _mul_long for a multiplication of the form Elementint. However, the multiplication of Matrixint 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.

Depends on #25476

Component: coercion

Keywords: Matrix _mul_long

Author: Simon King

Branch/Commit: 3c4a06d

Reviewer: Jeroen Demeyer

Issue created by migration from https://trac.sagemath.org/ticket/25079

[simon-king-jena]

Branch: u/SimonKing/use__mul_long_matrix_int

[simon-king-jena]

comment:2

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

[simon-king-jena]

Commit: e81581c

[simon-king-jena]

Author: Simon King

[sagetrac-git]

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

a6a63a9

Enable _mul_long for matrices

[sagetrac-git]

Changed commit from e81581c to a6a63a9

[sagetrac-git]

Changed commit from a6a63a9 to 31f085e

[sagetrac-git]

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

31f085e

Enable _mul_long for matrices

[simon-king-jena]

comment:5

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.

[simon-king-jena]

comment:6

All tests pass (with meataxe installed)...

[jdemeyer]

comment:7

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

[jdemeyer]

comment:8

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]

comment:9

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.

[simon-king-jena]

comment:10

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]

comment:11

Replying to @simon-king-jena:

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.

[simon-king-jena]

comment:12

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.

[sagetrac-git]

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

1103493

Use classify_elements more efficiently

[sagetrac-git]

Changed commit from 31f085e to 1103493

[simon-king-jena]

comment:14

Done!

[simon-king-jena]

comment:15

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]

Reviewer: Jeroen Demeyer

[simon-king-jena]

comment:19

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

[jdemeyer]

Changed dependencies from #25076 to none

[jdemeyer]

comment:21

Please add tests for multiplying with a negative integer.

[jdemeyer]

comment:22

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

[simon-king-jena]

comment:23

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.

[simon-king-jena]

comment:24

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

[simon-king-jena]

comment:25

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]

comment:26

Replying to @simon-king-jena:

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

[simon-king-jena]

comment:27

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]

comment:28

Replying to @simon-king-jena:

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

Sure.

[sagetrac-git]

Changed commit from 2360248 to 6b17d58

[sagetrac-git]

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

6b17d58

Fix 'Matrix_gfpn_dense times negative int'

[simon-king-jena]

comment:30

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]

Changed branch from u/SimonKing/use__mul_long_matrix_int to u/jdemeyer/use__mul_long_matrix_int

[jdemeyer]

comment:32

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

[jdemeyer]

Dependencies: #25476

[jdemeyer]

Changed commit from 6b17d58 to 3c4a06d

[vbraun]

Changed branch from u/jdemeyer/use__mul_long_matrix_int to 3c4a06d