Opened 10 months ago
Closed 9 months 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 10 months ago by
- Branch set to public/linear_algebra/linbox_rank_sparse_matrix-25257
- Commit set to afc426397e4330b98dbd3eb94f941806d2ecec02
- Description modified (diff)
comment:2 Changed 10 months 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 10 months 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 10 months ago by
(my version has C++ conversions between the mpz_vector *
of Sage and linbox custom datatype)
comment:5 Changed 10 months ago by
But priority is #24544 which fails to compile :-(
comment:6 Changed 10 months 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:7 Changed 10 months ago by
Could you try #23214?
comment:8 Changed 10 months ago by
- Branch public/linear_algebra/linbox_rank_sparse_matrix-25257 deleted
- Commit afc426397e4330b98dbd3eb94f941806d2ecec02 deleted
- Milestone changed from sage-8.2 to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
I would say #23214 superseeds this, which we can close as a duplicate.
comment:9 Changed 10 months ago by
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to positive_review
Thanks for creating this ticket: it motivated me to finish #23214.
comment:10 Changed 10 months ago by
comment:11 Changed 9 months ago by
- Resolution set to wontfix
- Status changed from positive_review to 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.