Opened 5 years ago

Closed 5 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) Commit: d48c188400d02ee7df99820b30fd8dc6a8f1bfc9
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

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 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/17822
  • Commit set to f7e649670dc0ec095b45471a4b8a39e2773a24c5
  • Status changed from new to needs_review

New commits:

f7e6496trac #17822: faster Matrix_integer_dense

comment:2 Changed 5 years ago by vdelecroix

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
Last edited 5 years ago by vdelecroix (previous) (diff)

comment:3 Changed 5 years ago by jdemeyer

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 5 years ago by git

  • Commit changed from f7e649670dc0ec095b45471a4b8a39e2773a24c5 to f796fa883dea2e337450f3cb7a0edeb78a692655

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

f796fa8trac #17822: use mpz_fits_ulong_p

comment:5 Changed 5 years ago by git

  • Commit changed from f796fa883dea2e337450f3cb7a0edeb78a692655 to 1cb707b613aa01dce6c4c4a50770ace3aec65345

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

1cb707btrac #17822: use mpz_fits_ulong_p

comment:6 Changed 5 years ago by git

  • Commit changed from 1cb707b613aa01dce6c4c4a50770ace3aec65345 to 555bcd26aac17c7c0e8cc4566968d8ffd7a1ff4d

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

555bcd2trac #17822: TypeError -> ArithmeticError in _inverse_flint

comment:7 Changed 5 years ago by vdelecroix

  • Description modified (diff)

comment:8 Changed 5 years ago by git

  • Commit changed from 555bcd26aac17c7c0e8cc4566968d8ffd7a1ff4d to bb38f4b52d27e56907c19538052c871e0a03a632

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

bb38f4btrac #17822: remove duplicated __copy__

comment:9 Changed 5 years ago by jdemeyer

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 5 years ago by git

  • Commit changed from bb38f4b52d27e56907c19538052c871e0a03a632 to 09575df74d198c8f0dba694dcfe94687ebe42afb

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

09575dftrac #17822: remove useless declaration

comment:11 follow-up: Changed 5 years ago by vdelecroix

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 P

since it serves no purpose.

right.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 5 years ago by jdemeyer

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 5 years ago by vdelecroix

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 5 years ago by jdemeyer

  • 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 5 years ago by jdemeyer

  • Commit changed from 09575df74d198c8f0dba694dcfe94687ebe42afb to d48c188400d02ee7df99820b30fd8dc6a8f1bfc9
  • Reviewers set to Jeroen Demeyer

Reviewer patch needs review.


New commits:

d48c188Reviewer patch

comment:16 follow-up: Changed 5 years ago by vdelecroix

What is this Cython syntax for?

cdef Matrix_integer_dense self = <Matrix_integer_dense?>sself

comment:17 follow-up: Changed 5 years ago by jdemeyer

It's a cast with check. In particular, it disallows sself = None.

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:18 in reply to: ↑ 16 Changed 5 years ago by vdelecroix

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 5 years ago by vdelecroix

Replying to jdemeyer:

It's a cast with check. In particular, it disallows sself = None.

sself can be None here!?

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:20 Changed 5 years ago by jdemeyer

If you do None^M with M an integer matrix, then yes.

comment:21 follow-up: Changed 5 years ago by vdelecroix

  • 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 5 years ago by jdemeyer

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 5 years ago by vbraun

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