> (first) try the FP variants of NTL's LLL first (I overlooked those before) > (then) try Damien's fast.c implementation, also the proved version seems > interesting, given the discussions on this list.
So, after I understood a bit better what makes LLL algorithms fast, here is what I came up with so far. I wrapped the approximate LLL versions of NTL. Joel, thank you 1000 times for making it possible to strip one layer for the NTL interface because I wrote 18 Pyrex interfaces (for 9 overloaded C++ functions) for NTL's LLL alone. And I didn't cover everything! From what I read MAGMA also uses approximate variants (overall they have 8 LLL implementations according to the manual), but they can do so because they can prove that the result is LLL reduced. That should translate to Damien's provable GPL implementation. However, I am not entirely sure what the result from the floating point variants in NTL is. Shoup writes: "Routines are provided for lattice basis reduction, including both exact-aritmetic variants (slow but sure) and floating-point variants (fast but only approximate)." What I do not understand is, if a not LLL reduced basis can be returned by the FP variants without that an exception is raised. I would appreciate input from somebody more experienced here. As an example consider the example from the MAGMA documentation: sage: B = MatrixSpace(IntegerRing(), 50, 51)(0 sage: for i in range(50): B[i,0] = ZZ.random_element(2**10000) sage: for i in range(50): B[i,i+1] = 1; Trying the fastest one: sage: B.LLL(algorithm="NTL:LLL_FP") LLL_FP: numbers too big...use LLL_XD ... <type 'exceptions.RuntimeError'> We try what NTL suggested: sage: time B.LLL(algorithm="NTL:LLL_XD") 50 x 51 dense matrix over Integer Ring CPU time: 43.55 s, Wall time: 44.73 s So, can we be sure now that this is correct? MAGMA's time: sage: M = magma(B) sage: time C = M.LLL() Wall: 15.53 s Also, MAGMA seems to use an heuristic to choose which LLL implementation out of eight is the best (and they say it is not very good) so I wonder if we should also make a choice if algorithm==None (defaults to exact version for now). So NTL is still behind but not as bad as before. I assume qflllgram() for John is next on the LLL List and then I'l have to look into Damien's GPL code. Martin PS: #723 updated. -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
