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 Cheers, Jeroen.