sagemathgh-39204: Speed up multimodular algorithm in bad case
    
**Edit**: Now flint has fixed
flintlib/flint#2129 , it should be better to
just switch to flint entirely — according to
flintlib/flint#2129 (comment) ,
one of the possible algorithms by flint is multimodular, which should be
faster than or equal to what we're having now. If it is slower in any
case, bug can be reported upstream.

------

Related to sagemath#39197.

Technically the algorithm doesn't deviate from @williamstein  's
original book; however the original book doesn't say *how many*
additional primes to add each time.

The original implementation roughly consider 3 more primes each time.
This can be highly inefficient when there are more columns than rows,
which makes the result's height much higher than the guess.

This increases the length of `M` by roughly a factor of `1.2` each time.
Worst case it makes the algorithm slower by a (hopefully small) constant
factor.

For the added test case, it appears to improve the performance.
(Originally takes 40s, now takes <10s on my machine)

### 📝 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.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ 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#39204
Reported by: user202729
Reviewer(s): Travis Scrimshaw

sagemathgh-39204: Speed up multimodular algorithm in bad case
    
**Edit**: Now flint has fixed
flintlib/flint#2129 , it should be better to
just switch to flint entirely — according to
flintlib/flint#2129 (comment) ,
one of the possible algorithms by flint is multimodular, which should be
faster than or equal to what we're having now. If it is slower in any
case, bug can be reported upstream.

------

Related to sagemath#39197.

Technically the algorithm doesn't deviate from @williamstein  's
original book; however the original book doesn't say *how many*
additional primes to add each time.

The original implementation roughly consider 3 more primes each time.
This can be highly inefficient when there are more columns than rows,
which makes the result's height much higher than the guess.

This increases the length of `M` by roughly a factor of `1.2` each time.
Worst case it makes the algorithm slower by a (hopefully small) constant
factor.

For the added test case, it appears to improve the performance.
(Originally takes 40s, now takes <10s on my machine)

### 📝 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.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ 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#39204
Reported by: user202729
Reviewer(s): Travis Scrimshaw

sagemathgh-39204: Speed up multimodular algorithm in bad case
    
**Edit**: Now flint has fixed
flintlib/flint#2129 , it should be better to
just switch to flint entirely — according to
flintlib/flint#2129 (comment) ,
one of the possible algorithms by flint is multimodular, which should be
faster than or equal to what we're having now. If it is slower in any
case, bug can be reported upstream.

------

Related to sagemath#39197.

Technically the algorithm doesn't deviate from @williamstein  's
original book; however the original book doesn't say *how many*
additional primes to add each time.

The original implementation roughly consider 3 more primes each time.
This can be highly inefficient when there are more columns than rows,
which makes the result's height much higher than the guess.

This increases the length of `M` by roughly a factor of `1.2` each time.
Worst case it makes the algorithm slower by a (hopefully small) constant
factor.

For the added test case, it appears to improve the performance.
(Originally takes 40s, now takes <10s on my machine)

### 📝 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.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ 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#39204
Reported by: user202729
Reviewer(s): Travis Scrimshaw

sagemathgh-39204: Speed up multimodular algorithm in bad case
    
**Edit**: Now flint has fixed
flintlib/flint#2129 , it should be better to
just switch to flint entirely — according to
flintlib/flint#2129 (comment) ,
one of the possible algorithms by flint is multimodular, which should be
faster than or equal to what we're having now. If it is slower in any
case, bug can be reported upstream.

------

Related to sagemath#39197.

Technically the algorithm doesn't deviate from @williamstein  's
original book; however the original book doesn't say *how many*
additional primes to add each time.

The original implementation roughly consider 3 more primes each time.
This can be highly inefficient when there are more columns than rows,
which makes the result's height much higher than the guess.

This increases the length of `M` by roughly a factor of `1.2` each time.
Worst case it makes the algorithm slower by a (hopefully small) constant
factor.

For the added test case, it appears to improve the performance.
(Originally takes 40s, now takes <10s on my machine)

### 📝 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.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ 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#39204
Reported by: user202729
Reviewer(s): Travis Scrimshaw

sagemathgh-39204: Speed up multimodular algorithm in bad case
    
**Edit**: Now flint has fixed
flintlib/flint#2129 , it should be better to
just switch to flint entirely — according to
flintlib/flint#2129 (comment) ,
one of the possible algorithms by flint is multimodular, which should be
faster than or equal to what we're having now. If it is slower in any
case, bug can be reported upstream.

------

Related to sagemath#39197.

Technically the algorithm doesn't deviate from @williamstein  's
original book; however the original book doesn't say *how many*
additional primes to add each time.

The original implementation roughly consider 3 more primes each time.
This can be highly inefficient when there are more columns than rows,
which makes the result's height much higher than the guess.

This increases the length of `M` by roughly a factor of `1.2` each time.
Worst case it makes the algorithm slower by a (hopefully small) constant
factor.

For the added test case, it appears to improve the performance.
(Originally takes 40s, now takes <10s on my machine)

### 📝 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.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ 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#39204
Reported by: user202729
Reviewer(s): Travis Scrimshaw

sagemathgh-39733: Make rational matrix rref default to flint_multimodular, add suboptions for flint algorithm
    
Because one of the algorithms used by flint is multimodular, it ought to
be faster than the implementation in Python.

At least after we upgrade to a version after
flintlib/flint#2129 .

(p/s: if someone uses the old version, the current choice of flint might
be slower in some cases, see the linked issue. An alternative which is
likely always faster is to explicitly use the multimodular algorithm in
flint. Do you think the current implementation is fine, or should we
provide an explicit `flint_multimodular` option instead?)

Fixes sagemath#39197

### 📝 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.
- [x] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->


sagemath#39204
    
URL: sagemath#39733
Reported by: user202729
Reviewer(s): Travis Scrimshaw

sagemathgh-39733: Make rational matrix rref default to flint_multimodular, add suboptions for flint algorithm
    
Because one of the algorithms used by flint is multimodular, it ought to
be faster than the implementation in Python.

At least after we upgrade to a version after
flintlib/flint#2129 .

(p/s: if someone uses the old version, the current choice of flint might
be slower in some cases, see the linked issue. An alternative which is
likely always faster is to explicitly use the multimodular algorithm in
flint. Do you think the current implementation is fine, or should we
provide an explicit `flint_multimodular` option instead?)

Fixes sagemath#39197

### 📝 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.
- [x] I have linked a relevant issue or discussion.
- [ ] I have created tests covering the changes.
- [ ] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->


sagemath#39204
    
URL: sagemath#39733
Reported by: user202729
Reviewer(s): Travis Scrimshaw