search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 453 forks source link

weak popov form #9069

Closed 3ef7b55e-0755-45b8-beb1-59dea5994ae8 closed 14 years ago

3ef7b55e-0755-45b8-beb1-59dea5994ae8 commented 14 years ago

Implement weak Popov form for a matrix over a rational function field k(t)

CC: @burcin @koffie @mminzlaff

Component: linear algebra

Author: Christopher Hall

Reviewer: John Cremona

Merged: sage-4.5.2.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/9069

burcin commented 14 years ago

Changed author from cjh to Chris Hall

JohnCremona commented 14 years ago

Reviewer: John Cremona

JohnCremona commented 14 years ago
comment:3

My student David Roberts implemented this in Magma, following the Mulders & Storjohann paper, and used it in the implementation of a lattice-based method for point-finding on curves over function fields F_q(T). So I am familiar with the algorithm. But when I gave a talk about the method in Leiden in 2006, I found that Hendrik Lenstra had never heard of Weak Popov Form, though his brother Arjen Lenstra's thesis (which dates back to the original LLL paper, so they could factor multivariate polynomials) had something entirely equivalent under another name. From what I remember, the upshot is that for most constant fields one might be better off using theory to bound degrees and then using linear algebra over the ground field.

The patch applies fine to 4.4.3 and long tests in the two files touched pass.

  1. line 4545: typo, C should be N? Same i nthe other file & docstring.
  2. In lines 99-105, why not just use an identity matrix?
  3. There is a slight inconsistency in the output for input a zero matrix, since it only has two components. For consistency, also output the third thing, even if it is just a tuple of -Infinity's.

Otherwise it looks ok to me, given that the tests work, but I have not had time to go through the important part of the code in great detail and have no more time right now.

JohnCremona commented 14 years ago

Work Issues: minor

3ef7b55e-0755-45b8-beb1-59dea5994ae8 commented 14 years ago

Attachment: trac_9069.patch.gz

3ef7b55e-0755-45b8-beb1-59dea5994ae8 commented 14 years ago
comment:4

Latest version of the patch incorporates minor changes made in response to Cremona's comments. Specifically, responses to his respective comments are:

  1. Yes, C should be N. Both docstrings corrected.
  2. We now construct N using an identity matrix. Note, the rest of the code expects N to be a list of tuples, hence N isn't an actual matrix.
  3. The output for a zero matrix is now consistent with the documentation.
JohnCremona commented 14 years ago
comment:5

Fine! Patch applies fine to 4.4.4.alpha1.

e14f4152-4982-4ace-8c95-73a0599b109b commented 14 years ago

Changed work issues from minor to none

e14f4152-4982-4ace-8c95-73a0599b109b commented 14 years ago

Merged: sage-4.5.2.alpha0

fchapoton commented 7 years ago

Changed author from Chris Hall to Christopher Hall

fchapoton commented 7 years ago
comment:9

unique name please