Unimodular transformation matrix of LLL algorithm

95 views

Santanu Sarkar

Sep 27, 2020, 8:35:17 AM9/27/20

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

Sep 27, 2020, 10:05:59 AM9/27/20
to sage-devel
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

Hopefully someone can expand on the hints, or even
push a branch to the ticket.

Martin R. Albrecht

Sep 27, 2020, 11:15:33 AM9/27/20
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

Sep 27, 2020, 1:43:45 PM9/27/20
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.

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.

Dima Pasechnik

Sep 27, 2020, 2:20:28 PM9/27/20
to sage-devel

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.

Nils Bruin

Sep 27, 2020, 3:42:00 PM9/27/20
to sage-devel
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.

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

Sep 27, 2020, 4:48:03 PM9/27/20
Dear Nils,
I consider Matrix E=[I,M1], where I is identity matrix.
Then reduction of E took 100 seconds. Hence I am not

Regards,
Santanu

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

Nils Bruin

Sep 27, 2020, 10:57:17 PM9/27/20
to sage-devel

On Sunday, September 27, 2020 at 1:48:03 PM UTC-7, Santanu Sarkar wrote:
Dear Nils,
I consider Matrix E=[I,M1], where I is identity matrix.
Then reduction of E took 100 seconds. Hence I am not

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

Santanu Sarkar

Sep 28, 2020, 8:34:46 AM9/28/20
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,
I consider Matrix E=[I,M1], where I is identity matrix.
Then reduction of E took 100 seconds. Hence I am not

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)

Regards,
Santanu

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

Martin R. Albrecht

Sep 28, 2020, 11:31:11 PM9/28/20
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

Sep 30, 2020, 6:02:14 AM9/30/20
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

Martin R. Albrecht

Oct 2, 2020, 2:38:24 AM10/2/20
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

Oct 2, 2020, 5:39:30 AM10/2/20
to sage-devel
On Fri, Oct 2, 2020 at 7:38 AM 'Martin R. Albrecht' via sage-devel
>
> 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