Opened 5 years ago

Closed 2 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) Commit: 9bc18b50d58d5fb4128d925c08d69fff524c420b
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

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 johanbosman 5 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 follow-up: Changed 5 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 5 years ago by dkrenn

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 5 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 5 years ago by fschulze

  • 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 5 years ago by johanbosman

comment:5 Changed 5 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 5 years ago by johanbosman

  • Dependencies set to #11068

comment:7 Changed 5 years ago by johanbosman

  • Dependencies #11068 deleted

Oops, wrong ticket.

comment:8 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:9 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:10 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:12 Changed 2 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:

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

comment:13 Changed 2 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

comment:14 Changed 2 years ago by cremona

Under review.

comment:15 Changed 2 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 2 years ago by drazioti

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

Last edited 2 years ago by drazioti (previous) (diff)

comment:17 Changed 2 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.