Re: matkerint versus matsnf

[Jeroen Demeyer <jdemeyer@cage.ugent.be>]

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

Cheers,
Jeroen.