Speed-up constructor of Matrix_modn_dense_template

[ClementPernet]

When a new matrix mod p with less than 23 bits is constructed, without specifying the intializing value, the constructor still scans the m x n coefficients (all equal to 0) and reduce them mod p.

This eats up a significant portion of the time taken to compute basic operations such as matrix products.

Component: linear algebra

Author: Clément Pernet

Branch/Commit: u/cpernet/speed_up_constructor_of_matrix_modn_dense_template @ 53d0597

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

[ClementPernet]

Branch: u/cpernet/speed_up_constructor_of_matrix_modn_dense_template

[ClementPernet]

Commit: 5182f3c

[ClementPernet]

Author: Clément Pernet

[ClementPernet]

New commits:

5182f3c

skip mod p reduction when no intializatin value is specified

[fchapoton]

comment:3

one possibly related failure in src/sage/matrix/matrix_modn_dense_template.pxi, see patchbot report

[ClementPernet]

comment:4

Yes indeed, I'll look into it.

[sagetrac-git]

Changed commit from 5182f3c to 53d0597

[sagetrac-git]

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

3dbad09	Merge branch 'master' into t/28432/speed_up_constructor_of_matrix_modn_dense_template
53d0597	Merge remote-tracking branch 'origin/develop' into t/28432/speed_up_constructor_of_matrix_modn_dense_template

[embray]

comment:6

Ticket retargeted after milestone closed

[mkoeppe]

comment:7

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:9

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:10

Setting a new milestone for this ticket based on a cursory review.

[vneiger]

Adding @marizee in the loop since this seems related to matrix creation issues we would like to fix.

[marizee]

The issue still stands, we can observe that matrix creation seems slow, which is confirmed when we compare it to the RREF method, or when we compare it to other contexts such as matrices over the rationals or over GF(2).

Here are some tests :

sage: M = MatrixSpace(GF(9001), 10000, 10000, False, None)
sage: %time mat = M.zero_matrix()
CPU times: user 1.07 s, sys: 145 ms, total: 1.21 s
Wall time: 1.21 s

The zero matrix is cached, so subsequent calls are much faster, and one can use
copy :

sage: %timeit mat = copy(M.zero_matrix())
142 ms ± 10.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

But still, this looks like a very long time for creating the zero matrix.

Furthermore, the cached zero matrix is not exploited for example in such calls :

sage: %timeit mat = M(0)
1.16 s ± 13 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit mat = M.zero()
1.17 s ± 2.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

To observe that this is too long, consider the following case :

sage: %timeit mat = zero_matrix(GF(9001), 1000, 1000)
15 ms ± 8.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: mat = random_matrix(GF(9001), 1000, 1000)
sage: %timeit mat[0,0] = 1; r = mat.rref()
115 ms ± 462 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

Here creating the zero matrix is much faster than computing the reduced row
echelon form of a random matrix of the same dimensions.

For other types such as rationals or matrices over GF(2), creation of the zero
matrix is also much faster :

sage: M = MatrixSpace(QQ, 10000, 10000, False, None)
sage: %time mat = M.zero_matrix()
CPU times: user 50.4 ms, sys: 199 ms, total: 249 ms
Wall time: 247 ms

sage: M = MatrixSpace(GF(2), 10000, 10000, False, None)
sage: %time mat = M.zero_matrix()
CPU times: user 707 µs, sys: 3.97 ms, total: 4.68 ms
Wall time: 4.63 ms

[vneiger]

Indeed, seeing that for example creating a matrix over the rationals is much faster (by a factor of 20 !), this issue still stands, and must be considered. I'm not sure that the problem is still that the entries are reduced mod p upon creation, as it was observed when this issue was created back in 2019; this must be investigated further.

Here creating the zero matrix is much faster than computing the reduced row
echelon form of a random matrix of the same dimensions.

I suppose you meant "is not much faster". Yes, this is an interesting comparison, zero_matrix takes almost 15% of the time of rref, which does not seem right for a 1000 x 1000 matrix. We should investigate what happens in the constructor.

[vneiger]

This issue is solved as a part of #35961 (solved via #36093).