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.

CC: @sagetrac-Bouillaguet @ClementPernet @videlec

Component: linear algebra

Keywords: linbox, sparse matrix

Reviewer: Vincent Delecroix

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

[tscrim]

comment:1

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.

[tscrim]

Branch: public/linear_algebra/linbox_rank_sparse_matrix-25257

[tscrim]

Commit: afc4263

[videlec]

comment:2

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.

[videlec]

comment:3

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

[videlec]

comment:4

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

[videlec]

comment:5

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

[tscrim]

comment:6

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.

[videlec]

comment:7

Could you try #23214?

[tscrim]

Changed author from Travis Scrimshaw to none

[tscrim]

Changed commit from afc4263 to none

[tscrim]

Changed branch from public/linear_algebra/linbox_rank_sparse_matrix-25257 to none

[tscrim]

comment:8

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

[videlec]

comment:9

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

[videlec]

Reviewer: Vincent Delecroix

[tscrim]

comment:10

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

[videlec]

comment:11

closing positively reviewed duplicates