#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)
Change History (10)
comment:1 Changed 7 years ago by
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
- Cc burcin added
comment:3 Changed 7 years ago by
- Reviewers set to John Cremona
- Status changed from needs_review to needs_work
- Work issues set to minor
Changed 7 years ago by
comment:4 Changed 7 years ago by
- 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:
- Yes, C should be N. Both docstrings corrected.
- 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.
- The output for a zero matrix is now consistent with the documentation.
comment:5 Changed 7 years ago by
- Status changed from needs_review to positive_review
Fine! Patch applies fine to 4.4.4.alpha1.
comment:6 Changed 7 years ago by
- Cc mderickx added
comment:7 Changed 7 years ago by
- Cc minz added
comment:8 Changed 7 years ago by
- Merged in set to sage-4.5.2.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
- Work issues minor deleted
Note: See
TracTickets for help on using
tickets.
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.
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.