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: |
Description (last modified by )
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
Branch: | → public/linear_algebra/linbox_rank_sparse_matrix-25257 |
---|---|
Commit: | → afc426397e4330b98dbd3eb94f941806d2ecec02 |
Description: | modified (diff) |
comment:2 Changed 5 years ago by
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.
comment:3 Changed 5 years ago by
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
(my version has C++ conversions between the mpz_vector *
of Sage and linbox custom datatype)
comment:6 Changed 5 years ago by
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:8 Changed 5 years ago by
Authors: | Travis Scrimshaw |
---|---|
Branch: | public/linear_algebra/linbox_rank_sparse_matrix-25257 |
Commit: | afc426397e4330b98dbd3eb94f941806d2ecec02 |
Milestone: | sage-8.2 → sage-duplicate/invalid/wontfix |
Status: | new → needs_review |
I would say #23214 superseeds this, which we can close as a duplicate.
comment:9 Changed 5 years ago by
Reviewers: | → Vincent Delecroix |
---|---|
Status: | needs_review → positive_review |
Thanks for creating this ticket: it motivated me to finish #23214.
comment:10 Changed 5 years ago by
comment:11 Changed 5 years ago by
Resolution: | → wontfix |
---|---|
Status: | positive_review → closed |
closing positively reviewed duplicates
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:
Initial hack of LinBox's rank for sparse matrices.