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

**Note:**See TracTickets for help on using tickets.

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