faster matrix integer dense

[videlec]

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

Component: linear algebra

Author: Vincent Delecroix

Branch/Commit: d48c188

Reviewer: Jeroen Demeyer

Issue created by migration from https://trac.sagemath.org/ticket/17822

[videlec]

New commits:

f7e6496

trac #17822: faster Matrix_integer_dense

[videlec]

Branch: u/vdelecroix/17822

[videlec]

Commit: f7e6496

[videlec]

comment:2

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]

comment:3

Instead of mpz_cmp_ui((<Integer>n).value, ULONG_MAX) < 1:, why not use mpz_fits_ui which is exactly made for that purpose?

[sagetrac-git]

Changed commit from f7e6496 to f796fa8

[sagetrac-git]

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

f796fa8

trac #17822: use mpz_fits_ulong_p

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

[sagetrac-git]

Changed commit from f796fa8 to 1cb707b

[sagetrac-git]

Changed commit from 1cb707b to 555bcd2