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:

Status badges

Description (last modified by Vincent Delecroix)

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.

Attachments (1)

12051_LLL_QQ.patch (1.3 KB) - added by Johan Bosman 11 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 11 years ago by Mike Hansen

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

comment:2 in reply to:  1 Changed 11 years ago by Daniel Krenn

Replying to mhansen:

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 11 years ago by Johan Bosman

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 Frithjof Schulze

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 Johan Bosman

Attachment: 12051_LLL_QQ.patch added

comment:5 Changed 11 years ago by Johan Bosman

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 Johan Bosman

Dependencies: #11068

comment:7 Changed 11 years ago by Johan Bosman

Dependencies: #11068

Oops, wrong ticket.

comment:8 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:9 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:10 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:11 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:12 Changed 8 years ago by Vincent Delecroix

Branch: public/12051
Commit: 9bc18b50d58d5fb4128d925c08d69fff524c420b

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


New commits:

644c7b1Trac 12051: LLL for matrices over QQ.
9bc18b5Trac 12051: remove trailing whitespaces

comment:13 Changed 8 years ago by Vincent Delecroix

Authors: Johan Bosman
Description: modified (diff)
Keywords: reals RR removed
Status: newneeds_review
Summary: LLL algorithm not available for matrices over QQ or RRLLL algorithm for matrices over QQ

comment:14 Changed 8 years ago by John Cremona

Under review.

comment:15 Changed 8 years ago by John Cremona

Reviewers: John Cremona
Status: needs_reviewpositive_review

Looks good to me, I tried lots of random tests and they work fine.

comment:16 Changed 8 years ago by K.A.Draziotis

I use this patch for a long time. I had no problem. I am wondering if a similar patch works for BKZ.

Last edited 8 years ago by K.A.Draziotis (previous) (diff)

comment:17 Changed 7 years ago by Volker Braun

Branch: public/120519bc18b50d58d5fb4128d925c08d69fff524c420b
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.