Opened 11 years ago
Closed 7 years ago
#12051 closed enhancement (fixed)
LLL algorithm for matrices over QQ
Reported by: | Daniel Krenn | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | linear algebra | Keywords: | LLL, rationals, QQ |
Cc: | Frithjof Schulze | Merged in: | |
Authors: | Johan Bosman | Reviewers: | John Cremona |
Report Upstream: | N/A | Work issues: | |
Branch: | 9bc18b5 (Commits, GitHub, GitLab) | Commit: | 9bc18b50d58d5fb4128d925c08d69fff524c420b |
Dependencies: | Stopgaps: |
Description (last modified by )
Matrices over QQ
do not have a method LLL(...)
like matrices over ZZ
. Here is a simple implementation:
- get rid of the denominator
- call the
LLL
method of integer matrices - set the denominator back.
Note: in previous version it was suggested that such an approach might be useful for matrices over RR
. But it is not completely clear how to do that efficiently.
Attachments (1)
Change History (18)
comment:1 follow-up: 2 Changed 11 years ago by
comment:2 Changed 11 years ago by
Replying to mhansen:
You mean for matrices over
RR
whose entries happen to be integers?
No. A strategy could be the following: For matrices over QQ
you can multiply by the least common multiple of all denominators to get a matrix over ZZ
, then apply LLL, and then scale back. For matrices over the reals (which are of finite precision), do also some scaling to get an integer-matrix.
comment:3 Changed 11 years ago by
It would definitely be good to have this! For QQ, the proposed strategy obviously works. For RR, it probably needs some thought what sort of scaling to do here. For instance, if the matrix has very large as well as very small entries.
comment:4 Changed 11 years ago by
Cc: | Frithjof Schulze added |
---|
We asked Andy Novocin about the case of matrices over RR
. If one wants to use LLL for rational number reconstruction and has lots of decimal digits he proposed the algorithm in http://www.cs.uwaterloo.ca/~astorjoh/issac11ratrecon.pdf
Changed 11 years ago by
Attachment: | 12051_LLL_QQ.patch added |
---|
comment:5 Changed 11 years ago by
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.
comment:6 Changed 11 years ago by
Dependencies: | → #11068 |
---|
comment:8 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:9 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:10 Changed 8 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:11 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:12 Changed 8 years ago by
Branch: | → public/12051 |
---|---|
Commit: | → 9bc18b50d58d5fb4128d925c08d69fff524c420b |
comment:13 Changed 8 years ago by
Authors: | → Johan Bosman |
---|---|
Description: | modified (diff) |
Keywords: | reals RR removed |
Status: | new → needs_review |
Summary: | LLL algorithm not available for matrices over QQ or RR → LLL algorithm for matrices over QQ |
comment:15 Changed 8 years ago by
Reviewers: | → John Cremona |
---|---|
Status: | needs_review → positive_review |
Looks good to me, I tried lots of random tests and they work fine.
comment:16 Changed 8 years ago by
I use this patch for a long time. I had no problem. I am wondering if a similar patch works for BKZ.
comment:17 Changed 7 years ago by
Branch: | public/12051 → 9bc18b50d58d5fb4128d925c08d69fff524c420b |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
You mean for matrices over
QQ
andRR
whose entries happen to be integers?