#12051: LLL algorithm not available for matrices over QQ or RR
------------------------------+---------------------------------------------
Reporter: dkrenn | Owner: jason, was
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.8
Component: linear algebra | Keywords: LLL, rationals, reals, QQ, RR
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
------------------------------+---------------------------------------------
Comment(by johanbosman):
For RR there is no perfect way to do this; the inexact nature of floating
point arithmetic can make things extremely unpleasant.
Andy suggested the following. Scale and round the input matrix so that
the largest entry has about 300 (or so?) bits. Then augment it with the
identity matrix and perform LLL on the augmented matrix. The augmented
part then contains the basis transformation that has to be performed.
Perform this transformation on the input matrix and repeat the procedure
until things do not improve anymore (e.g. when the largest entry doesn't
decrease anymore).
This sounds good as a general idea, but may fail big time in specific
cases, for instance if the input L is an orthogonal sum L1 + L2 with L1
generated by very small vectors and L2 consisting of very large vectors.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12051#comment:5>
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.
