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 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 <nbr...@sfu.ca> 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.
>>> 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
> <https://groups.google.com/d/msgid/sage-devel/7ae8410f-f391-4a81-941a-9860d76db8a4o%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/CAOe8sPLR%3DPJAfShCjbQozT0GKxgaR2amO4qH14JCdytgo4wf4g%40mail.gmail.com.
