Date: Mon, 19 Feb 96 13:06:49 CST From: rusin (Dave Rusin) To: fateman@CS.Berkeley.EDU Subject: Re: Questions on CAS comparisons >Of course it depends on what you are doing, but people who are >(for example) finding zeros of polynomial systems using GB >get very tired of waiting. If they were to use resultants, >or (much faster) numerical routines, they could get much >further. Wow -- resultants offered as the practical alternative -- I guess GB must hide worse bugaboos than I thought. >While specific "easy" cases can sometimes be solved >(e.g. factorable systems), as a general method, GB takes >super-exponential time, and its results (very large) are >of very little use. I am aware that the size of a GB can be exponential in the size of the original basis, and that the degrees of the generators can be larger (only up to the square of the original degrees, I thought). I take it there are even more extreme examples then? >I would be interested in hearing what your experience has >been, thoguh. Well, I had to do some group-cohomology (spectral sequence) calculations which amounted to deciding whether or not an element in a ring Z/2[x1, ..., xn] lay in an a homogeneous ideal I=(p1, ..., pm). Here n ran up to about 5 or 10, m was a little larger, and the degrees of the p's ran up to about 16. I had tried doing it by hand, not having ever heard of Groebner bases or even a reasonable division algorithm, and I found myself running in circles (deducing by dint of great strength that p = Sum(a_i p_i) + a_0 for some polynomials a_i and then noticing that a_0 = p !). Moreover, I have had algebraic varieties given parametrically which I wanted to describe implicitly (e.g. x=t^2, y=t^3 --> y^2=x^3). For varieties which are complete intersections this is no big deal in general, but otherwise (i.e. if more equations are needed to correctly pin down the variety than the simpleminded dimension count would predict) I found that hand calculations tended to miss some defining relations. If there are better ways to decide ideal membership, or to eliminate variables correctly, I'd like to know about them. Incidentally, I absolutely agree that solving systems of equations numerically is much faster if that's the kind of answer you need. Care must be taken of course but numerical answers come so fast you can afford to be sloppy first and ask questions afterwards. dave PS - I am currently engaged in a faculty seminar on Groebner Bases. If there is a damning critical account of GB techniques in the literature I'd like to take a look at it. ============================================================================== Date: Mon, 19 Feb 1996 12:40:48 -0800 From: "Richard J. Fateman" To: rusin@math.niu.edu Subject: Re: Questions on CAS comparisons From rusin@math.niu.edu Mon Feb 19 11:08:45 1996 >Of course it depends on what you are doing, but people who are >(for example) finding zeros of polynomial systems using GB >get very tired of waiting. If they were to use resultants, >or (much faster) numerical routines, they could get much >further. Wow -- resultants offered as the practical alternative -- I guess GB must hide worse bugaboos than I thought. My colleague John Canny (jfc@cs.berkeley.edu) and some of his students have made great press about using resultants -- where the resultants can be precomputed to solve certain problems in motion planning-- so that "real-time" calculuations can be done by robots. The computations that took minutes by GB can be done in milliseconds. This is not a general solution, but then the problem was not a general problem. >While specific "easy" cases can sometimes be solved >(e.g. factorable systems), as a general method, GB takes >super-exponential time, and its results (very large) are >of very little use. I am aware that the size of a GB can be exponential in the size of the original basis, and that the degrees of the generators can be larger (only up to the square of the original degrees, I thought). I have not studied this, but I believe the coefficients in the generators can grow much faster. An answer with 3,000 digit coefficients can be disappointing. I take it there are even more extreme examples then? >I would be interested in hearing what your experience has >been, thoguh. Well, I had to do some group-cohomology (spectral sequence) calculations which amounted to deciding whether or not an element in a ring Z/2[x1, ..., xn] lay in an a homogeneous ideal I=(p1, ..., pm). Here n ran up to about 5 or 10, m was a little larger, and the degrees of the p's ran up to about 16. I had tried doing it by hand, not having ever heard of Groebner bases or even a reasonable division algorithm, and I found myself running in circles (deducing by dint of great strength that p = Sum(a_i p_i) + a_0 for some polynomials a_i and then noticing that a_0 = p !). If you did the calculations with the aid of computer algebra system but not GB, would you have made mistakes? Would you have gotten the answer faster? Moreover, I have had algebraic varieties given parametrically which I wanted to describe implicitly (e.g. x=t^2, y=t^3 --> y^2=x^3). For varieties which are complete intersections this is no big deal in general, but otherwise (i.e. if more equations are needed to correctly pin down the variety than the simpleminded dimension count would predict) I found that hand calculations tended to miss some defining relations. If there are better ways to decide ideal membership, or to eliminate variables correctly, I'd like to know about them. Incidentally, I absolutely agree that solving systems of equations numerically is much faster if that's the kind of answer you need. Care must be taken of course but numerical answers come so fast you can afford to be sloppy first and ask questions afterwards. Yes. dave PS - I am currently engaged in a faculty seminar on Groebner Bases. If there is a damning critical account of GB techniques in the literature I'd like to take a look at it. You might look at papers by Canny and Manocha (he is at Duke or North Carolina State, a former student of Canny's). Canny may have a link to it from http://http.cs.berkeley.edu/~jfc  RJF ============================================================================== To: rusin@math.niu.edu Subject: Re: Seeking condemnation of Groebner Bases Date: Mon, 19 Feb 1996 21:46:56 -0500 From: Dinesh Manocha In message <9602192100.AA04520@clinch.math.niu.edu>, rusin@math.niu.edu writes: >I recently had an email exchange with Richard Fateman concerning the >efficiency and applicability of Groebner Bases. While we were in >agreement about the kinds of occasions under which their use was >or was not appropriate, I was surprised when he mentioned that you >and John Canny had found resultants to be more effective than GB >in some situations. > >Since I am currently involved in a faculty seminar on Groebner Bases, >I am curious about your experience in this direction. I had always >considered resultants to be a clear example of a wonder theory which >became a computational nightmare, and by comparison found Groebner bases >to be a workable practical alternative for elimination theory. Can >you describe what experiences swung the situation the other for you? >Can you recommend some literature? > >Thanks >dave Our experiences are totally. We view Groebner basis as a nice mathematical tool but a computational nightmare. We have extensively used resultants for a number of elimination problems, computing numerical approximation to roots and geometric problems. They work very well in practice (in terms of speed and accuracy). As for references, you can refer to some of our work. We have also tried out a number of Groebner basis implemenations (those available in Maple, Mathematica, Macaulay) and found that resultants were about two orders of magnitude faster (for the examples we tried). Most of the papers are available on WWW pages. They are: http://www.cs.unc.edu/~manocha/resultants.html (Papers on symbolic elimination) http://www.cs.unc.edu/~manocha/equations.html (Papers on numerical approximation to zero and one dimensional algebraic sets) http://www.cs.unc.edu/~manocha/kinematics.html (Applications to robot kinematics problems: in particular used for real-time algorithms) http://www.cs.unc.edu/~geom/intersect.html (Applications to intersection problems) Let us know if you have any problems accessing these papers. There is work of many other authors in this area. Check out papers by Saxena and Kapur in ISSAC'95, Ph.D. thesis of I. Emiris (at UC Berkeley) etc. We will be very interested in your experiences. best, Dinesh ============================================================================== From: "H.-G. Gr\"abe" Newsgroups: sci.math.symbolic Subject: Re: Questions on CAS comparisons Date: Wed, 21 Feb 1996 10:04:27 +0100 Richard J. Fateman wrote: > > In article <31287189.5D0B@informatik.un-leipzig.de>, > H.-G. Gr\"abe wrote: > > >...There are several comparisons of parts of the > >mathematical engines themselves in the literature, among them my > >comparison of the Groebner factorizer as the essential part of the > >solver in my paper ``On Factorized Groebner Bases'', (see > >http://www.informatik.uni-leipzig.de/~compalg/ca-fg.html#publikationen). > >I think, it's worth to have somewhere such comparisons collected. > > While this is a worthwhile point of comparision, it is, I think, hardly > as significant for most "users" as a system-wide feature comparison. > ... > So I think it is worthwhile to have both "engine" comparisons > and "system" comparisons. > That's true, but good comparative investigations also for other parts of the CAS engine are lacking as far as I know. But I would insist in comparisons beyond run time, since for the casual user it's more dangerous to have *false* answers from the inner part of the engine than from the outer part as in most items of Wester's list. In this context I don't agree with RJF's point of view on GB: It's the heart of the symbolic equations solver in all CAS that I know to have a "solve" command, but output quality is quite different, see the paper cited above. I could imagine, that this also applies to factorization, gcd computation, more advanced mathematics as PDE'S etc. HGG