Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#1279 closed defect (fixed)

[with spkg, with positive review] LLL on "tall" matrices immediately crashes sage

Reported by: was Owned by: malb
Priority: major Milestone: sage-2.8.15
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

If you create an n x m matrix over ZZ in sage with n > m, then
run the LLL algorithm on it (fplll), Sage completely terminates.

sage: A = random_matrix(ZZ, 15, 10)
sage: A.LLL()
Ill-formed matrix  : d>n
bsd:~ was$ 

Possible Solutions:

  1. trap bad conditions somewhere and raise an exception.
  1. Just immediately give an error in the A.LLL function if A is nonsquare (instead of letting fplll do this


  1. Put an error in the fplll wrapper code in libs/fplll

Attachments (1)

trac_1279.patch (1.2 KB) - added by malb 7 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 7 years ago by malb

  • Owner changed from was to malb
  • Status changed from new to assigned

comment:2 Changed 7 years ago by malb

A new spkg is available at which replaces the exit(1) call with an abort() call which we can and do trap.

http://sage.math.washington.edu/home/malb/pkgs/libfplll-2.1.4-20071127.spkg

Still, we should check for nr>nc ourselves to present a more userfriendly exception rather than a RuntimeError?

Changed 7 years ago by malb

comment:3 Changed 7 years ago by was

  • Summary changed from LLL on "tall" matrices immediately crashes sage to [with refereed patch] LLL on "tall" matrices immediately crashes sage

Looks good ready to include.

comment:4 Changed 7 years ago by malb

  • Summary changed from [with refereed patch] LLL on "tall" matrices immediately crashes sage to [don't apply this patch] LLL on "tall" matrices immediately crashes sage

Do not apply this patch as is:

Damien Stehle wrote via e-mail:

I did not apply your patch for d>n, which is not invalid
(though it was said to be in proved.cpp). If there are linear
dependencies, LLL will just find them and output zero vectors before a
LLL-reduced basis of the input lattice.

the new fplll is available at

http://sage.math.washington.edu/home/malb/pkgs/fplll-2.1.5.tgz

comment:5 Changed 7 years ago by malb

Damien replaced all exit calls with quit calls. However, neither I nor man knows about any quit system call and thus 2.1.5 doesn't build at least on my machine.

comment:6 Changed 7 years ago by malb

  • Summary changed from [don't apply this patch] LLL on "tall" matrices immediately crashes sage to [with spkg] LLL on "tall" matrices immediately crashes sage

A new spkg is available at

http://sage.math.washington.edu/home/malb/pkgs/libfplll-2.1.6-20071129.spkg

which fixes this issue for me. Don't forget to touch fplll.pyx and sage -b after installing that package.

comment:7 Changed 7 years ago by cwitty

  • Summary changed from [with spkg] LLL on "tall" matrices immediately crashes sage to [with spkg, with positive review] LLL on "tall" matrices immediately crashes sage

I installed the new spkg (on 32-bit x86 Linux). The test in the bug report no longer crashes, and doctests in fplll.pyx and matrix_integer_dense.pyx still pass.

I did not apply the attached patch, and I don't think we should apply it... as Damien points out, that case is not actually invalid.

In short, the spkg looks good to me.

comment:8 Changed 7 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from assigned to closed

Merged in 2.8.15.alpha1.

comment:9 Changed 7 years ago by mabshoff

To make it crystal clear: The spkg was merged, the patch was backed out after Carl reminded me :)

Michael

Note: See TracTickets for help on using tickets.