Opened 10 years ago
Closed 7 years ago
#12051 closed enhancement (fixed)
LLL algorithm for matrices over QQ
Reported by: | dkrenn | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | linear algebra | Keywords: | LLL, rationals, QQ |
Cc: | fschulze | 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 10 years ago by
comment:2 in reply to: ↑ 1 Changed 10 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 10 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 10 years ago by
- Cc fschulze 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 10 years ago by
comment:5 Changed 10 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 10 years ago by
- Dependencies set to #11068
comment:8 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:9 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:10 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:11 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:12 Changed 7 years ago by
- Branch set to public/12051
- Commit set to 9bc18b50d58d5fb4128d925c08d69fff524c420b
comment:13 Changed 7 years ago by
- Description modified (diff)
- Keywords reals RR removed
- Status changed from new to needs_review
- Summary changed from LLL algorithm not available for matrices over QQ or RR to LLL algorithm for matrices over QQ
comment:14 Changed 7 years ago by
Under review.
comment:15 Changed 7 years ago by
- Reviewers set to John Cremona
- Status changed from needs_review to positive_review
Looks good to me, I tried lots of random tests and they work fine.
comment:16 Changed 7 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 changed from public/12051 to 9bc18b50d58d5fb4128d925c08d69fff524c420b
- Resolution set to fixed
- Status changed from positive_review to closed
You mean for matrices over
QQ
andRR
whose entries happen to be integers?