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 notifications@github.com 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 https://github.com/tclose/Diophantine/issues/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 tom.close@monash.edu 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 notifications@github.com 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 https://github.com/tclose/Diophantine/issues/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: tom.close@monash.edu 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 keithmatt@gmail.com 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 tom.close@monash.edu 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 notifications@github.com 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 https://github.com/tclose/Diophantine/issues/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: tom.close@monash.edu 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 keithmatt@gmail.com 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 keithmatt@gmail.com 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 tom.close@monash.edu 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 notifications@github.com 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 https://github.com/tclose/Diophantine/issues/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: tom.close@monash.edu 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 notifications@github.com 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 https://github.com/tclose/Diophantine/issues/2#issuecomment-329843223, 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