Opened 7 years ago

Closed 7 years ago

Last modified 4 months ago

#9069 closed defect (fixed)

weak popov form

Reported by: cjh Owned by: jason, was
Priority: major Milestone: sage-4.5.2
Component: linear algebra Keywords:
Cc: burcin, mderickx, minz Merged in: sage-4.5.2.alpha0
Authors: Christopher Hall Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (1)

trac_9069.patch (12.3 KB) - added by cjh 7 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 7 years ago by cjh

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by burcin

  • Authors changed from cjh to Chris Hall
  • Cc burcin added

comment:3 Changed 7 years ago by cremona

  • Reviewers set to John Cremona
  • Status changed from needs_review to needs_work
  • Work issues set to minor

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.

Changed 7 years ago by cjh

comment:4 Changed 7 years ago by cjh

  • Status changed from needs_work to needs_review

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.

comment:5 Changed 7 years ago by cremona

  • Status changed from needs_review to positive_review

Fine! Patch applies fine to 4.4.4.alpha1.

comment:6 Changed 7 years ago by mderickx

  • Cc mderickx added

comment:7 Changed 7 years ago by minz

  • Cc minz added

comment:8 Changed 7 years ago by mpatel

  • Merged in set to sage-4.5.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
  • Work issues minor deleted

comment:9 Changed 4 months ago by chapoton

  • Authors changed from Chris Hall to Christopher Hall

unique name please

Note: See TracTickets for help on using tickets.