Jeroen Demeyer on Wed, 23 Sep 2009 20:21:18 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: matkerint versus matsnf

Bill Allombert wrote:
On Wed, Sep 23, 2009 at 06:55:07PM +0200, Jeroen Demeyer wrote:
This is almost exactly what matkerint(,2) does, apart for the final
reduction... However this is still very surprising. What kind of
matrix is that ?
As I said before, a matrix with more columns than rows.

In fact, SNF reduction is not needed, HNF suffices:

fastkerint(M) = {
    my(HU = mathnf(M,1));
    my(dim = #M - #HU[1]);
    my(K = vecextract(HU[2], (1<<dim)-1));
    K * qflll(K);

This gives an LLL-reduced basis and is faster than matkerint() in most cases where the kernel is non-trivial, in particular when the number of columns is more than the number of rows:

gp> M=matrix(50,51,i,j,random(10^6));
time = 4 ms.
gp> K1=matkerint(M);
time = 18,457 ms.
gp> K2=fastkerint(M);
time = 121 ms.
gp> K1 == K2 || K1 == -K2
time = 0 ms.
%138 = 1