#9069: weak popov form
------------------------------+---------------------------------------------
Reporter: cjh | Owner: jason, was
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.4.4
Component: linear algebra | Keywords:
Author: Chris Hall | Upstream: N/A
Reviewer: John Cremona | Merged:
Work_issues: minor |
------------------------------+---------------------------------------------
Changes (by cremona):
* status: needs_review => needs_work
* reviewer: => John Cremona
* work_issues: => minor
Comment:
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9069#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
