Add flatter support #40274
Merged
Add flatter support #40274
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 dc5a22f; changes) is ready! 🎉 |
dimpase
reviewed
Jun 25, 2025
| @@ -3097,6 +3101,16 @@ cdef class Matrix_integer_dense(Matrix_dense): | |||
| [0 0 0] | |||
| [0 0 0] | |||
|
|
|||
| When ``algorithm='flatter'``, some matrices are not supported depends | |||
There was a problem hiding this comment.
the sentence is broken. When is a Germanism, too. You want something like
The ``algorithm='flatter'`` might not support matrices supported by other algorithms.
dimpase
reviewed
Jun 25, 2025
| @@ -3024,6 +3024,10 @@ cdef class Matrix_integer_dense(Matrix_dense): | |||
|
|
|||
| - ``'pari'`` -- pari's qflll | |||
|
|
|||
| - ``'flatter'`` -- external executable ``flatter``, requires manual install (see caveats below). | |||
| Note that sufficiently new version of ``pari`` also supports FLATTER algorithm, see | |||
There was a problem hiding this comment.
please provide Pari version info where this appeared. Also, do you know if this already is available from cypari2 ?
There was a problem hiding this comment.
- New recursive implementation of the qflll and qflllgram functions
using the FLATTER reduction algorithm of N. Heninger and K. Ryan.
from https://pari.math.u-bordeaux.fr/archives/pari-announce-24/msg00003.html
so, 2.17.0.
supposedly it's available
sage: pari.version()
(2, 17, 1)
but pari is still slower than flatter on my machine. Demo where LLL is used to compute (integral) kernel of a matrix:
m = random_matrix(ZZ, 25, 50, x=1, y=10^100)
assert m.rank() == 25
%time m.change_ring(QQ).right_kernel_matrix() # 2.5s
%time m.right_kernel_matrix() # 8s
%time m1 = (m.T*2^1200).augment(matrix.identity(50)).LLL(algorithm="pari") # 5s
assert m1[:25,:25]==0
%time m1 = (m.T*2^1200).augment(matrix.identity(50)).LLL(algorithm="flatter") # 3s (CPU time is small because time is spent in subprocess)
assert m1[:25,:25]==0
more:
%time m.right_kernel_matrix(algorithm='flint') # 6s
%time m.right_kernel_matrix(algorithm='pari') # unreasonably long
%time m.right_kernel_matrix(algorithm='padic') # 8.5s
%time m.change_ring(QQ).right_kernel_matrix(algorithm='flint') # 2.2s
%time m.change_ring(QQ).right_kernel_matrix(algorithm='padic') # 2.2s
dimpase
reviewed
Jun 25, 2025
| if fp is not None or early_red or use_givens or transformation or eta is not None or use_siegel: | ||
| raise TypeError("flatter does not support fp, early_red, use_givens, transformation, eta or use_siegel") | ||
| if kwds: | ||
| raise TypeError("flatter does not support additional keywords") |
There was a problem hiding this comment.
would it be more consistent to just ignore kwds here?
There was a problem hiding this comment.
I think it's better practice to complain to the user about invalid data than to silently ignore them.
dimpase
approved these changes
Jun 26, 2025
vbraun
pushed a commit
to vbraun/sage
that referenced
this pull request
Jun 27, 2025
sagemathgh-40274: Add flatter support Supports calling external `flatter` executable for `LLL` algorithm. (If the user wants to use this it is necessary to install from source from https://github.com/keeganryan/flatter) ### 📝 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. - [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#40274 Reported by: user202729 Reviewer(s): Dima Pasechnik, user202729
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.
Supports calling external
flatterexecutable forLLLalgorithm. (If the user wants to use this it is necessary to install from source from https://github.com/keeganryan/flatter)📝 Checklist
⌛ Dependencies