Hi all, My name is Andy Novocin and I was a student of Mark van Hoeij's, and now I'm a post-doc at LIRMM in Montpellier, France.
I'm interested in polynomial factoring over the rationals in one variable. I've also recently become a SAGE-user and I'll be attending SAGE Days 10. I decided I would begin trying to implement some of my ideas for polynomial factoring in SAGE/C++ to help SAGE consistently beat MAGMA. The very first step I took was taking NTL's factoring code, adding about 6-8 lines of code which use fpLLL before using NTL's LLL. This made NTL's factoring code significantly faster, and on many cases (reducible polynomials) already beats MAGMA! It's a fairly simple hack of the NTL code, I simply take the lattice NTL would like to reduce, pass it to fplll then pass it back to NTL. Then when NTL calls its own LLL it will also find an already reduced basis but still compute whatever extra information it needs and it probably won't need to make many switches at all (if any). fpLLL is already included in SAGE, as is NTL I just want to use them together since NTL does some nice book keeping. I will be programming my own algorithm (probably using FLINT) in the coming year which should use all of the speed-ups I can think of, but for now we can already beat MAGMA (in lots of cases but not yet all) with just a few lines of hacking. Ok here are some tests I ran: For each test I took a polynomial which ought to break van Hoeij style algorithms by having a Galois group with elements mostly of order 2. I then factored this polynomial through SAGE using, my PATCH for NTL, then MAGMA, then PARI, then NTL. I have discovered that NTL has time savers for non-irreducible polynomials, specifically the case when there are many small factors. Whereas MAGMA is best when the polynomial is irreducible. For polynomials below a certain threshold they are all very fast. Here are the timings in seconds: Degree 128 irreducible : with PATCH 3.5s, with MAGMA 3.0s, with PARI 2.6s, with NTL 7.0s Degree 191 factors of degrees 128,32,16,8,4,2,1: with PATCH 12.6s, with MAGMA 17.0s, with PARI 16.8s, with NTL 64.6s Degree 192 factors of degrees 128,64: with PATCH 15.0s, with MAGMA 22.5s, with PARI 23.3s, with NTL 78.5s Degree 256 irreducible: with PATCH 78.9s, with MAGMA 63.1s, with PARI 130.5s, with NTL 594.3s Degree 288 factors of degrees 256, 32: with PATCH 131.3s, with MAGMA 197.0s, with PARI 355.8s, with NTL 970.5s Degree 300 factors of degrees 256,32,8,4: with PATCH 147.1s, with MAGMA 248.2s, with PARI 360.9s, with NTL 1103.3s Degree 511 factors of degrees 256,128,64,32,16,8,4,2,1: with PATCH 6761.4s, with MAGMA 24568.1s, with PARI 24123.9s, with NTL 21576.4s Currently SAGE uses pari for polynomials between degree 30 and degree 300. How to people feel about using this hack with the NTL that ships with SAGE? I think it's interesting for two piece of SAGE not to be able to use each other in this way. Maybe we should ask Victor Shoup if he minds... I'm new to this side of computer science. Thank you all for your time, see you at SD10, -Andy Novocin --~--~---------~--~----~------------~-------~--~----~ 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://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
