Roman, I thoroughly agree with you that the multipolygcd and factoring problem is not going to go away overnight. I'm sure by your comments that you can guess what we've been doing with FLINT for univariate gcd and how long even that is taking.
Also, I too get frustrated by some of the simple-minded comments that get made about this problem. I also get tired of posting about the information available about what Magma does for GCD and factoring and about the various papers available on this subject. But, this is partly my own fault, since Mike Hanson set up a webpage to blog everything we know about the subject in order to come up with a strategy for dealing with this problem, and I've been too lazy (or busy) to put my notes on there. But let me say from off-list discussions with Joel Mohler that I think he just might be going to prove us all wrong. There just might be a simple set of algorithms which give the answer almost all the time quickly (if you are comparing to Magma) for multipoly factoring. So I'm not ready to make a call on this one. I'm not saying I'm off to the local book maker to place money on Joel's approach, but simply that he's already proved me wrong on a number of points of "established wisdom" and his overall plan looks very promising. But having said that, there is no *single* algorithm which will always work quickly. There have also been some recent improvements in algorithms which will take much of the hard work out of this problem. This is an advantage that people in the past didn't have. It pains me to admit it, but possibly "doing things properly" by going through all the "really hard work" that people have done in the past, just may not be necessary any more. How sad, because I was looking forward to this challenge! But we'll see. Regarding probabilistic algorithms, we need to be careful to distinguish Las Vegas algorithms from Monte Carlo algorithms (you can check wikipedia for what I am taking as my definitions). Victor Shoup actually implements both in NTL, but one kind of probabilistic algorithm is perfectly fine for inclusion in SAGE so long as early bailout is implemented (something SINGULAR is guilty of not doing).The other kind of probabilistic algorithm is fine too, if proper checks of correctness are made and if there is a fallback to another algorithm if the checks fail. I essentially do this in FLINT for GCD at one point, due to a comment of Allan Steel on the Magma website and the result is something like a 100 times speedup in getting the correct answer. At one point, what I do in FLINT is asymptotically (and practically much) faster than what Pari does because of this simple observation. By the way, it turns out that a single algorithm is sufficient to beat Magma at univariate GCD over ZZ. But at the very least one can actually be asymptotically faster (in increasing size of coefficients), so why stop there! Let's plan to eventually look well past Magma. Bill. On 1 Apr, 07:50, Roman Pearce <[EMAIL PROTECTED]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
