Opened 12 years ago
Closed 12 years ago
#1188 closed defect (fixed)
unexpected results after LLL?
Reported by: | malb | Owned by: | malb |
---|---|---|---|
Priority: | blocker | Milestone: | sage-2.8.13 |
Component: | linear algebra | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Consider this example from the Magma handbook:
# n integers which's GCD we are interested in sage: Q = [ 67015143, 248934363018, 109210, 25590011055, 74631449, 10230248, 709487, 68965012139, 972065, 864972271 ] sage: n = len(Q) sage: S = 100 sage: X = Matrix(IntegerRing(), n, n + 1) sage: for i in xrange(n): ... X[i,i + 1] = 1 sage: for i in xrange(n): ... X[i,0] = S*Q[i] sage: L = X.LLL() sage: show(L) sage: M = L[n-1].list()[1:] sage: add([Q[i]*M[i] for i in range(n)]) 864972271
which isn't quite right, we expect:
# n integers which's GCD we are interested in sage: Q = [ 67015143, 248934363018, 109210, 25590011055, 74631449, 10230248, 709487, 68965012139, 972065, 864972271 ] sage: n = len(Q) sage: S = 100 sage: X = Matrix(IntegerRing(), n, n + 1) sage: for i in xrange(n): ... X[i,i + 1] = 1 sage: for i in xrange(n): ... X[i,0] = S*Q[i] sage: L = X.LLL(algorithm='NTL:LLL') sage: show(L) sage: M = L[n-1].list()[1:] sage: add([Q[i]*M[i] for i in range(n)]) -1
Is this my lack of understanding of LLL reduction or is this a bug?
Attachments (3)
Change History (15)
comment:1 Changed 12 years ago by
comment:2 Changed 12 years ago by
My processor is a Core2Duo which I use in 64-bit mode (Debian/testing AMD64). I can also reproduce this bug on sage.math (64-bit Opteron). So I assume this is an issue with 64-bit architectures.
comment:3 Changed 12 years ago by
- Owner changed from was to malb
- Priority changed from major to blocker
- Status changed from new to assigned
I upgraded this bug to a blocker as it is a bug which leads to wrong results without raising an error.
comment:4 Changed 12 years ago by
One quick point is at least the result is still a basis for the correct lattice:
A = X.row_module() B = L.row_module() A == B /// True
so it's returning something that is a basis for the correct lattice. But maybe it's not LLL reduced.
We should write a function to determine whether or not a matrix is LLL reduced, i.e., use the LLL criterion, as described in Section 2.6 of Cohen's book.
If the output isn't LLL reduced, then there is definitely a bug.
Anyway, I am going to attempt to implement this criterion right now, and see what happens.
comment:5 Changed 12 years ago by
OK, I wrote a program to compute Gramm-schmidt form, in order to check the LLL criterion. I tried it on the above output L (I will post this elsewhere when I finish documenting it: http://trac.sagemath.org/sage_trac/ticket/1201). It is DEFINITELY THE CASE THAT NTL is getting things *wrong* here. When transforming the rows of L into orthogonal form using LLL a coefficient mu_ij of 68719476736.0213 appears, which is > 1/2, so the resulting matrix is not LLL reduced. This this is still thus a major blocker.
One "fix" would be to have it print a big warning no matter what on 64-bit, which would at least allow us to release. But this really needs to get fixed / understood.
comment:6 Changed 12 years ago by
Correction to the above comment: fpLLL gets things wrong, not NTL.
Currently Sage doesn't check the return value of the LLL() calls in fplll.pyx (zero = ok, non-zero = error). When adding that, it turns out that for this example fpLLL itself detects something is wrong.
comment:7 Changed 12 years ago by
In at least two places, fpLLL was assuming longs and ints were the same size. The patch I'm attaching should fix those. I already e-mailed Damien Stehle about this, too.
comment:8 Changed 12 years ago by
A new spkg is available at:
http://sage.math.washington.edu/home/malb/pkgs/libfplll-2.1.4-20071119.spkg
malb will add a doctest to verify this issue has really been fixed. Once that is merged we can hopefully close this ticket.
Cheers,
Michael
comment:9 Changed 12 years ago by
malb: The error codes from LLL() are positive when an error occurs. Attaching an updated (non-hg) patch that replaces the ret < 0 checks by ret != 0.
comment:10 Changed 12 years ago by
On IRC:
[11:46] <wjp> malb: I slightly updated your fplll patch replacing ret < 0 by ret != 0 since fpLLL returns positive values on error [11:46] <malb> I disagree [11:46] <malb> are you sure it has to be an error if !=0 ? [11:47] <malb> it just returns kappa, doesn't it? [11:47] <wjp> only in error case, as far as I can tell [11:47] <malb> the example will not work if you test for ret != 0 [11:47] <malb> i.e. the doctest I just added [11:48] <wjp> that's strange; I'll look through the fplll sources again then [11:48] <malb> also heuristic may return kappa != 0 because it is not guaranteed to be LLL reduced anyway [11:48] <malb> I only superficially scanned the source though [11:48] <wjp> hm, so it might not be usable as an error code [11:49] <malb> yes, but I am not sure, we could ask Damien?
comment:11 Changed 12 years ago by
#1188 looks good -- make sure to only apply fplll2.patch instead of fplll.patch.
And wow or wow wjp did a great job on that one in multiple ways!
comment:12 Changed 12 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
Merged in 2.8.13.rc1. - see #1217 for followup.
I would like to close this ticket. I did apply the doctest.patch and updated to the latest upstream libfplll.spkg that malb provided.
I get -1 with both X.LLL() and X.LLL(algorithm='NTL:LLL') on a Pentium M with sage-2.8.12. Maybe a processor-specific problem?