#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:
- trap bad conditions somewhere and raise an exception.
- Just immediately give an error in the A.LLL function if A is nonsquare (instead of letting fplll do this
- Put an error in the fplll wrapper code in libs/fplll
Attachments (1)
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
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
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?