Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-10-02 Thread Dima Pasechnik 
On Fri, Oct 2, 2020 at 7:38 AM 'Martin R. Albrecht' via sage-devel
 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.27966700018
sage: M=ntl.mat_ZZ(row,col,fl)
sage: tt=cputime(); rr=M.LLL(return_U=True); cputime(tt)
40.46842100035
sage: tt=cputime(); rr=A.LLL(); cputime(tt)
7.2654263

Dima




>
> sage: print(RR(log(abs(U[0][0]),2)))
> 1277.66401749439
>
> Santanu Sarkar  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  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  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 sub

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-10-01 Thread 'Martin R. Albrecht' via sage-devel 
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

Santanu Sarkar  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  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  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.

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-30 Thread 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

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

-- 
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/CAOe8sPJP1-ZWg9hnZvRfpU7x7nkyLw7%2BO%2BT8i0Sm8RevbVzQEA%40mail.gmail.com.

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-28 Thread 'Martin R. Albrecht' via sage-devel 
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  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  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.

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-28 Thread Santanu Sarkar 
Dear Nils,
Thanks a lot for your help.

On Mon, 28 Sep 2020 at 08:27, Nils Bruin  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


>
>
>
>
>
>> Regards,
>> Santanu
>>
>>
>> On Mon, 28 Sep 2020 at 01:12, Nils Bruin  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, 
 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  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
>

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-27 Thread 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 
>
>
> On Mon, 28 Sep 2020 at 01:12, Nils Bruin > 
> 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,  
>>> 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  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
  
 
 .

>>> -- 
>> 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/7a0e4e01-74b0-4076-beb5-c8fc4dbb05eeo%40googlegroups.com
>>  
>> 
>> .
>>
>

-- 
You received this message because you are subscribed to the Google Groups

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-27 Thread 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


On Mon, 28 Sep 2020 at 01:12, Nils Bruin  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,  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  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
>>> 
>>> .
>>>
>> --
> 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/7a0e4e01-74b0-4076-beb5-c8fc4dbb05eeo%40googlegroups.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/CAOe8sPKyH3UX3a3spPK2m_maZhPDUKwrALwrspbWgbxmyNHY_A%40mail.gmail.com.

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-27 Thread 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:
>
>
>
> On Sun, 27 Sep 2020, 18:43 Santanu Sarkar,  > 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 > 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
>>  
>> 
>> .
>>
>

-- 
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/7a0e4e01-74b0-4076-beb5-c8fc4dbb05eeo%40googlegroups.com.

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-27 Thread Dima Pasechnik 
On Sun, 27 Sep 2020, 18:43 Santanu Sarkar, 
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-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  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
>> .
>>
> --
> 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/CAOe8sPLQ8%2BqnGwJq%3DCGTi5f-HcZAJc3%2Bgpe6sf-qASGnvPVRJw%40mail.gmail.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/CAAWYfq3B%3DjWihKvPDz5MYqbVVOZPmhbST_yFQj5YOqSZG2X4uA%40mail.gmail.com.

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-27 Thread 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



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

-- 
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/CAOe8sPLQ8%2BqnGwJq%3DCGTi5f-HcZAJc3%2Bgpe6sf-qASGnvPVRJw%40mail.gmail.com.

Re: [sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-27 Thread 'Martin R. Albrecht' via sage-devel 
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  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.

[sage-devel] Unimodular transformation matrix of LLL algorithm

2020-09-27 Thread 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

-- 
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/CAOe8sPL9gocLMRMBLWZ0T6KJ3_u7tqphJi-UBO0rVLGaeWLcbw%40mail.gmail.com.