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