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] --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
