Implementing LLL well is a black art. I don't know enough to know why the Magma one is so much better, but at least part of the reason may be that the experts in LLL are using Magma for their development work. Hence, once everyone in te world uses Sage, ...
Thanks for wrapping NTL's LLL. But NTL only has integer LLL, where the input is a basis for the lattice in Z^n, while for some applications it is also useful to have a version which takes as input the Gram matrix over R (i.e. any positive definite symmetric real matrix). For example that is what is useful for reducing bases of elliptic curves. Pari has that but NTL does not. John On 9/21/07, Martin Albrecht <[EMAIL PROTECTED]> wrote: > > Hi everyone, > > SAGE 2.8.5 finally adds a method for LLL lattice reduction to the > Matrix_integer_dense class. For now it only wraps NTL but we actually have > two more implementations available in SAGE which are to be wrapped > conveniently soon. However, as ticket > > http://trac.sagemath.org/sage_trac/ticket/723 > > points out, they are all blown away by MAGMA. > > sage: a = random_matrix(ZZ,200) > sage: time b=a.lll() # NTL, delta = 3/4 > CPU times: user 10.63 s, sys: 0.03 s, total: 10.66 s > Wall time: 10.67 > > sage: m = magma(a) > sage: time b = m.LLL() # MAGMA, delta = 3/4 > CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s > Wall time: 1.72 > > sage: p = pari(a) > sage: time b = p.qflll(1) # Pari > CPU times: user 10.47 s, sys: 0.03 s, total: 10.51 s > Wall time: 10.61 > > sage: g = gap(a) > sage: time b = g.LLLReducedBasis() # GAP > killed after two minutes > > The relevant MAGMA documentation is at > > http://www.msri.org/about/computing/docs/magma/html/text833.htm > > The relevant PARI documentation is at > > http://pari.math.u-bordeaux.fr/dochtml/html.stable/Vectors,_matrices,_linear_algebra_and_sets.html#qflll > > The relevant NTL documentation is at: > > http://www.shoup.net/ntl/doc/LLL.txt > > Also, Google came up with > > http://www.math.uu.nl/people/vdkallen/lllimplementations.html > > which could be relevant or not, I don't know. > > The point of this mail is to ask you -- dear LLL wizards -- (a) why Magma is > so much faster and (b) what we can do about it. > > Thoughts? > Martin > > -- > 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] > > > > > -- John Cremona --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
