On Mon, Mar 31, 2008 at 6:48 PM, Roman Pearce <[EMAIL PROTECTED]> wrote: > > > The important thing isn't what algorithm is implemented, but that the > > result is fast(er than Magma). > > The important thing is whether users can hope to get an answer at all. > The old Singular factoring code was hopeless and I bet multivariate > gcd > is still hopeless. And what about correct ? The new code you linked > to looks like a probabilistic algorithm.
Just because an algorithm is probabilistic doesn't mean it necessarily gives wrong answers. By the way, see http://www-fourier.ujf-grenoble.fr/~parisse/publi/gcdheu.pdf which is I think a paper that proves correctness of the algorithm we're talking about. (I've not carefully read the above short paper, so I'm not vouching for it though.) > There's no point in being > fast if you're wrong, and developing good routines will take months. In some cases being fast but possibly wrong is very useful. I think this is not the situation here for mpoly gcd. It is the case for many interesting computations with algebraic number fields, and people just have to live with it. By the way, for factoring and gcd there are double checks. > I simply wanted to point out the existence of what appears to be > correct routines, even if they are slow. I do greatly appreciate that, and I think I misunderstood your comment to suggest that we should forget about implementing our own code and just use Maxima and be done with it. I apologize. I was responding off list to a lot of "use lisp/Maxima or else" emails from somebody, and was perhaps short tempered as a result. Hopefully you understand. > Also, to Joel Mohler: > 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 > > What you are trying to do is not a "weeks long" project, it is one > of the central achievements of the entire field. It took a > decade > to do the first time, so don't expect to have "industrial strength" > routines soon. It will realistically take months of full time work. > 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"? Does *any* program doing multivariate polynomial gcd and factorization well except Magma? I'm not being rhetorical -- I just don't know the answer. If only Magma does well, we should just find out what algorithms they use, and if they aren't just copying from the above book, then we *need* to be more clever than whatever is in that book. Allan Steel did it -- by himself -- and so can we. 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. Maybe we can appeal to his vanity and ask him. > The people on this list seem to hilariously underestimate the depth > of this problem, and that concerns me. I want Sage to succeed, and > you can't with that attitude. This is a massive undertaking, and > if you treat it like it's not it is ultimately very discouraging. > > I'd spell it all out: the things you need to do, the problems and > subproblems, but it's easier and better if you just read the book. I'm curious -- have you actually implemented multivariate gcd and/or multivariate factorization? You talk as if you have. -- William --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
