Hi all, Since there has been a little bit of speculation and discussion about incorporating FLINT into SAGE, let me give a (rather long) account of where things are, at present, from *my* perspective.
For those who don't know, FLINT is an extremely fast C library for doing *core* arithmetic. It's largely built on GMP (though for some functions we couldn't resist rolling our own). It will eventually be a complete number theory library (Fast Library for Number Theory) somewhat akin to NTL, but for now it basically has polynomial arithmetic, integer factorisation and fast integer multiplication algorithms and that's all!! But don't let appearances deceive. FLINT is already tens of thousands of lines of code, uncompromisingly fast and consists of many, many functions in numerous modules and includes a vast infrastructure including memory management, testing, profiling and graphing code, some automatic tuning code and example programs, documentation, a myriad of different algorithms and functions and hundreds of hours of research and innovation (all hopelessly incomplete of course). We'll be at SAGE days 5, and I really hope to have the opportunity to discuss integer and polynomial arithmetic and basic number field arithmetic with other SAGE developers, since this is what we can really make an impact on for now. As many people know, we are writing FLINT especially for SAGE, but both David Harvey and I are anal retentive Australians who care so much about performance that we often forget that there is a real world happening out there. I sometimes slip sideways around corners to save footsteps and I dream in vivid colour pixels of making FLINT functions 1% faster (when I actually get around to sleeping). But seriously, pin us down, help us figure out what the interface between SAGE and FLINT should look like and hopefully we can get this beast into SAGE sooner rather than later. Now for the gruesome details: At present, polynomials are only implemented over ZZ in FLINT. But the intention is to implement pseudo division very shortly, which will give ZZ with a denominator for various things if desired. Pseudo division is almost a cut and paste job I believe. It should be about a weekend's work. I should have done it ages ago, but other things have intervened. I have one more *small* project to complete before I implement pseudo division though (a slight additional speedup of polynomial division). It's not essential, but I need it for other reasons, probably related to deep seated feelings of self worth. :-) I have given some thought to how we will make a QQ[x] functionality over the top of ZZ[x], but I haven't discussed that with David Harvey yet. However, this actually won't affect FLINT for quite some time, since at the polynomial level, only pseudo division needs to be implemented for now. However this is something people might have opinions on. Please share them. Some details to consider with FLINT: 1) By SAGE days 5 I hope to at least let people know what the basic interface for ZZ[x] will be. I've discussed this with William Stein and you can expect some kind of "announcement" of this, even if just on this list. There will be two FLINT polynomial modules, but for now only one will be ready. However both modules cover essentially the same things. It sounds complicated, but it is actually worse than you can possibly imagine. 2) I'm hopeful that by SAGE days 6 we'll have one of our two polynomial modules implemented which will include addition, subtraction, multiplication, division and remainder, scalar multiplication, scalar division, pseudo division, content and polynomial exponentiation, fast integer multiplication and all the other usual bits and bobs for converting and managing polynomials. Obviously we are quite close to most of this or I wouldn't be saying anything about it right now. As an added bonus, we might throw in very rough evaluation, derivative and composition functions (naive algorithms only). Then again we might not have enough time, (but technically none of these is a challenge if you have all the above). I also hope to have a new version of my quadratic sieve fully coded by SAGE days 5 or 6 (it is very close to being done right now - it's working, but needs a small amount of tidying up). 3) But, we've hit a major snag: the best algorithms for polynomial gcd (the most important polynomial operation, fullstop) require polynomial arithmetic over Z/pZ and complex root finding. Whilst we have some code for the latter which is quite well done, it was not written specifically for the FLINT project and will need considerable reworking. Some work has been done on a Z/pZ module, but it is hopelessly incomplete. 4) FLINT is some way from having polynomial factorisation or efficient irreducibility tests, efficient root finding and numerous other higher level algorithms that we haven't even thought about yet. Please let us know what your favourite polynomial algorithm is that you'd like to see in FLINT. It might inspire us. We have nothing that would be useful to singularity theory or Groebner bases. But we absolutely want to leave that stuff up to the SINGULAR people!! That hardly goes without saying, but just in case people had the wrong idea.... 5) We only have polynomials over ZZ and no other rings or fields at present (obviously there are plans for much more, and many bits and pieces of code have already been written and/or planned for future modules). Polynomials are univariate only and probably always will be. Our data types are not recursive. Each new type in FLINT will get its own super efficient implementation. This is why everything is done in C. Performance is everything!! 6) We have a lot of testing and documentation to do, though both David and I have begun documentation projects for the respective modules we have been nursing and the current test code is already quite extensive. 7) David is not actively working on FLINT for the next month or two or three due to thesis, etc. I am applying for jobs and grants, but probably still have enough time to complete 2 especially since I also have a student (David Howden) who is theoretically being paid to help me. I've had two other students (Tomasz Lechowski and Daniel Scott) who have just completed projects, and they did some excellent work for us. 8) Tuning for different platforms is not part of our short term plans, though if someone wanted to work on this it is straightforward enough. We also have a profiling platform all set up for FLINT. It will produce lots of pretty graphs if you know how to drive it. One of my students has expanded our profiling code to include some NTL and Pari functions and we already have code for profiling some Magma functions and of course many FLINT functions. We still lack LiDIA profiling code, though LiDIA doesn't implement asymptotically fast polynomial arithmetic over ZZ and it's all C++, so there will be no surprises there. As many of you know we have the utterly diabolical aim of thrashing every other package out there by a big margin and producing the evidence to prove it! David Harvey sometimes forgets that we aren't trying to beat FLINT (because that's the one we are writing), but a few hours of electric shock therapy usually sorts this out. Then again, I do the same thing myself from time to time. 9) FLINT 1.0 will (hopefully) be reentrant (modulo making the memory manager threadsafe). FLINT 1.0 will have no parallel algorithms implemented. These will come later. It is good to beat everyone else without them, then it will be awesome when we do have them! 10) FLINT has received extensive testing in the field by in excess of 2 people, including David and I. In something like 30,000+ lines of code we hope there will be less than zero serious bugs and corner cases and we anticipate the initial mean time between failure to be well in excess of 18446744073709551615 seconds! 11) All FLINT function names have Australian spelling. We found very early on that these perform much faster than functions with American spellings. All told, the major shortcoming in the short term is actually the lack of poly gcd. That is my fault. In my quest to become the most powerful Jedi ever, I forgot that algorithms for Z[x] need to control coefficient explosion, and I have so far failed to convince the Knuth- Lehmer-Schoenhage method to do this. I calculate a less than 1% chance of succeeding in this. The upshot is that we are going to have to make our first FLINT release without fast poly gcd. To do gcd properly we need polynomials over Z/pZ and complex root finding. Neither is slated to appear in FLINT 1.0. That's a major nuisance. However, an awful lot can be done both for plain polynomial arithmetic and for basic number field arithmetic in SAGE without gcd. In actual fact, it should be possible for us to write efficient conversion routines in C for going from a FLINT polynomial object to an NTL polynomial object and vice versa (at the very least), so a partial transition to NTL is both possible and definitely advisable if SAGE is to safely transition to FLINT. Technically, a handful of indispensible high level NTL polynomial functions could be encapsulated in a FLINT interface and we could replace these NTL functions one by one as we find the time to develop them. That would enable SAGE to use FLINT without worrying about NTL at all for ZZ[x] arithmetic. If that would be useful, let me know and I'll make sure that happens. It's not much work if the number of functions is small. But this all being said, we have to get, as a minimum, the essentials listed in 2 above, and appropriate testing done for the code we've written. It is critical to the performance, cohesion and credibility of FLINT that all of those things are complete, before we make a release. So that's our priority for now. Feel free to fire questions at us on list and obviously come and sit down and talk to us at SAGE days 5 and 6. Bill. --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
