Speed up multimodular algorithm in bad case #39204
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
Documentation preview for this PR (built with commit ce55b7c; changes) is ready! 🎉 |
|
Superseded by #39733 |
|
Even with #39733, I think there is a benefit for speeding up this implementation within Sage (some people might need it for some reason). Should we reopen this? |
|
Up to you, if there's some interest…? At least the change in this pull request is not overly complicated. |
|
I will do the review. I should be able to get to it tomorrow. |
Merged
5 tasks
vbraun
pushed a commit
to vbraun/sage
that referenced
this pull request
Apr 4, 2025
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
vbraun
pushed a commit
to vbraun/sage
that referenced
this pull request
Apr 5, 2025
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
vbraun
pushed a commit
to vbraun/sage
that referenced
this pull request
Apr 7, 2025
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
vbraun
pushed a commit
to vbraun/sage
that referenced
this pull request
Apr 10, 2025
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
vbraun
pushed a commit
to vbraun/sage
that referenced
this pull request
Apr 13, 2025
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
vbraun
pushed a commit
to vbraun/sage
that referenced
this pull request
Apr 13, 2025
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
vbraun
pushed a commit
to vbraun/sage
that referenced
this pull request
Apr 18, 2025
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
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 #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
Mby roughly a factor of1.2each 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
⌛ Dependencies