Skip to content

Conversation

mkoeppe
Copy link
Contributor

@mkoeppe mkoeppe commented Jun 21, 2023

📚 Description

Follow-ups:

📝 Checklist

  • The title is concise, informative, and self-explanatory.
  • 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

@xuluze @jsantillan3 @discopt

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Jun 21, 2023

Does not build yet; discopt/cmr#29

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Jun 21, 2023

In -minimal configurations, our boost is too old or too cropped

  [cmr-git]   /sage/local/var/tmp/sage/build/cmr-git/src/src/cmr/matroid.hpp:7:10: fatal error: boost/numeric/ublas/matrix.hpp: No such file or directory
  [cmr-git]    #include <boost/numeric/ublas/matrix.hpp>
  [cmr-git]             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  [cmr-git]   compilation terminated.

@github-actions
Copy link

Documentation preview for this PR (built with commit 8341677; changes) is ready! 🎉

vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 23, 2023
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
vbraun pushed a commit to vbraun/sage that referenced this pull request Aug 27, 2023
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
@mkoeppe
Copy link
Contributor Author

mkoeppe commented Dec 11, 2023

Rebased away from the boost upgrade, updated CMR to latest

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Dec 11, 2023

I've adapted the interface to the new CMR version.

There are a few doctest failures that I don't understand

sage -t --random-seed=129552849186103186121087193282398427711 src/sage/matrix/matrix_cmr_sparse.pyx
**********************************************************************
File "src/sage/matrix/matrix_cmr_sparse.pyx", line 734, in sage.matrix.matrix_cmr_sparse.Matrix_cmr_chr_sparse.modulus
Failed example:
    M.modulus()
Expected:
    1
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/matrix/matrix_cmr_sparse.pyx", line 789, in sage.matrix.matrix_cmr_sparse.Matrix_cmr_chr_sparse.strong_modulus
Failed example:
    M.strong_modulus()
Expected:
    1
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/matrix/matrix_cmr_sparse.pyx", line 837, in sage.matrix.matrix_cmr_sparse.Matrix_cmr_chr_sparse.is_k_modular
Failed example:
    M.is_k_modular(1)
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/matrix/matrix_cmr_sparse.pyx", line 876, in sage.matrix.matrix_cmr_sparse.Matrix_cmr_chr_sparse.is_strongly_k_modular
Failed example:
    M.is_strongly_k_modular(1)
Expected:
    True
Got:
    False
**********************************************************************

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Dec 11, 2023

Also I haven't done anything yet on the Python side about the new terminology "equimodular" that CMR now uses.

@xuluze
Copy link
Contributor

xuluze commented Dec 18, 2023

I have encountered the following underflow issue in the parent_rows_and_columns function for a children node.

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: R12_large = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 12, sparse=True), [[1, -1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
....: [0, 0, 0, 1, -1, 0, 0, 0, 1 , 1, 1, 1], 
....: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1], 
....: [ 1,  0,  1,  0,  0,  0,  0,  0,  1,  1,  0,  0],
....: [ 0,  1,  1,  0,  0,  0,  0,  0,  0,  0, -1, -1],
....: [ 0,  0,  0,  1,  0,  1,  0,  0,  1,  1,  0,  0],
....: [ 0,  0,  0,  0,  1,  1,  0,  0,  0,  0, -1, -1],
....: [ 0,  0,  0,  0,  0,  0,  1,  0,  1,  0,  1,  0],
....: [ 0,  0,  0,  0,  0,  0,  0,  1,  0,  1,  0,  1]])
sage: result, certificate = R12_large.is_totally_unimodular(certificate=True)
sage: certificate._children()[0].parent_rows_and_columns()
((2, 7, 8, 0, 3), (6, 7, 8, 9, 10, 11, 18446744073709551615))

Any ideas for how to fix it? Thank you!

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Dec 18, 2023

I see the same on my machine

@discopt
Copy link

discopt commented Dec 18, 2023

I'll can have a look. At least I cannot reproduce it standalone by reading from a file.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Dec 18, 2023

this number is uint64_t(-1)

@discopt
Copy link

discopt commented Dec 18, 2023

I have encountered the following underflow issue in the parent_rows_and_columns function for a children node.

sage: from sage.matrix.matrix_cmr_sparse import Matrix_cmr_chr_sparse
sage: R12_large = Matrix_cmr_chr_sparse(MatrixSpace(ZZ, 9, 12, sparse=True), [[1, -1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
....: [0, 0, 0, 1, -1, 0, 0, 0, 1 , 1, 1, 1], 
....: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1], 
....: [ 1,  0,  1,  0,  0,  0,  0,  0,  1,  1,  0,  0],
....: [ 0,  1,  1,  0,  0,  0,  0,  0,  0,  0, -1, -1],
....: [ 0,  0,  0,  1,  0,  1,  0,  0,  1,  1,  0,  0],
....: [ 0,  0,  0,  0,  1,  1,  0,  0,  0,  0, -1, -1],
....: [ 0,  0,  0,  0,  0,  0,  1,  0,  1,  0,  1,  0],
....: [ 0,  0,  0,  0,  0,  0,  0,  1,  0,  1,  0,  1]])
sage: result, certificate = R12_large.is_totally_unimodular(certificate=True)
sage: certificate._children()[0].parent_rows_and_columns()
((2, 7, 8, 0, 3), (6, 7, 8, 9, 10, 11, 18446744073709551615))

This is exactly the issue of the 3-sum: the submatrix indexed by these rows and columns is (excluding the last one):

 1  1  1  1  1  1
 1  0  1  0  1  0
 0  1  0  1  0  1
 0  0  1  1  1  1
 0  0  1  1  0  0

The SIZE_MAX entry for the last column indicates the artificial column with two 1s in the last rows and 0s otherwise (over F_2):

 1  1  1  1  1  1 0
 1  0  1  0  1  0 0
 0  1  0  1  0  1 0
 0  0  1  1  1  1 1
 0  0  1  1  0  0 1

The second matrix has a SIZE_MAX row as the first row, which means that the first two are 1s and 0s everywhere else (and that this row is not part of the input matrix).

1  1  0  0  0  0  0  0 
1  1  1 -1  0  0  0  0 
1  1  0  0  0  1 -1  0 
1  0  1  0  1  0  0  0 
0 -1  0  1  1  0  0  0 
1  0  0  0  0  1  0  1 
0 -1  0  0  0  0  1  1 

I'm very open to changing this behavior, so we can have a discussion offline.

vbraun pushed a commit to vbraun/sage that referenced this pull request Apr 20, 2024
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
vbraun pushed a commit to vbraun/sage that referenced this pull request Apr 25, 2024
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
@mkoeppe
Copy link
Contributor Author

mkoeppe commented May 14, 2024

Rebased on 10.4.beta6

@mkoeppe
Copy link
Contributor Author

mkoeppe commented May 14, 2024

Haven't tested yet because I can't build on macOS at the moment due to #38002.

@mkoeppe
Copy link
Contributor Author

mkoeppe commented Oct 3, 2024

@xuluze OK to rebase on the current beta version?

@xuluze
Copy link
Contributor

xuluze commented Oct 3, 2024

@xuluze OK to rebase on the current beta version?

Sure

xuluze and others added 30 commits October 13, 2024 16:04
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants