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 > > > On Mon, 28 Sep 2020 at 01:12, Nils Bruin <nbr...@sfu.ca <javascript:>> > wrote: > >> 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: >>> >>> >>> >>> On Sun, 27 Sep 2020, 18:43 Santanu Sarkar, <sarkar.s...@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. >>> >>> >>> >>>> Thanks again for your help. >>>> >>>> Regards, >>>> Santanu >>>> >>>> >>>> >>>> On Sun, 27 Sep 2020 at 20:45, 'Martin R. Albrecht' via sage-devel < >>>> sage-...@googlegroups.com> wrote: >>>> >>>>> 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 >>>>> >>>>> >>>>> Santanu Sarkar <sarkar.s...@gmail.com> writes: >>>>> > 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 >>>>> >>>>> >>>>> -- >>>>> >>>>> _pgp: https://keybase.io/martinralbrecht >>>>> _www: https://malb.io >>>>> >>>>> -- >>>>> 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. >>>>> 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. >>>> 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 >>>> >>>> <https://groups.google.com/d/msgid/sage-devel/CAOe8sPLQ8%2BqnGwJq%3DCGTi5f-HcZAJc3%2Bgpe6sf-qASGnvPVRJw%40mail.gmail.com?utm_medium=email&utm_source=footer> >>>> . >>>> >>> -- >> 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 <javascript:>. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/sage-devel/7a0e4e01-74b0-4076-beb5-c8fc4dbb05eeo%40googlegroups.com >> >> <https://groups.google.com/d/msgid/sage-devel/7a0e4e01-74b0-4076-beb5-c8fc4dbb05eeo%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> > -- 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+unsubscr...@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.
