Lattice reduction over polynomial lattice

[Santanu Sarkar]

Dear all,

   I have polynomial lattice over a finite field. So each component of the 

vectors v_1, v_2, v_3 are polynomials over a finite field say F_11. Hence 

v_1=(f_1(x), f_2(x), f_3(x)),  v_2=(g_1(x), g_2(x), g_3(x)) and 

v_3=(h_1(x), h_2(x), h_3(x)). Here norm is the maximum degree of each 

 component. Does there exist LLL algorithm for this lattice in Sage? 

[Santanu Sarkar]

Dear all,

  I am searching lattice reduction for polynomial matrices in Sage.

Kindly help me.

T. Mulders and A. Storjohann. On lattice reduction for polynomial matrices.
Journal of Symbolic Computation, 35(4):377 – 401, 2003

[Martin R. Albrecht]

Hi,

I don’t think this is implemented in Sage.

Cheers,
Martin

--

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: martinr...@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

[John Cremona]

On 21 February 2017 at 08:38, 'Martin R. Albrecht' via sage-support

<sage-s...@googlegroups.com> wrote:
> Hi,
>
> I don’t think this is implemented in Sage.

I think it is: searching for weak_popov_form finds results in
matrix/matrix2.pyx with a method M.weak_popov_form(), though
admittedly the docstring for that says

".. WARNING:: This function currently does **not** compute the weak
Popov form of a matrix, but rather a row reduced form (which is a
slightly weaker requirement). See :meth:`row_reduced_form`."

John

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Johan S. R. Nielsen]

Indeed, Sage has row_reduced_form for a polynomial matrix. The row reduced form is sufficient to find a vector in the row space which has minimal degree.

The method used to be called weak_popov_form, but that form is slightly stronger and the algorithm does not compute it. Hence the warning.

The current implementation is very slow. The next beta release of Sage should feature #21024 which introduces an implementation of the Mulders-Storjohann algorithm, which computes the weak Popov form, and does so much faster than the current row_reduced_form (hence, row_reduced_form will, in the future, actually call weak_popov_form). If you are impatient, you can checkout that ticket and recompile Sage to get the new implementation right away.

Best,
Johan

[Santanu Sarkar]

Dear all,

   Thanks a lot for your kind help. 

--

You received this message because you are subscribed to the Google Groups "sage-support" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscribe@googlegroups.com.