Opened 4 years ago

Closed 18 months ago

#25191 closed enhancement (fixed)

Add flag for returning LLL transformation matrix

Reported by: pbruin Owned by:
Priority: major Milestone: sage-9.3
Component: linear algebra Keywords: LLL
Cc: malb, slelievre Merged in:
Authors: Martin Albrecht Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 098245f (Commits, GitHub, GitLab) Commit: 098245f11b01ec3f12777112c34f7407dc7f5452
Dependencies: Stopgaps:

Status badges

Description

The method sage.matrix.matrix_integer_dense.Matrix_integer_dense.LLL accepts extra keywords, which are supposed to be passed to fpylll in case fplll is used. However, these are currently ignored.

The kwds argument could be used to request LLL to return the transformation matrix to the LLL-reduced basis instead of the basis itself. Perhaps a better solution would be to remove kwds and to add a separate argument for such a flag.

See also #12050.

Change History (11)

comment:2 Changed 21 months ago by malb

  • Branch set to u/malb/lll-transformation-matrix

comment:3 Changed 21 months ago by malb

  • Authors set to Martin Albrecht
  • Commit set to 4ca158a626da65b0204a566409a79fdcaa1f4ab6
  • Status changed from new to needs_review

New commits:

4ca158aadd a transformation option to LLL()

comment:4 Changed 21 months ago by dimpase

the branch say that returning the transform is not implemented in NTL, but IMHO it does, as I wrote:

row=16
col=10
tt=cputime()
A = random_matrix(ZZ,  row,col,x=-2000, y=2000)
fl=flatten(list(map(list,list(A))))
M=ntl.mat_ZZ(row,col,fl)
tt=cputime(); rr=M.LLL(return_U=True); cputime(tt)

you can read in M.LLL? that

   If return_U is True, a value U is returned which is the
   transformation matrix, so that U is a unimodular m x m matrix with
   U * old-self = new-self. Note that the first m-r rows of U form a
   basis (as a lattice) for the kernel of old-B.

comment:5 Changed 21 months ago by git

  • Commit changed from 4ca158a626da65b0204a566409a79fdcaa1f4ab6 to b02a25ac9aec3244264c10f5f2755ed3adba4c61

Branch pushed to git repo; I updated commit sha1. New commits:

b02a25atransformation matrices for NTL's LLLs

comment:6 Changed 21 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:7 follow-up: Changed 18 months ago by chapoton

  • why the changes in nlt_mat_ZZ ?
  • This line should end with a double colon
    +        We return the transformation matrix:
    
  • This sentence looks wrong now : Not implemented in case of NTL.

comment:8 Changed 18 months ago by dimpase

  • Branch changed from u/malb/lll-transformation-matrix to u/dimpase/lll-transformation-matrix
  • Commit changed from b02a25ac9aec3244264c10f5f2755ed3adba4c61 to 098245f11b01ec3f12777112c34f7407dc7f5452
  • Reviewers set to Dima Pasechnik

New commits:

8c6d598add a transformation option to LLL()
e29bb22transformation matrices for NTL's LLLs
098245faddressed reviewer remarks

comment:9 Changed 18 months ago by dimpase

  • Status changed from needs_review to positive_review

lgtm

comment:10 in reply to: ↑ 7 Changed 18 months ago by malb

Replying to chapoton:

  • why the changes in nlt_mat_ZZ ?

IIRC the datatype wasn't right before.

comment:11 Changed 18 months ago by vbraun

  • Branch changed from u/dimpase/lll-transformation-matrix to 098245f11b01ec3f12777112c34f7407dc7f5452
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.