faster matrix integer dense

[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

[vdelecroix]

New commits:

​f7e6496

trac #17822: faster Matrix_integer_dense

[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

[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?

[git]

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

​f796fa8

trac #17822: use mpz_fits_ulong_p

[git]

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

​1cb707b

trac #17822: use mpz_fits_ulong_p

[git]

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

​555bcd2

trac #17822: TypeError -> ArithmeticError in _inverse_flint

[git]

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

​bb38f4b

trac #17822: remove duplicated __copy__

[jdemeyer]

Why did you move __copy__? It's harder to review that way.

Please remove

cdef object P

since it serves no purpose.

[git]

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

​09575df

trac #17822: remove useless declaration

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

[jdemeyer]

Replying to vdelecroix:

__copy__ is referenced in the list of LEVEL 2 functionalities.

What does this "LEVEL 2 functionalities" mean anyway?

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

[jdemeyer]

Reviewer patch needs review.

---

New commits:

​d48c188

Reviewer patch

[vdelecroix]

What is this Cython syntax for?

cdef Matrix_integer_dense self = <Matrix_integer_dense?>sself

[jdemeyer]

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

[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".

[vdelecroix]

Replying to jdemeyer:

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

sself can be None here!?

[jdemeyer]

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

[vdelecroix]

Thanks for the improvements! (And if you have time, there is the follow up #17824)

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