LLL_gram() is a good deal faster than checking positive definiteness:
sage: m = random_matrix(ZZ,20)
sage: %time (m*m.transpose()).LLL_gram()
CPU times: user 3.92 s, sys: 0.00 s, total: 3.92 s
Wall time: 3.94 s
200 x 200 dense matrix over Integer Ring
sage: %time (m*m.transpose()).is_positive_definite()
CPU times: user 28.18 s, sys: 0.01 s, total: 28.19 s
Wall time: 28.32 s
True
I guess this means that positive definiteness could be checked much more
efficiently. But for now we should probably just implement
LLL_gram(check=True) in Sage. If checking can be done faster than the
actual computation then we wouldn't need the flag.
On Monday, January 21, 2013 2:04:49 PM UTC, Javier López Peña wrote:
>
> I stand corrected. Note however that lllgramint = qflllgram(-, 1) is
> suggested by pari itself:
>
> ? lllgramint(D)
> *** at top-level: lllgramint(D)
> *** ^-------------
> *** not a function in function call
> A function with that name existed in GP-1.39.15; to run in backward
> compatibility mode, type "default(compatible,3)", or set "compatible = 3"
> in
> your GPRC file.
>
> New syntax: lllgramint(x) ===> qflllgram(x,1)
>
> qflllgram(G,{flag=0}): LLL reduction of the lattice whose gram matrix is G
> (gives the unimodular transformation matrix). flag is optional and can be
> 0:
> default,1: assumes x is integral, 4: assumes x is integral, returns [K,T],
> where K is the integer kernel of x and T the LLL reduced image, 5: same as
> 4
> but x may have polynomial coefficients, 8: same as 0 but x may have
> polynomial
> coefficients.
>
>
>
> Since the pari function does not check for positive-definition maybe we
> should before calling the pari function? Perhaps allowing a flag to disable
> the check for people who need top-speed and know what they are doing.
>
> Cheers,
> J
>
> On Monday, January 21, 2013 1:52:42 PM UTC, Volker Braun wrote:
>>
>> Its not a bug, its undefined behavior for invalid input.
>>
>> Also, I don't think we should ever use lllgramint = qflllgram(-, 1).
>> Thats the toy implementation, you want the adaptive floating point
>> implementation (flag=0) for real work.
>>
>> http://permalink.gmane.org/gmane.comp.mathematics.pari.devel/2480
>>
>>
>> On Monday, January 21, 2013 1:48:22 PM UTC, Javier López Peña wrote:
>>>
>>> Hi Volker,
>>>
>>> I think lllgramint() is deprecated, we should call gflllgram(D,1)
>>> instead.
>>> The bug remains the same though.
>>>
>>> Cheers,
>>> J
>>>
>>> On Monday, January 21, 2013 1:41:35 PM UTC, Volker Braun wrote:
>>>>
>>>>
>>>>
>>>> On Wednesday, December 19, 2012 11:07:03 PM UTC, William wrote:
>>>>>
>>>>> > sage: D=Matrix(IntegerModRing(),
>>>>> [[-1,1,0,1,1,0],[1,-3,1,0,0,0],[0,1,-2,0,0,0],[1,0,0,-3,0,0],[1,0,0,0,-4,1],[0,0,0,0,1,-5]]);D
>>>>>
>>>>> > [-1 1 0 1 1 0]
>>>>> > [ 1 -3 1 0 0 0]
>>>>> > [ 0 1 -2 0 0 0]
>>>>> > [ 1 0 0 -3 0 0]
>>>>> > [ 1 0 0 0 -4 1]
>>>>> > [ 0 0 0 0 1 -5]
>>>>> > sage: X = D.LLL_gram();
>>>>>
>>>>
>>>> This uses Pari lllgramint(), which assumes that the matrix is positive
>>>> definite. If the matrix is not positive definite, Pari may not return.
>>>>
>>>> sage: D.is_positive_definite()
>>>> False
>>>>
>>>>
>>>>
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To post to this group, send email to sage-support@googlegroups.com.
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
