-
-
Notifications
You must be signed in to change notification settings - Fork 655
Add cmr
(Combinatorial Matrix Recognition library) and Cython interface
#35801
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
base: develop
Are you sure you want to change the base?
Conversation
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.cmr
Matrix_cmr_chr_sparse
CMR_DEC_...
)Matrix_integer_dense
along the lines of the existing methodssmith_form
etc.; delegate toMatrix_cmr_chr_sparse
methodsbreathe
- Sphinx plugin for project documentation using Doxygen #37577)Matroid
corresponding node types of the Seymour decompositionsage.graphs.connectivity.spqr_tree
?DecompositionNode
Follow-ups:
sage.tensor.modules
: Add methodsis_unimodular
etc. #38139📝 Checklist
⌛ Dependencies
cmr/dec.h
API cannot distinguishCMR_DEC_IRREGULAR
,CMR_DEC_UNKNOWN
,CMR_DEC_SERIES_PARALLEL
discopt/cmr#32MatrixSpace
: Support constructingHom(CombinatorialFreeModule)
#37514matrix
,Graph.incidence_matrix
,LinearMatroid.representation
: Support constructingHom(CombinatorialFreeModule)
elements #37692@xuluze @jsantillan3 @discopt