On Mar 31, 10:55 pm, "William Stein" <[EMAIL PROTECTED]> wrote: > On Mon, Mar 31, 2008 at 6:48 PM, Roman Pearce <[EMAIL PROTECTED]> wrote: > > > You need "Algorithms for Computer Algebra" by Geddes, Czapor, and > > Labahn: > > Chapter 5: Chinese Remainder Theorem > > Chapter 6: Newton's Iteration and Hensel Lifting > > Chapter 7: Polynomial GCD > > Chapter 8: Polynomial Factorization ... > > There's about 100 pages of material in that book, when you take out > > the exercises, etc. You need it all.
> We'll see. By the way, who "did it"? For Maple, I believe Michael Monagan and Laurent Bernadin wrote a lot of the main routines in use today. But many other people have contributed over a long period of time. A lot of old code has been replaced, and the full list of contributors would have at least 20 people on it. > Does *any* program doing > multivariate polynomial gcd and factorization well except Magma? Yes, Maple and Mathematica. It's not just factoring over Z either. You will eventually want to factor over algebraic number fields and function fields. Factoring and GCDs are a huge problem and getting them implemented is a significant accomplishment. You will also need resultants, probably. > By the way, the book you suggest above was published in 1992. > Allan Steel implemented all the fast gcd/factoring code in Magma > many years later. It's perhaps highly likely he made great progress over > what's in that book. The book describes the basic core approach which everyone needs to understand. People like Allan Steel work on these algorithms over and over and develop deep insight into them. That's how you make fundamental improvements. Often an improvement will be something simple, but thinking of it and understanding why it works is the product of a massive amount of experience and expertise. People can't just go and get that out of a book. You have to be fully immersed in the problem to understand what is going on. I am not an expert in this area, but if I had to write this thing I would start with that book. You can work through all the algorithms carefully. A careful choice of data structures and pre-existing routines would produce a first version that "works". It wouldn't be great, but it would get Sage out of a rut. Then you go back and try again, with better data structures and better routines and a little more insight. By the third version or so, you can make fundamental improvements. There are many, many things you can do. It's a whole area of computer algebra. The best strategy is to find a student who is interested in factorization. Sage has some nice libraries (fast GMP, FLINT) and a nice programming language that can be compiled. So there is the potential here to write fast code. But getting the algorithms right is a big commitment, say 1-2 months for a first version (using pre-existing routines) and 2-4 months for each version after that (when you're rewriting things from scratch). It could be longer, depending on how it goes. > I'm curious -- have you actually implemented multivariate gcd and/or > multivariate factorization? During (most of) a course in computer algebra, I implemented the algorithms on top of Maple. Of course my code was garbage, but I worked through the algorithms and got an appreciation for them. It's not a giant impossible task (unless you insist on beating Magma), but it can't be done "part-time" either. And you have to start by saying "our code might be slower on a lot of examples, but we're going to use the right algorithms." That's a difficult pill to swallow. One big leg up is that Sage already has good univariate factorization mod p and over GF(p^q). I suspect that in terms of code, there is not really that much to write, but acquiring the necessary experience will take time and a lot of effort. One final piece of advice - you can't win by copying your competitors. So forget about what Magma does for now. Magma may be the fastest system out there, but I doubt it's the fastest system *possible*. Allan Steel surely knows "there's no such thing as the fastest code". This is really true. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
