Opened 2 years ago
Last modified 7 weeks ago
#29315 new enhancement
Make LLL reduction for integer matrix kernel optional
Reported by: | gh-RikVoorhaar | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.7 |
Component: | linear algebra | Keywords: | integer matrices, kernel, speed |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
In the _right_kernel_matrix
method of matrix_integer_dense
there is a choice of 3 algorithms. With choice algorithm='pari'
it calls the matkerint
routine of PARI. According to the documentation this "gives an LLL-reduced ℤ-basis".
The matker(x, flag = 1)
routine omits the LLL-reduction, and for large matrices is much faster. It seems that the padic
and flint
algorithms also compute this LLL-reduced form.
In some applications this LLL reduction is not necessary.
I recommend documenting this fact and making LLL-reduction optional (but perhaps default).
In my particular application all three algorithms about equally fast, but directly calling
M.__pari__().matker(flag=1).mattranspose().sage()
gives a speedup of several orders of magnitude for large matrices. (In my case sparse matrices of shape around 2000x1000.)
Change History (6)
comment:1 Changed 2 years ago by
- Milestone changed from sage-9.1 to sage-9.2
comment:2 Changed 21 months ago by
- Milestone changed from sage-9.2 to sage-9.3
comment:3 Changed 15 months ago by
- Milestone changed from sage-9.3 to sage-9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:4 Changed 10 months ago by
- Milestone changed from sage-9.4 to sage-9.5
comment:5 Changed 5 months ago by
- Milestone changed from sage-9.5 to sage-9.6
comment:6 Changed 7 weeks ago by
- Milestone changed from sage-9.6 to sage-9.7
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.