95 views

Skip to first unread message

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

to sage-...@googlegroups.com

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

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.

Sep 27, 2020, 11:15:33 AM9/27/20

to sage-...@googlegroups.com

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

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

Sep 27, 2020, 1:43:45 PM9/27/20

to sage-...@googlegroups.com

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.

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 butM1.LLL() took only 3 seconds. Of course I understand weare 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.

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.

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.

Sep 27, 2020, 4:48:03 PM9/27/20

to sage-...@googlegroups.com

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.

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

Sep 28, 2020, 8:34:46 AM9/28/20

to sage-...@googlegroups.com

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

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)

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.

Sep 28, 2020, 11:31:11 PM9/28/20

to sage-...@googlegroups.com

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.

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.

Sep 30, 2020, 6:02:14 AM9/30/20

to sage-...@googlegroups.com

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)

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.

Oct 2, 2020, 2:38:24 AM10/2/20

to sage-...@googlegroups.com

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

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

1277.66401749439

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

<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?
<sage-...@googlegroups.com> wrote:

>

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

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu