🚀 go-pugleaf

In article <15639@dime.cs.umass.edu> yodaiken@freal.cs.umass.edu (victor yodaiken) writes:
>In article <10838@medusa.cs.purdue.edu> gb@cs.purdue.edu (Gerald Baumgartner) writes:
>>This Groebner basis algorithm has a similar structure as the
>>Knuth-Bendix algorithm (Knuth-Bendix can be simulated by Groebner
>>basis algorithm, probably vice versa). The Groebner basis algorithm
>>runs in doubly exponential time (double exp. in the degree of the
>>polynomials and exponential in the number of polys or so) and still it
>>is useful (at least many mathematicians are using it).
>
>BTW, I'm sure you know that double exponential functions are p.r.

But I need to know more than just the asymptotical behaviour to use
it for a bound.

>But when you compute the algorithm on a real computer, you do have bounds
>on time and storage. Thus, even without a known bound, you implicitly 
>program the algorithm in a bounded way. Why is it better to use implicit
>bounds?

The usual way to run this algorithm on more difficult examples is to
start it and see whether you get a useful result before the machine
crashes the next time. I've seen useful results after 1-2 weeks of CPU
time on a Microvax II.

(BTW, you might have used the algorithm already, it's built in in
Mathematica, for simplifying systems of poly equations.)

Sure you can use bounds on the running time (say 1 year). But with
algorithms whose running time is completely unpredictable (that's how
it appears to the user) why not use the natural bound of waiting until
the next downtime of the machine.

I don't think your proposed PR constructs are a bad thing, but I'd like
to have non-PR constructs as well.

Gerald

--
Gerald Baumgartner
Dept. of Computer Sciences, Purdue University, W. Lafayette, IN 47907
Internet: gb@cs.purdue.edu  UUCP: ...!{decwrl,gatech,ucbvax}!purdue!gb