Opened 6 years ago
Closed 6 years ago
#17822 closed enhancement (fixed)
faster matrix integer dense
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  linear algebra  Keywords:  
Cc:  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Jeroen Demeyer 
Report Upstream:  N/A  Work issues:  
Branch:  d48c188 (Commits, GitHub, GitLab)  Commit:  d48c188400d02ee7df99820b30fd8dc6a8f1bfc9 
Dependencies:  Stopgaps: 
Description (last modified by )
We now have a flint implementation of dense integer matrices. The branch proposes various optimization in matrix.matrix_integer_dense
to make it faster.
follow up: #17824
Change History (23)
comment:1 Changed 6 years ago by
 Branch set to u/vdelecroix/17822
 Commit set to f7e649670dc0ec095b45471a4b8a39e2773a24c5
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
new timings:
sage: M = MatrixSpace(ZZ,3) sage: m = M([1,2,3,4,5,6,1,2,3]) sage: %timeit m*m 1000000 loops, best of 3: 1.13 µs per loop sage: %timeit m**3 100000 loops, best of 3: 2.04 µs per loop sage: %timeit m**100 100000 loops, best of 3: 7.71 µs per loop sage: %timeit m**100 1000 loops, best of 3: 377 µs per loop sage: %timeit ~m 10000 loops, best of 3: 37 µs per loop sage: M1 = MatrixSpace(ZZ,4,2) sage: m1 = M1(range(8)) sage: M2 = MatrixSpace(ZZ,3,4) sage: m2 = M2(range(12)) sage: %timeit m2*m1 100000 loops, best of 3: 4.8 µs per loop
same operations on sage6.6.beta0:
sage: M = MatrixSpace(ZZ,3) sage: m = M([1,2,3,4,5,6,1,2,3]) sage: %timeit m*m 100000 loops, best of 3: 4.72 µs per loop sage: %timeit m**3 100000 loops, best of 3: 10.2 µs per loop sage: %timeit m**100 10000 loops, best of 3: 45.8 µs per loop sage: %timeit m**100 1000 loops, best of 3: 462 µs per loop sage: %timeit ~m 1000 loops, best of 3: 138 µs per loop sage: M1 = MatrixSpace(ZZ,4,2) sage: m1 = M1(range(8)) sage: M2 = MatrixSpace(ZZ,3,4) sage: m2 = M2(range(12)) sage: %timeit m2*m1 100000 loops, best of 3: 10.7 µs per loop
comment:3 Changed 6 years ago by
Instead of mpz_cmp_ui((<Integer>n).value, ULONG_MAX) < 1:
, why not use mpz_fits_ui
which is exactly made for that purpose?
comment:4 Changed 6 years ago by
 Commit changed from f7e649670dc0ec095b45471a4b8a39e2773a24c5 to f796fa883dea2e337450f3cb7a0edeb78a692655
Branch pushed to git repo; I updated commit sha1. New commits:
f796fa8  trac #17822: use mpz_fits_ulong_p

comment:5 Changed 6 years ago by
 Commit changed from f796fa883dea2e337450f3cb7a0edeb78a692655 to 1cb707b613aa01dce6c4c4a50770ace3aec65345
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
1cb707b  trac #17822: use mpz_fits_ulong_p

comment:6 Changed 6 years ago by
 Commit changed from 1cb707b613aa01dce6c4c4a50770ace3aec65345 to 555bcd26aac17c7c0e8cc4566968d8ffd7a1ff4d
Branch pushed to git repo; I updated commit sha1. New commits:
555bcd2  trac #17822: TypeError > ArithmeticError in _inverse_flint

comment:7 Changed 6 years ago by
 Description modified (diff)
comment:8 Changed 6 years ago by
 Commit changed from 555bcd26aac17c7c0e8cc4566968d8ffd7a1ff4d to bb38f4b52d27e56907c19538052c871e0a03a632
Branch pushed to git repo; I updated commit sha1. New commits:
bb38f4b  trac #17822: remove duplicated __copy__

comment:9 Changed 6 years ago by
Why did you move __copy__
? It's harder to review that way.
Please remove
cdef object P
since it serves no purpose.
comment:10 Changed 6 years ago by
 Commit changed from bb38f4b52d27e56907c19538052c871e0a03a632 to 09575df74d198c8f0dba694dcfe94687ebe42afb
Branch pushed to git repo; I updated commit sha1. New commits:
09575df  trac #17822: remove useless declaration

comment:11 followup: ↓ 12 Changed 6 years ago by
Replying to jdemeyer:
Why did you move
__copy__
? It's harder to review that way.
__copy__
is referenced in the list of LEVEL 2 functionalities. So I first implement it there and then I discover that it was already in the begining of the file.
Please remove
cdef object Psince it serves no purpose.
right.
comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 6 years ago by
Replying to vdelecroix:
__copy__
is referenced in the list of LEVEL 2 functionalities.
What does this "LEVEL 2 functionalities" mean anyway?
comment:13 in reply to: ↑ 12 Changed 6 years ago by
Replying to jdemeyer:
Replying to vdelecroix:
__copy__
is referenced in the list of LEVEL 2 functionalities.What does this "LEVEL 2 functionalities" mean anyway?
It refers to the crazy organization of the matrix code inside matrix0.pyx
, matrix1.pyx
and matrix2.pyx
.
comment:14 Changed 6 years ago by
 Branch changed from u/vdelecroix/17822 to u/jdemeyer/ticket/17822
 Created changed from 02/21/15 16:17:00 to 02/21/15 16:17:00
 Modified changed from 02/23/15 14:22:35 to 02/23/15 14:22:35
comment:15 Changed 6 years ago by
 Commit changed from 09575df74d198c8f0dba694dcfe94687ebe42afb to d48c188400d02ee7df99820b30fd8dc6a8f1bfc9
 Reviewers set to Jeroen Demeyer
comment:16 followup: ↓ 18 Changed 6 years ago by
What is this Cython syntax for?
cdef Matrix_integer_dense self = <Matrix_integer_dense?>sself
comment:17 followup: ↓ 19 Changed 6 years ago by
It's a cast with check. In particular, it disallows sself = None
.
comment:18 in reply to: ↑ 16 Changed 6 years ago by
Replying to vdelecroix:
What is this Cython syntax for?
cdef Matrix_integer_dense self = <Matrix_integer_dense?>sself
just found out "cast type checked".
comment:19 in reply to: ↑ 17 Changed 6 years ago by
Replying to jdemeyer:
It's a cast with check. In particular, it disallows
sself = None
.
sself
can be None
here!?
comment:20 Changed 6 years ago by
If you do None^M
with M
an integer matrix, then yes.
comment:21 followup: ↓ 22 Changed 6 years ago by
 Status changed from needs_review to positive_review
Thanks for the improvements! (And if you have time, there is the follow up #17824)
comment:22 in reply to: ↑ 21 Changed 6 years ago by
Replying to vdelecroix:
And if you have time, there is the follow up #17824
Not before this one is merged (I rely on the web trac diff view for reviewing which is only reliable if all dependencies have been merged).
comment:23 Changed 6 years ago by
 Branch changed from u/jdemeyer/ticket/17822 to d48c188400d02ee7df99820b30fd8dc6a8f1bfc9
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #17822: faster Matrix_integer_dense