random_matrix with sparse=True is very slow

[dfdeshom]

Creating a 2000x2000 full matrix is much faster than creating a 500x500 sparse matrix:

sage: %time A = random_matrix(ZZ,2000)
CPU times: user 0.97 s, sys: 0.28 s, total: 1.25 s
Wall time: 1.25

sage: %time B = random_matrix(ZZ,500,sparse=True)
CPU times: user 7.20 s, sys: 0.00 s, total: 7.20 s
Wall time: 7.20

Component: linear algebra

Keywords: sd31

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

[sagetrac-ryan]

comment:2

could it have anything to do with the fact that a random matrix is not sparse in nature?

[sagetrac-ryan]

comment:4

I noted that even when we specify the density of nonzero entries, a sparse matrix still takes a significant amount of time.

sage: time B = random_matrix(ZZ, 2000, density=.05, sparse=True)
Time: CPU 7.02 s, Wall: 8.77 s
sage: time A = random_matrix(ZZ 2000, density=.05, sparse=False)
Time: CPU 1.20 s, Wall: 1.70 s

[sagetrac-ryan]

comment:5

Well...apparently density=.05 is too dense for a 2000x2000 matrix

sage: time A = random_matrix(QQ, 2000, density=.01, sparse=True)
Time: CPU 2.17 s, Wall: 2.82 s
sage: time A = random_matrix(QQ, 2000, density=.01, sparse=False)
Time: CPU 3.25 s, Wall: 3.57 s

However, sparse matrices in sage are in need of some tender loving care (according to some other sage devs)

[sagetrac-ryan]

Changed keywords from none to sd31

[videlec]

Seems reasonable to me in sage 10.0.beta3

sage: %time A = random_matrix(ZZ 2000, density=.05, sparse=False)
CPU times: user 45.9 ms, sys: 27.9 ms, total: 73.8 ms
Wall time: 72.7 ms

I propose to close as won't fix.

[jhpalmieri]

In 10.2.beta1:

sage: %time A = random_matrix(ZZ, 2000, density=.05, sparse=False)
CPU times: user 38.2 ms, sys: 6.87 ms, total: 45 ms
Wall time: 46.2 ms
sage: %time A = random_matrix(ZZ, 2000, density=.05, sparse=True)
CPU times: user 1.32 s, sys: 26.7 ms, total: 1.35 s
Wall time: 1.37 s

So still a difference. This goes away as the density drops:

sage: %time A = random_matrix(ZZ, 2000, density=.005, sparse=False)
CPU times: user 21.6 ms, sys: 836 µs, total: 22.5 ms
Wall time: 22.8 ms
sage: %time A = random_matrix(ZZ, 2000, density=.005, sparse=True)
CPU times: user 43.9 ms, sys: 2.79 ms, total: 46.7 ms
Wall time: 46.4 ms

I think we can close this.