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:

Status badges

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 mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

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.

comment:2 Changed 21 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:3 Changed 15 months ago by mkoeppe

  • 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 mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:5 Changed 5 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:6 Changed 7 weeks ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.