It's about QuadraticForm(...).short_vector_list_up_to_length(l), which finds all vectors of length less than l. As opposed to fpLLL, which approximates a basis of short vectors. The same guy who wrote fpLLL implemented enumeration of short vectors in Magama. And clearly, I can't possibly beat that implementation.
Martin Am Dienstag, 28. Januar 2014 19:45:43 UTC+1 schrieb Thierry (sage-googlesucks@xxx): > > Hi, > > On Tue, Jan 28, 2014 at 07:04:10AM -0800, Martin Raum wrote: > > Hi all: > > > > You might or might not know that the current implementation of short > > vectors for quadratic forms (aka lattices) is, say, unreliable. We are > > using PARI, which, as I was informed, never focused on anything like > this. > > Also, the current implementation is quite slow; unbearably slow by my > means. > > Which part of Sage code is it about ? To find short vectors of integer > lattices, Sage uses fpLLL by default, which is assumed to be both fast > and reliable: > > sage: M = random_matrix(ZZ, 100) > sage: %time M.LLL().column(0) > CPU times: user 0.78 s, sys: 0.00 s, total: 0.78 s > Wall time: 0.79 s > (0, 1, -1, 5, -1, -1, 6, -1, 4, 0, 0, -1, -6, -2, -2, 1, 3, -4, -7, 10, > 3, -3, 2, 1, -3, -3, -2, 1, 1, 0, 2, 5, -1, -1, 1, 0, 1, 1, 6, 11, -5, > -2, 4, -2, 1, 8, 5, 0, -4, 3, -1, -8, -7, 4, -1, 3, -10, 1, 1, -4, -7, > 2, -9, -1, -13, 22, -6, 17, -5, -6, -6, 22, 6, -13, 8, 17, 10, 4, 10, > -11, -7, 44, 7, 9, -19, -33, -15, 1, 45, -48, 23, 0, 13, 14, 80, 20, > -246, -63, -233, -95010) > > Ciao, > Thierry > > > > I have an implementation using interval arithmetic which is not quite as > > fast as Magma, but performes quite nicely. The implementation is in C++. > I > > originally wrote a Cython wrapper, it seems really hard to maintain, > mostly > > because several freatures of C++ are not easily wrapped of Cython. So I > > have used boost::python, which even resulted in better performance. > > > > So, how likely is it that we will have a boost python as a standard > > library? We already have headers, and the python part of boost is not > even > > too big (126 kb on my system). It would provide us with an alternative > way > > to wrap C++ code, which I personally am desperate for. > > > > In any event, I can prove the C++ code and my Cython wrapper, but I > > wouldn't want to support this for the next years. > > > > Best, Martin > > > > -- > > You received this message because you are subscribed to the Google > Groups "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to sage-devel+...@googlegroups.com <javascript:>. > > To post to this group, send email to > > sage-...@googlegroups.com<javascript:>. > > > Visit this group at http://groups.google.com/group/sage-devel. > > For more options, visit https://groups.google.com/groups/opt_out. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/groups/opt_out.
