Opened 10 years ago

Closed 7 years ago

# LLL algorithm for matrices over QQ

Reported by: Owned by: dkrenn jason, was major sage-6.4 linear algebra LLL, rationals, QQ fschulze Johan Bosman John Cremona N/A 9bc18b5 9bc18b50d58d5fb4128d925c08d69fff524c420b

Matrices over `QQ` do not have a method `LLL(...)` like matrices over `ZZ`. Here is a simple implementation:

1. get rid of the denominator
2. call the `LLL` method of integer matrices
3. 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.

### comment:1 follow-up: ↓ 2 Changed 10 years ago by mhansen

You mean for matrices over `QQ` and `RR` whose entries happen to be integers?

### comment:2 in reply to: ↑ 1 Changed 10 years ago by dkrenn

You mean for matrices over `QQ` and `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 johanbosman

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 fschulze

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

### comment:5 Changed 10 years ago 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.

### comment:6 Changed 10 years ago by johanbosman

• Dependencies set to #11068

### comment:7 Changed 10 years ago by johanbosman

• Dependencies #11068 deleted

Oops, wrong ticket.

### comment:8 Changed 8 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:9 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:10 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:11 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:12 Changed 7 years ago by vdelecroix

• Branch set to public/12051
• Commit set to 9bc18b50d58d5fb4128d925c08d69fff524c420b

transform the patch into a git branch (and remove trailing whitespaces)

New commits:

 ​644c7b1 `Trac 12051: LLL for matrices over QQ.` ​9bc18b5 `Trac 12051: remove trailing whitespaces`

### comment:13 Changed 7 years ago by vdelecroix

• Authors set to Johan Bosman
• 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

Under review.

### comment:15 Changed 7 years ago by cremona

• 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 drazioti

I use this patch for a long time. I had no problem.

Version 0, edited 7 years ago by drazioti (next)

### comment:17 Changed 7 years ago by vbraun

• Branch changed from public/12051 to 9bc18b50d58d5fb4128d925c08d69fff524c420b
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.