Opened 5 years ago

Closed 5 years ago

#25257 closed enhancement (wontfix)

Implement rank for sparse integer matrix using LinBox

Reported by: tscrim Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: linear algebra Keywords: linbox, sparse matrix
Cc: Bouillaguet, cpernet, vdelecroix Merged in:
Authors: Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (11)

comment:1 Changed 5 years ago by tscrim

Branch: public/linear_algebra/linbox_rank_sparse_matrix-25257
Commit: afc426397e4330b98dbd3eb94f941806d2ecec02
Description: modified (diff)

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:

afc4263Initial hack of LinBox's rank for sparse matrices.

comment:2 Changed 5 years ago by vdelecroix


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.

comment:3 Changed 5 years ago by 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).

comment:4 Changed 5 years ago by vdelecroix

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

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:5 Changed 5 years ago by vdelecroix

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

comment:6 Changed 5 years ago by 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.

comment:7 Changed 5 years ago by vdelecroix

Could you try #23214?

comment:8 Changed 5 years ago by tscrim

Authors: Travis Scrimshaw
Branch: public/linear_algebra/linbox_rank_sparse_matrix-25257
Commit: afc426397e4330b98dbd3eb94f941806d2ecec02
Milestone: sage-8.2sage-duplicate/invalid/wontfix
Status: newneeds_review

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

comment:9 Changed 5 years ago by vdelecroix

Reviewers: Vincent Delecroix
Status: needs_reviewpositive_review

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

comment:10 Changed 5 years ago by 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).

comment:11 Changed 5 years ago by vdelecroix

Resolution: wontfix
Status: positive_reviewclosed

closing positively reviewed duplicates

Note: See TracTickets for help on using tickets.