Implement rank for sparse integer matrix using LinBox

[tscrim]

Right now the only way to compute the rank of a sparse integer matrix is to either convert it to a dense matrix or a rational matrix (which simply does Gaussian elimination). Both of these options are horrible. Linbox provides a rank algorithm more for sparse matrices. The aim of this ticket is to expose this.

For example, I have a sparse matrix

matrix dims: 11550 x 5775
density: 1/1155
number nonzero positions: 57750

it takes <11s with linbox on my computer, and I gave up after well over minute doing it over Q.

This is a part of #13915.

[tscrim]

Here is an initial branch that is horribly hacked together, but it was sufficient for my purposes and to demonstrate that we should do this.

---

New commits:

​afc4263

Initial hack of LinBox's rank for sparse matrices.

[vdelecroix]

Nice.

Please add tests for all possible corner cases (0 x 1, 1 x 0 and 0 x 0). I had troubles with these with other linbox functions.

I think that it would be better to isolate the conversion dict -> sparse matrix as in #24544 (libs/linbox/conversion.pxd). What do you think? Moreover, the datastructure for sparse integer matrix is not a dict. Converting to a dict is a lot of waste. Though, this can be done in a second time.

[vdelecroix]

BTW, I already have rank/det/solve for sparse matrices on a branch. You might want to wait for next week (Sage days in Cernay).

[vdelecroix]

(my version has C++ conversions between the mpz_vector * of Sage and linbox custom datatype)

[vdelecroix]

But priority is #24544 which fails to compile :-(

[tscrim]

I completely agree with comment:2. I was just trying to get the rank of certain big matrices rather than do rank frequently, so converting from the internal format was not a big issue for me. Again "horribly hacked together" :) I also highly doubt what I've done is the correct, or even good, way to do it too.

I am happy to wait until next week. I will be visiting Sydney, so I probably won't have much time to devote to Sage development next week. However, I am happy to review tickets where I can.

[vdelecroix]

Could you try #23214?

[tscrim]

I would say #23214 superseeds this, which we can close as a duplicate.

[vdelecroix]

Thanks for creating this ticket: it motivated me to finish #23214.

[tscrim]

Thank you for doing a much better job than I did on this ticket. I will try to get to #23214 as soon as I can. I think I have some time in the afternoon tomorrow to properly review it then (too tired tonight to review the #24544 parts).

[vdelecroix]

closing positively reviewed duplicates