Hermite Normal Form

[Santanu Sarkar]

Is there any faster method to compute Hermite Normal Form
  of a matrix  A and corresponding transformation matrix? I use
A.hermite_form(transformation=true). However it is very slow.

Also is there any transformation matrix corresponding to the LLL algorithm.

[luisfe]

On Dec 28, 5:27 pm, Santanu Sarkar <sarkar.santanu....@gmail.com>
wrote:

What are the size/shape of your problem? If you just want the
hermite_form you can use A.hermite_form(algorithm = ...), where the
algorithms available can be checked in A.echelon_form.

If you need transformation = true. Then the method will always be a
padic one, that is asymptotically fast, but may be slow for small
matrices.

Concerning the question of LLL. I may be wrong, but I think that there
is not right now a built-in method to obtain the transformation
matrix. You could solve the linear system of equations

sage: A = random_matrix(ZZ, 25, 50)
sage: B = A.LLL()
sage: trans_matrix = A \ B
sage: A * trans_matrix == B
True

[Santanu Sarkar]

Size of my matrix is (90, 36) with entries are around 2^1000. What is the fastest
method  to compute Hermite Normal Form?

In my matrix number of rows greater than number of columns. That is
A=  random_matrix(ZZ, 90, 36). Then how can I calculate  transformation matrix
of LLL?

--
To post to this group, send email to sage-s...@googlegroups.com
To unsubscribe from this group, send email to sage-support...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-support
URL: http://www.sagemath.org

[luisfe]

On Dec 28, 6:23 pm, Santanu Sarkar <sarkar.santanu....@gmail.com>
wrote:

> Size of my matrix is (90, 36) with entries are around 2^1000. What is the
> fastest
> method to compute Hermite Normal Form?

In that case, the fastest may be the default one you are already
using. Note that computing the Hermite form is fast, the hard part is
computing the transformation matrix.

> In my matrix number of rows greater than number of columns. That is
> A= random_matrix(ZZ, 90, 36). Then how can I calculate transformation
> matrix
> of LLL?

I made a mistake, if the lattice is represented by the rows, then it
is not A\B but trans_matrix = A.solve_left(B), look at the
documentation of the methods.

trans_matrix * A = B

express the rows of B as combinations of rows of A

[Santanu Sarkar]

Thank you very much.

--