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: sage-8.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 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.

Change History (34)

comment:1 Changed 3 years ago by SimonKing

  • Branch set to u/SimonKing/use__mul_long_matrix_int

comment:2 Changed 3 years ago by SimonKing

  • Authors set to Simon King
  • Commit set to e81581c9cbcb518b7eba0e91639a521015875cce
  • Status changed from new to needs_review

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:

bf9cefdNew MatrixArgs object to deal with constructing matrices
cc82825Merge 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
bed63f0Add a test ensuring that #24742 remains fixed
f0e97afModify the test that ensures that #24742 remains fixed
e81581cEnable _mul_long for matrices

comment:3 Changed 3 years ago by git

  • Commit changed from e81581c9cbcb518b7eba0e91639a521015875cce to a6a63a9f70691d61ae964800c0ce00f0397769c5

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

a6a63a9Enable _mul_long for matrices

comment:4 Changed 3 years ago by git

  • Commit changed from a6a63a9f70691d61ae964800c0ce00f0397769c5 to 31f085e4c1ad2823bf30174781be12662192e573

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

31f085eEnable _mul_long for matrices

comment:5 Changed 3 years ago by 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.

comment:6 Changed 3 years ago by SimonKing

All tests pass (with meataxe installed)...

comment:7 Changed 3 years ago by jdemeyer

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

comment:8 follow-up: Changed 3 years ago by jdemeyer

  • 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 follow-up: Changed 3 years ago by 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.

comment:10 in reply to: ↑ 8 ; follow-up: Changed 3 years ago by 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.

comment:11 in reply to: ↑ 10 Changed 3 years ago by 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.

comment:12 in reply to: ↑ 9 Changed 3 years ago by 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.

comment:13 Changed 3 years ago by git

  • Commit changed from 31f085e4c1ad2823bf30174781be12662192e573 to 1103493866985a869f2a64d8a2c3b5ab4a74332d

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

1103493Use classify_elements more efficiently

comment:14 Changed 3 years ago by SimonKing

  • Status changed from needs_work to needs_review

Done!

comment:15 Changed 3 years ago by 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.

comment:16 follow-up: Changed 2 years ago by jdemeyer

  • 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 git

  • Commit changed from 1103493866985a869f2a64d8a2c3b5ab4a74332d to 236024890ba6a7667006f073bd414904d8c22ba9

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

2360248Return NotImplemented when a TypeError occurs in matrix times long

comment:18 in reply to: ↑ 16 Changed 2 years ago by SimonKing

  • Status changed from needs_work to needs_review

Replying to jdemeyer:

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

Done, I think.

comment:19 Changed 2 years ago by SimonKing

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

comment:20 Changed 2 years ago by jdemeyer

  • Dependencies #25076 deleted
  • Milestone changed from sage-8.2 to sage-8.3

comment:21 Changed 2 years ago by jdemeyer

Please add tests for multiplying with a negative integer.

comment:22 follow-up: Changed 2 years ago by jdemeyer

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

comment:24 Changed 2 years ago by SimonKing

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

comment:25 follow-up: Changed 2 years ago by 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?

comment:26 in reply to: ↑ 25 ; follow-up: Changed 2 years ago by 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).

comment:27 in reply to: ↑ 26 ; follow-up: Changed 2 years ago by 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?

comment:28 in reply to: ↑ 27 Changed 2 years ago by jdemeyer

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 git

  • Commit changed from 236024890ba6a7667006f073bd414904d8c22ba9 to 6b17d582db337fab1c87fd3bf0b28e11370ef013

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

6b17d58Fix 'Matrix_gfpn_dense times negative int'

comment:30 Changed 2 years ago by SimonKing

  • 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 jdemeyer

  • 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 jdemeyer

  • Commit changed from 6b17d582db337fab1c87fd3bf0b28e11370ef013 to 3c4a06d3080dd8528053be95b86154822d4d2b79
  • Dependencies set to #25476

Rebased on top of #25476.


New commits:

4eae803Making matrices use the new _echelon_in_place method.
e2f0550Specify that _echelon_in_place shall return the pivots
3c4a06dEnable _mul_long for matrices

comment:33 Changed 2 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:34 Changed 2 years ago by vbraun

  • Branch changed from u/jdemeyer/use__mul_long_matrix_int to 3c4a06d3080dd8528053be95b86154822d4d2b79
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.