On Fri, Oct 2, 2020 at 7:38 AM 'Martin R. Albrecht' via sage-devel <sage-devel@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 > > sage: print(RR(log(abs(U[0][0]),2))) > 1277.66401749439 > > Santanu Sarkar <sarkar.santanu....@gmail.com> writes: > > 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 > > > > On Tue, 29 Sep 2020 at 09:01, 'Martin R. Albrecht' via sage-devel < > > sage-devel@googlegroups.com> wrote: > > > >> 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. > >> > >> Cheers, > >> Martin > >> > >> > >> Santanu Sarkar <sarkar.santanu....@gmail.com> writes: > >> > 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 > >> > > >> > > >> > > >> > On Sun, 27 Sep 2020 at 20:45, 'Martin R. Albrecht' via sage-devel < > >> > sage-devel@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.santanu....@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-devel+unsubscr...@googlegroups.com. > >> >> To view this discussion on the web visit > >> >> > >> https://groups.google.com/d/msgid/sage-devel/87h7rjmesx.fsf%40googlemail.com > >> >> . > >> >> > >> > >> > >> -- > >> > >> _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-devel+unsubscr...@googlegroups.com. > >> To view this discussion on the web visit > >> https://groups.google.com/d/msgid/sage-devel/87blhrm5uu.fsf%40googlemail.com > >> . > >> > > > -- > > _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-devel+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/sage-devel/874knfe0py.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-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq01Wck8wS9qaoCUb8uHcWyL%2BgqamCJDOHrqxmMfbuhcpw%40mail.gmail.com.
