Add cmr (Combinatorial Matrix Recognition library) and Cython interface#35801
Add cmr (Combinatorial Matrix Recognition library) and Cython interface#35801mkoeppe wants to merge 262 commits intosagemath:developfrom
cmr (Combinatorial Matrix Recognition library) and Cython interface#35801Conversation
|
Does not build yet; discopt/cmr#29 |
|
In |
|
Documentation preview for this PR (built with commit 8341677; changes) is ready! 🎉 |
sagemathgh-35810: Drop support for GCC < 8.4, drop testing of `debian-buster` and `fedora-29` <!-- Please provide a concise, informative and self-explanatory title. --> <!-- Don't put issue numbers in the title. Put it in the Description below. --> <!-- For example, instead of "Fixes sagemath#12345", use "Add a new method to multiply two integers" --> ### 📚 Description <!-- Describe your changes here in detail. --> <!-- Why is this change required? What problem does it solve? --> Prerequisite of: - sagemath#34816 - sagemath#35703 - sagemath#35801 See also: - sagemath#32074 Instead of fully dropping `debian-buster` (LTS until 2024-06) in the CI, we replace it by `debian-buster-gcc_spkg` to verify that users on this platform have the recourse of installing a newer GCC. We also remove `linuxmint-19.3-gcc_8-python3.8` and change `fedora-30-python3.8` to `fedora-30` (which builds python from spkg), to prevent a merge conflict with sagemath#35404 We also add `debian-trixie` (= current testing). <!-- If this PR resolves an open issue, please link to it here. For example "Fixes sagemath#12345". --> <!-- If your change requires a documentation PR, please link it appropriately. --> ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. It should be `[x]` not `[x ]`. --> - [x] The title is concise, informative, and self-explanatory. - [ ] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on - sagemath#12345: short description why this is a dependency - sagemath#34567: ... --> <!-- If you're unsure about any of these, don't hesitate to ask. We're here to help! --> URL: sagemath#35810 Reported by: Matthias Köppe Reviewer(s): Dima Pasechnik
sagemathgh-35810: Drop support for GCC < 8.4, drop testing of `debian-buster` and `fedora-29` <!-- Please provide a concise, informative and self-explanatory title. --> <!-- Don't put issue numbers in the title. Put it in the Description below. --> <!-- For example, instead of "Fixes sagemath#12345", use "Add a new method to multiply two integers" --> ### 📚 Description <!-- Describe your changes here in detail. --> <!-- Why is this change required? What problem does it solve? --> Prerequisite of: - sagemath#34816 - sagemath#35703 - sagemath#35801 See also: - sagemath#32074 Instead of fully dropping `debian-buster` (LTS until 2024-06) in the CI, we replace it by `debian-buster-gcc_spkg` to verify that users on this platform have the recourse of installing a newer GCC. We also remove `linuxmint-19.3-gcc_8-python3.8` and change `fedora-30-python3.8` to `fedora-30` (which builds python from spkg), to prevent a merge conflict with sagemath#35404 We also add `debian-trixie` (= current testing). <!-- If this PR resolves an open issue, please link to it here. For example "Fixes sagemath#12345". --> <!-- If your change requires a documentation PR, please link it appropriately. --> ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. It should be `[x]` not `[x ]`. --> - [x] The title is concise, informative, and self-explanatory. - [ ] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on - sagemath#12345: short description why this is a dependency - sagemath#34567: ... --> <!-- If you're unsure about any of these, don't hesitate to ask. We're here to help! --> URL: sagemath#35810 Reported by: Matthias Köppe Reviewer(s): Dima Pasechnik
|
Rebased away from the boost upgrade, updated CMR to latest |
|
I've adapted the interface to the new CMR version. There are a few doctest failures that I don't understand |
|
Also I haven't done anything yet on the Python side about the new terminology "equimodular" that CMR now uses. |
|
I have encountered the following underflow issue in the Any ideas for how to fix it? Thank you! |
|
I see the same on my machine |
|
I'll can have a look. At least I cannot reproduce it standalone by reading from a file. |
|
this number is uint64_t(-1) |
This is exactly the issue of the 3-sum: the submatrix indexed by these rows and columns is (excluding the last one): The The second matrix has a I'm very open to changing this behavior, so we can have a discussion offline. |
sagemathgh-37514: `MatrixSpace`: Support constructing `Hom(CombinatorialFreeModule)` <!-- ^ Please provide a concise and informative title. --> <!-- ^ Don't put issue numbers in the title, do this in the PR description below. --> <!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method to calculate 1 + 2". --> <!-- v Describe your changes below in detail. --> <!-- v Why is this change required? What problem does it solve? --> <!-- v If this PR resolves an open issue, please link to it here. For example, "Fixes sagemath#12345". --> The `FreeModule` constructor was recently generalized so that it can create `CombinatorialFreeModule` objects. In particular, ``` sage: ZZ^3 Ambient free module of rank 3 over the principal ideal domain Integer Ring sage: ZZ^['a','b','c'] Free module generated by {'a', 'b', 'c'} over Integer Ring ``` Here as a follow-up, we extend `MatrixSpace` in a similar way: When lists or enumerated sets of row indices and column indices are given, it constructs `CombinatorialFreeModule`s whose bases are indexed by these index sets, and then returns the homset. In particular, ``` sage: ZZ^(2, 3) Full MatrixSpace of 2 by 3 dense matrices over Integer Ring sage: ZZ^(['x','y'], ['a', 'b', 'c']) Set of Morphisms from Free module generated by {'a', 'b', 'c'} over Integer Ring to Free module generated by {'x', 'y'} over Integer Ring in Category of finite dimensional modules with basis over Integer Ring ``` Follow-up PRs: - extend `matrix` likewise; guiding application: adjacency / incidence "matrices" of graphs, where rows/columns are indexed by nodes and edges - see also sagemath#35801 ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [ ] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on. For example, --> <!-- - sagemath#12345: short description why this is a dependency --> <!-- - sagemath#34567: ... --> URL: sagemath#37514 Reported by: Matthias Köppe Reviewer(s): Frédéric Chapoton, gmou3, Matthias Köppe, Travis Scrimshaw
sagemathgh-37514: `MatrixSpace`: Support constructing `Hom(CombinatorialFreeModule)` <!-- ^ Please provide a concise and informative title. --> <!-- ^ Don't put issue numbers in the title, do this in the PR description below. --> <!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method to calculate 1 + 2". --> <!-- v Describe your changes below in detail. --> <!-- v Why is this change required? What problem does it solve? --> <!-- v If this PR resolves an open issue, please link to it here. For example, "Fixes sagemath#12345". --> The `FreeModule` constructor was recently generalized so that it can create `CombinatorialFreeModule` objects. In particular, ``` sage: ZZ^3 Ambient free module of rank 3 over the principal ideal domain Integer Ring sage: ZZ^['a','b','c'] Free module generated by {'a', 'b', 'c'} over Integer Ring ``` Here as a follow-up, we extend `MatrixSpace` in a similar way: When lists or enumerated sets of row indices and column indices are given, it constructs `CombinatorialFreeModule`s whose bases are indexed by these index sets, and then returns the homset. In particular, ``` sage: ZZ^(2, 3) Full MatrixSpace of 2 by 3 dense matrices over Integer Ring sage: ZZ^(['x','y'], ['a', 'b', 'c']) Set of Morphisms from Free module generated by {'a', 'b', 'c'} over Integer Ring to Free module generated by {'x', 'y'} over Integer Ring in Category of finite dimensional modules with basis over Integer Ring ``` Follow-up PRs: - extend `matrix` likewise; guiding application: adjacency / incidence "matrices" of graphs, where rows/columns are indexed by nodes and edges - see also sagemath#35801 ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [ ] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on. For example, --> <!-- - sagemath#12345: short description why this is a dependency --> <!-- - sagemath#34567: ... --> URL: sagemath#37514 Reported by: Matthias Köppe Reviewer(s): Frédéric Chapoton, gmou3, Matthias Köppe, Travis Scrimshaw
|
Rebased on 10.4.beta6 |
|
Haven't tested yet because I can't build on macOS at the moment due to #38002. |
|
@xuluze OK to rebase on the current beta version? |
Sure |
…lar (first version)
add_examples_is_strongly_unimodular
📚 Description
https://discopt.github.io/cmr/, and dependencies
sage.libs.cmrMatrix_cmr_chr_sparseCMR_DEC_...)Matrix_integer_densealong the lines of the existing methodssmith_formetc.; delegate toMatrix_cmr_chr_sparsemethodsbreathe- Sphinx plugin for project documentation using Doxygen #37577)Matroidcorresponding node types of the Seymour decompositionsage.graphs.connectivity.spqr_tree?DecompositionNodeFollow-ups:
sage.tensor.modules: Add methodsis_unimodularetc. #38139📝 Checklist
⌛ Dependencies
cmr/dec.hAPI cannot distinguishCMR_DEC_IRREGULAR,CMR_DEC_UNKNOWN,CMR_DEC_SERIES_PARALLELdiscopt/cmr#32MatrixSpace: Support constructingHom(CombinatorialFreeModule)#37514matrix,Graph.incidence_matrix,LinearMatroid.representation: Support constructingHom(CombinatorialFreeModule)elements #37692@xuluze @jsantillan3 @discopt