Opened 8 years ago
Closed 8 years ago
#17822 closed enhancement (fixed)
faster matrix integer dense
Reported by: | vdelecroix | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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 8 years ago by
Branch: | → u/vdelecroix/17822 |
---|---|
Commit: | → f7e649670dc0ec095b45471a4b8a39e2773a24c5 |
Status: | new → needs_review |
comment:2 Changed 8 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 sage-6.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 8 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 8 years ago by
Commit: | f7e649670dc0ec095b45471a4b8a39e2773a24c5 → f796fa883dea2e337450f3cb7a0edeb78a692655 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
f796fa8 | trac #17822: use mpz_fits_ulong_p
|
comment:5 Changed 8 years ago by
Commit: | f796fa883dea2e337450f3cb7a0edeb78a692655 → 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 8 years ago by
Commit: | 1cb707b613aa01dce6c4c4a50770ace3aec65345 → 555bcd26aac17c7c0e8cc4566968d8ffd7a1ff4d |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
555bcd2 | trac #17822: TypeError -> ArithmeticError in _inverse_flint
|
comment:7 Changed 8 years ago by
Description: | modified (diff) |
---|
comment:8 Changed 8 years ago by
Commit: | 555bcd26aac17c7c0e8cc4566968d8ffd7a1ff4d → bb38f4b52d27e56907c19538052c871e0a03a632 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
bb38f4b | trac #17822: remove duplicated __copy__
|
comment:9 Changed 8 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 8 years ago by
Commit: | bb38f4b52d27e56907c19538052c871e0a03a632 → 09575df74d198c8f0dba694dcfe94687ebe42afb |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
09575df | trac #17822: remove useless declaration
|
comment:11 follow-up: 12 Changed 8 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 follow-up: 13 Changed 8 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 Changed 8 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 8 years ago by
Branch: | u/vdelecroix/17822 → u/jdemeyer/ticket/17822 |
---|---|
Created: | Feb 21, 2015, 4:17:00 PM → Feb 21, 2015, 4:17:00 PM |
Modified: | Feb 23, 2015, 2:22:35 PM → Feb 23, 2015, 2:22:35 PM |
comment:15 Changed 8 years ago by
Commit: | 09575df74d198c8f0dba694dcfe94687ebe42afb → d48c188400d02ee7df99820b30fd8dc6a8f1bfc9 |
---|---|
Reviewers: | → Jeroen Demeyer |
comment:16 follow-up: 18 Changed 8 years ago by
What is this Cython syntax for?
cdef Matrix_integer_dense self = <Matrix_integer_dense?>sself
comment:17 follow-up: 19 Changed 8 years ago by
It's a cast with check. In particular, it disallows sself = None
.
comment:18 Changed 8 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 Changed 8 years ago by
Replying to jdemeyer:
It's a cast with check. In particular, it disallows
sself = None
.
sself
can be None
here!?
comment:21 follow-up: 22 Changed 8 years ago by
Status: | needs_review → positive_review |
---|
Thanks for the improvements! (And if you have time, there is the follow up #17824)
comment:22 Changed 8 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 8 years ago by
Branch: | u/jdemeyer/ticket/17822 → d48c188400d02ee7df99820b30fd8dc6a8f1bfc9 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
New commits:
trac #17822: faster Matrix_integer_dense