Unimodular transformation matrix of LLL algorithm

[Santanu Sarkar]

Dear all,

   I have a matrix M1 with integer entries with 90 rows and 6 columns.

After applying LLL algorithm of M1, I get M2=M1.LLL(). I want to get

corresponding unimodular transformation matrix T such that

T*M1=M2. We can find T by

T=M2*M1.pseudoinverse() or T== M1.solve_left(M2), but determinant of T becomes 0 i.e.,  T.det()=0.

I want T.det()=1.

Best regards,

Santanu

[Samuel Lelievre]

There is a ticket for that with some hints on how to do it.

- Sage Trac ticket 25191

  Add flag for returning LLL transformation matrix

  https://trac.sagemath.org/ticket/25191

Hopefully someone can expand on the hints, or even

push a branch to the ticket.

[Martin R. Albrecht]

Hi there,

This should do the trick:

sage: from fpylll import *
sage: A = random_matrix(ZZ, 6, 90)
sage: U = IntegerMatrix.identity(6)
sage: B = LLL.reduction(IntegerMatrix.from_matrix(A), U).to_matrix(matrix(ZZ, 6,
90))
sage: U = U.to_matrix(matrix(ZZ, 6,6))
sage: B == U*A
True
sage: abs(U.det())
1

Cheers,
Martin

--

_pgp: https://keybase.io/martinralbrecht
_www: https://malb.io

[Santanu Sarkar]

Dear Martin,

    Thank you so much. It works!

Can we make it faster? 

It took 17 seconds for my problem but 

M1.LLL() took only 3 seconds. Of course I understand we 

are calculating extra matrix U.  

Thanks again for your help. 

Regards,

Santanu 

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/87h7rjmesx.fsf%40googlemail.com.

[Dima Pasechnik]

On Sun, 27 Sep 2020, 18:43 Santanu Sarkar, <sarkar.sa...@gmail.com> wrote:

Dear Martin,

    Thank you so much. It works!

Can we make it faster? 

It took 17 seconds for my problem but 

M1.LLL() took only 3 seconds. Of course I understand we 

are calculating extra matrix U.  

one needs to do some Cython programming, as suggested by

the trac ticket mentioned above.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAOe8sPLQ8%2BqnGwJq%3DCGTi5f-HcZAJc3%2Bgpe6sf-qASGnvPVRJw%40mail.gmail.com.

[Nils Bruin]

You could do the same thing as you do with Gaussian elimination to track the row operations: augment the matrix with an identity matrix.

In order for the augmentation to not affect your LLL reduction, you'd want to multiply your original matrix by a large constant, so that the augmented coordinates do not affect the norms significantly.

On Sunday, September 27, 2020 at 11:20:28 AM UTC-7, Dima Pasechnik wrote:

To unsubscribe from this group and stop receiving emails from it, send an email to sage-...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/87h7rjmesx.fsf%40googlemail.com.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sage-...@googlegroups.com.

[Santanu Sarkar]

Dear Nils,

   Thank you so much for your comments.  

I consider Matrix E=[I,M1], where I is identity matrix. 

Then reduction of E took 100 seconds. Hence I am not 

going any advantage. 

Regards,

Santanu 

To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/7a0e4e01-74b0-4076-beb5-c8fc4dbb05eeo%40googlegroups.com.

[Nils Bruin]

On Sunday, September 27, 2020 at 1:48:03 PM UTC-7, Santanu Sarkar wrote:

Dear Nils,

   Thank you so much for your comments.  

I consider Matrix E=[I,M1], where I is identity matrix. 

Then reduction of E took 100 seconds. Hence I am not 

going any advantage. 

Try [10^b*M1,I] with b = 50 or so (it depends on your problem what a "large" number is). I'm not promising that it's faster, but it's worth a try. If you do not scale M1, then I would expect you're getting back different answers, unless all the vectors in the span of M1 already have very large norm.

I now also see that you're looking at a very "overgenerated" lattice (span of 90 vectors in ZZ^6?) Such a lattice almost surely has a very small covolume. I'd expect that just a HNF is actually quite fast to compute. The transformation matrix in such a case is also highly non-unique. It's not so surprising that keeping track of it is very much more expensive in this case (although I'm not sure it explains the full factor that you see).

I'd expect that something like 8 combinations of the 90 generating vectors already generate the same lattice. Now you're looking at LLL-reducing a 8x6 matrix rather than a 90x6 matrix!

 

Regards,

Santanu 

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/7a0e4e01-74b0-4076-beb5-c8fc4dbb05eeo%40googlegroups.com.

[Santanu Sarkar]

Dear Nils,

    Thanks a lot for your help. 

On Mon, 28 Sep 2020 at 08:27, Nils Bruin <nbr...@sfu.ca> wrote:

On Sunday, September 27, 2020 at 1:48:03 PM UTC-7, Santanu Sarkar wrote:

Dear Nils,

   Thank you so much for your comments.  

I consider Matrix E=[I,M1], where I is identity matrix. 

Then reduction of E took 100 seconds. Hence I am not 

going any advantage. 

Try [10^b*M1,I] with b = 50 or so (it depends on your problem what a "large" number is). I'm not promising that it's faster, but it's worth a try. If you do not scale M1, then I would expect you're getting back different answers, unless all the vectors in the span of M1 already have very large norm.

I now also see that you're looking at a very "overgenerated" lattice (span of 90 vectors in ZZ^6?) Such a lattice almost surely has a very small covolume. I'd expect that just a HNF is actually quite fast to compute. The transformation matrix in such a case is also highly non-unique. It's not so surprising that keeping track of it is very much more expensive in this case (although I'm not sure it explains the full factor that you see).

I'd expect that something like 8 combinations of the 90 generating vectors already generate the same lattice. Now you're looking at LLL-reducing a 8x6 matrix rather than a 90x6 matrix!

Yes, 8 vectors generate same lattice. How can we use this information to find a matrix U such that 

UM1=M1.LLL() with determinant of U=\pm 1? I see the following code to find coordinate vectors is very slow

in the actual problem.  

from sage.modules.free_module_integer import IntegerLattice
A = random_matrix(ZZ, 3, 3, x=-2, y=2)

L = IntegerLattice(A, lll_reduce=False);
v=vector([-1,0,0])
print L.coordinates(v)

Please help me. 

Regards,

Santanu 

 

To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/7ae8410f-f391-4a81-941a-9860d76db8a4o%40googlegroups.com.

[Martin R. Albrecht]

Hi there,

Sage is using FP(y)LLL under the hood, so there shouldn’t be that much of a performance difference. As far as I can see, both Sage and FPyLLL have the same defaults so it’s not clear to me why you see this performance difference.

[Santanu Sarkar]

Dear Martin,

  Kindly see the following code.

from fpylll import (IntegerMatrix, LLL)
row=160
col=100
tt=cputime()
A = random_matrix(ZZ,  row,col,x=-2000, y=2000)
U = IntegerMatrix.identity(row)
tt=cputime()
B = LLL.reduction(IntegerMatrix.from_matrix(A), U).to_matrix(matrix(ZZ, row,col))
print cputime(tt)
tt=cputime()
A=A.LLL()
print cputime(tt)

Lattice reduction takes 49 seconds in the first case and 7 seconds in the second case. 

Maybe I am missing something. 

Best regards,

Santanu 

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/87blhrm5uu.fsf%40googlemail.com.

[Martin R. Albrecht]

Seems like the cost of doing business, the entries of U are pretty big:

sage: print(RR(log(abs(U[0][0]),2)))
1277.66401749439

[Dima Pasechnik]

On Fri, Oct 2, 2020 at 7:38 AM 'Martin R. Albrecht' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> Seems like the cost of doing business, the entries of U are pretty big:

Could it be mostly the overhead of treating U as a part of input?
After all, LLL produces a sequence of (sparse?) linear transformations
applied to the input,
doesn't fplll provide a facility to keep track of them?
NTL does offer such an option in its LLL implementation, and while
it's default LLL is slower, U is computed quite fast,
the computation that return U is only two times longer than the one
without returning U.

sage: fl=flatten(list(map(list,list(A))))
sage: M=ntl.mat_ZZ(row,col,fl)
sage: tt=cputime(); rr=M.LLL(); cputime(tt)
18.279667000000018
sage: M=ntl.mat_ZZ(row,col,fl)
sage: tt=cputime(); rr=M.LLL(return_U=True); cputime(tt)
40.468421000000035
sage: tt=cputime(); rr=A.LLL(); cputime(tt)
7.265420000000063

Dima

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/874knfe0py.fsf%40googlemail.com.