Re: matkerint versus matsnf

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Wed, Sep 23, 2009 at 08:14:33PM +0200, Jeroen Demeyer wrote:
> 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:

Yes, this is how matkerint(,1) work.

> 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.

Here:
? K1=matkerint(M);
time = 14,848 ms.
? K2=fastkerint(M);
time = 76 ms.
? K3=matkerint(M,1);
time = 737 ms.
? K4=matker(M);
time = 733 ms.

The issue with matkerint(,1) is that it first compute matker(M) and
then the HNF of the result, and thus suffer from rational coefficients
explosion.  Your function fastkerint() seems more straightforward and more
efficient (everthing is done with integers).

Cheers,
Bill.