lllhermite Index error

[tanbur]

I believe there is a bug in the code:
lllhermite(sympy.Matrix([[0,1,0,1],[-1,0,1,0]])
throws an exception. I believe this is because

def lllhermite(G, m1=1, n1=1):
    """
    Input: integer mxn matrix A, nonzero, at least two rows+
    Output: small unimodular matrix B and HNF(A), such that BA=HNF(A)+
    The Havas, Majewski, Matthews LLL method is used+
    We usually take alpha=m1/n1, with (m1,n1)=(1,1) to get best results+
    """
    m = G.shape[0]
    n = G.shape[1]
    A, B, L, D = initialise_working_matrices(G)
    if first_nonzero_is_negative(A):
        B[m, m] = -1
        A[m, :] *= -1

should be:

m = G.shape[0]
n = G.shape[1]
A, B, L, D = initialise_working_matrices(G)
if first_nonzero_is_negative(A):
    B[m-1, m-1] = -1
    A[m-1, :] *= -1

What do you think?

[tclose]

Hi Richard, Thanks for finding this bug. This module is actually just a direct port of Keith Matthews (cc'd) PHP code, so I don't have a good grasp of the algorithm behind it. Since Python and PHP use different index schemes (i.e. Python from 0 and PHP from 1), it is pretty likely that I missed this conversion. So if you would like to make a pull request then I would be happy to merge it. Thanks, Tom

…

On 5 September 2017 at 01:19, Richard Tanburn ***@***.***> wrote: I believe there is a bug in the code: lllhermite(sympy.Matrix([[0,1,0,1],[-1,0,1,0]]) throws an exception. I believe this is because def lllhermite(G, m1=1, n1=1): """ Input: integer mxn matrix A, nonzero, at least two rows+ Output: small unimodular matrix B and HNF(A), such that BA=HNF(A)+ The Havas, Majewski, Matthews LLL method is used+ We usually take alpha=m1/n1, with (m1,n1)=(1,1) to get best results+ """ m = G.shape[0] n = G.shape[1] A, B, L, D = initialise_working_matrices(G) if first_nonzero_is_negative(A): B[m, m] = -1 A[m, :] *= -1 should be: m = G.shape[0] n = G.shape[1] A, B, L, D = initialise_working_matrices(G)if first_nonzero_is_negative(A): B[m-1, m-1] = -1 A[m-1, :] *= -1 What do you think? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABAYlqZ0WCdk3YPe9dG2wv-ySnHaBhzaks5sfBURgaJpZM4PMCmA> .

-- *THOMAS G. CLOSE, PHD* Senior Informatics Officer *Monash Biomedical Imaging* Monash University Room 139, 770 Blackburn Rd Clayton Campus, Clayton VIC 3800 Australia T: +61 3 9902 9804 M: +61 491 141 390 E: tom.close@monash.edu mbi.monash.edu.au

[tclose]

9.50am Brisbane, Wednesday 13th September 2017 Hi Tom and Richard, Yes, in my PHP code, the matrices are indeed indexed from 1 to m, not 0 to m-1, so hopefully that will solve the problem. I'm happy to try out an offending example, to verify that this is the case. By the way, take note of a slight correction to the LLLHNF algorithm mentioned at item 5 of http://www.numbertheory.org/corrections.html Regards Keith Matthews https://www.numbertheory.org/keith.html

…

On Wed, Sep 13, 2017 at 9:29 AM, Thomas Close ***@***.***> wrote: Hi Richard, Thanks for finding this bug. This module is actually just a direct port of Keith Matthews (cc'd) PHP code, so I don't have a good grasp of the algorithm behind it. Since Python and PHP use different index schemes (i.e. Python from 0 and PHP from 1), it is pretty likely that I missed this conversion. So if you would like to make a pull request then I would be happy to merge it. Thanks, Tom On 5 September 2017 at 01:19, Richard Tanburn ***@***.***> wrote: > I believe there is a bug in the code: > lllhermite(sympy.Matrix([[0,1,0,1],[-1,0,1,0]]) > throws an exception. I believe this is because > > def lllhermite(G, m1=1, n1=1): > """ Input: integer mxn matrix A, nonzero, at least two rows+ Output: small unimodular matrix B and HNF(A), such that BA=HNF(A)+ The Havas, Majewski, Matthews LLL method is used+ We usually take alpha=m1/n1, with (m1,n1)=(1,1) to get best results+ """ > m = G.shape[0] > n = G.shape[1] > A, B, L, D = initialise_working_matrices(G) > if first_nonzero_is_negative(A): > B[m, m] = -1 > A[m, :] *= -1 > > should be: > > m = G.shape[0] > n = G.shape[1] > A, B, L, D = initialise_working_matrices(G)if first_nonzero_is_negative(A): > B[m-1, m-1] = -1 > A[m-1, :] *= -1 > > What do you think? > > — > You are receiving this because you are subscribed to this thread. > Reply to this email directly, view it on GitHub > <#2>, or mute the thread > <https://github.com/notifications/unsubscribe-auth/ABAYlqZ0WCdk3YPe9dG2wv-ySnHaBhzaks5sfBURgaJpZM4PMCmA> > . > -- *THOMAS G. CLOSE, PHD* Senior Informatics Officer *Monash Biomedical Imaging* Monash University Room 139, 770 Blackburn Rd <https://maps.google.com/?q=770+Blackburn+Rd&entry=gmail&source=g> Clayton Campus, Clayton VIC 3800 Australia T: +61 3 9902 9804 <+61%203%209902%209804> M: +61 491 141 390 <+61%20491%20141%20390> E: ***@***.*** mbi.monash.edu.au

[tclose]

http://www.numbertheory.org/php/lllhermite1.html gives the answer [1 0 -1 0], which is in HNF. [0 1 0 1] https://www.numbertheory.org/keith.html

…

On Wed, Sep 13, 2017 at 9:52 AM, KEITH MATTHEWS ***@***.***> wrote: 9.50am Brisbane, Wednesday 13th September 2017 Hi Tom and Richard, Yes, in my PHP code, the matrices are indeed indexed from 1 to m, not 0 to m-1, so hopefully that will solve the problem. I'm happy to try out an offending example, to verify that this is the case. By the way, take note of a slight correction to the LLLHNF algorithm mentioned at item 5 of http://www.numbertheory.org/corrections.html Regards Keith Matthews https://www.numbertheory.org/keith.html On Wed, Sep 13, 2017 at 9:29 AM, Thomas Close ***@***.***> wrote: > Hi Richard, > > Thanks for finding this bug. This module is actually just a direct port > of Keith Matthews (cc'd) PHP code, so I don't have a good grasp of the > algorithm behind it. > > Since Python and PHP use different index schemes (i.e. Python from 0 and > PHP from 1), it is pretty likely that I missed this conversion. So if you > would like to make a pull request then I would be happy to merge it. > > Thanks, > > Tom > > On 5 September 2017 at 01:19, Richard Tanburn ***@***.***> > wrote: > >> I believe there is a bug in the code: >> lllhermite(sympy.Matrix([[0,1,0,1],[-1,0,1,0]]) >> throws an exception. I believe this is because >> >> def lllhermite(G, m1=1, n1=1): >> """ Input: integer mxn matrix A, nonzero, at least two rows+ Output: small unimodular matrix B and HNF(A), such that BA=HNF(A)+ The Havas, Majewski, Matthews LLL method is used+ We usually take alpha=m1/n1, with (m1,n1)=(1,1) to get best results+ """ >> m = G.shape[0] >> n = G.shape[1] >> A, B, L, D = initialise_working_matrices(G) >> if first_nonzero_is_negative(A): >> B[m, m] = -1 >> A[m, :] *= -1 >> >> should be: >> >> m = G.shape[0] >> n = G.shape[1] >> A, B, L, D = initialise_working_matrices(G)if first_nonzero_is_negative(A): >> B[m-1, m-1] = -1 >> A[m-1, :] *= -1 >> >> What do you think? >> >> — >> You are receiving this because you are subscribed to this thread. >> Reply to this email directly, view it on GitHub >> <#2>, or mute the thread >> <https://github.com/notifications/unsubscribe-auth/ABAYlqZ0WCdk3YPe9dG2wv-ySnHaBhzaks5sfBURgaJpZM4PMCmA> >> . >> > > > > -- > *THOMAS G. CLOSE, PHD* > Senior Informatics Officer > > *Monash Biomedical Imaging* > Monash University > Room 139, 770 Blackburn Rd > <https://maps.google.com/?q=770+Blackburn+Rd&entry=gmail&source=g> > Clayton Campus, Clayton VIC 3800 > Australia > > T: +61 3 9902 9804 <+61%203%209902%209804> > M: +61 491 141 390 <+61%20491%20141%20390> > E: ***@***.*** > mbi.monash.edu.au >

[tclose]

Hi Keith, Thanks for checking that out. I have merged Richard's changes so that should fix it. Cheers, Tom

…

On 13 September 2017 at 10:42, KEITH MATTHEWS ***@***.***> wrote: http://www.numbertheory.org/php/lllhermite1.html gives the answer [1 0 -1 0], which is in HNF. [0 1 0 1] https://www.numbertheory.org/keith.html On Wed, Sep 13, 2017 at 9:52 AM, KEITH MATTHEWS ***@***.***> wrote: > 9.50am Brisbane, Wednesday 13th September 2017 > Hi Tom and Richard, > Yes, in my PHP code, the matrices are indeed indexed from 1 to m, not > 0 to m-1, so hopefully that will solve the problem. > I'm happy to try out an offending example, to verify that this is the > case. > > By the way, take note of a slight correction to the LLLHNF algorithm > mentioned at item 5 of http://www.numbertheory.org/corrections.html > > Regards > Keith Matthews > > > https://www.numbertheory.org/keith.html > > On Wed, Sep 13, 2017 at 9:29 AM, Thomas Close ***@***.***> > wrote: > >> Hi Richard, >> >> Thanks for finding this bug. This module is actually just a direct port >> of Keith Matthews (cc'd) PHP code, so I don't have a good grasp of the >> algorithm behind it. >> >> Since Python and PHP use different index schemes (i.e. Python from 0 and >> PHP from 1), it is pretty likely that I missed this conversion. So if you >> would like to make a pull request then I would be happy to merge it. >> >> Thanks, >> >> Tom >> >> On 5 September 2017 at 01:19, Richard Tanburn ***@***.***> >> wrote: >> >>> I believe there is a bug in the code: >>> lllhermite(sympy.Matrix([[0,1,0,1],[-1,0,1,0]]) >>> throws an exception. I believe this is because >>> >>> def lllhermite(G, m1=1, n1=1): >>> """ Input: integer mxn matrix A, nonzero, at least two rows+ Output: small unimodular matrix B and HNF(A), such that BA=HNF(A)+ The Havas, Majewski, Matthews LLL method is used+ We usually take alpha=m1/n1, with (m1,n1)=(1,1) to get best results+ """ >>> m = G.shape[0] >>> n = G.shape[1] >>> A, B, L, D = initialise_working_matrices(G) >>> if first_nonzero_is_negative(A): >>> B[m, m] = -1 >>> A[m, :] *= -1 >>> >>> should be: >>> >>> m = G.shape[0] >>> n = G.shape[1] >>> A, B, L, D = initialise_working_matrices(G)if first_nonzero_is_negative(A): >>> B[m-1, m-1] = -1 >>> A[m-1, :] *= -1 >>> >>> What do you think? >>> >>> — >>> You are receiving this because you are subscribed to this thread. >>> Reply to this email directly, view it on GitHub >>> <#2>, or mute the thread >>> <https://github.com/notifications/unsubscribe-auth/ABAYlqZ0WCdk3YPe9dG2wv-ySnHaBhzaks5sfBURgaJpZM4PMCmA> >>> . >>> >> >> >> >> -- >> *THOMAS G. CLOSE, PHD* >> Senior Informatics Officer >> >> *Monash Biomedical Imaging* >> Monash University >> Room 139, 770 Blackburn Rd >> <https://maps.google.com/?q=770+Blackburn+Rd&entry=gmail&source=g> >> Clayton Campus, Clayton VIC 3800 >> Australia >> >> T: +61 3 9902 9804 <+61%203%209902%209804> >> M: +61 491 141 390 <+61%20491%20141%20390> >> E: ***@***.*** >> mbi.monash.edu.au >> > >

-- *THOMAS G. CLOSE, PHD* Senior Informatics Officer *Monash Biomedical Imaging* Monash University Room 139, 770 Blackburn Rd Clayton Campus, Clayton VIC 3800 Australia T: +61 3 9902 9804 M: +61 491 141 390 E: tom.close@monash.edu mbi.monash.edu.au

[berthouz]

Change has been merged in numpy but not master. Is that intentional?

[tclose]

Just merged the new PR into master now

…

On 16 September 2017 at 03:14, berthouz ***@***.***> wrote: Change has been merged in numpy but not master. Is that intentional? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABAYln4kzVIRFj3wlvbB-59zXcK0bcw0ks5sirBpgaJpZM4PMCmA> .

-- *THOMAS G. CLOSE, PHD* Senior Informatics Officer *Monash Biomedical Imaging* Monash University Room 139, 770 Blackburn Rd Clayton Campus, Clayton VIC 3800 Australia T: +61 3 9902 9804 M: +61 491 141 390 E: tom.close@monash.edu mbi.monash.edu.au