inequalities, intervals, Cylindrical Decomposition, CAD, was Re: problems

Real closed fields, CAD, etc., while solveable, are known to be extremely
computationally intensive, in general.

Even the simpler theory of rational order and addition (something I worked on back in
1973-ish) -- roughly what fourier/simplex/etc. do -- is nearly as complex.  I believe
that Jeanne Ferrante & Rackoff wrote the 1975 paper on the complexity of this theory.

http://cseweb.ucsd.edu/~ferrante/

Computers have gotten faster, so larger problems have become solveable, but single
& double exponentials remain very constraining.

Just like integer factoring is usually turned off due to complexity issues, some
of these more powerful methods -- even if implemented -- will usually be turned
off by default due to long running times.

At 09:06 AM 7/10/2011, Richard Fateman wrote:
>On 7/10/2011 8:19 AM, Barton Willis wrote:
>>-----maxima-bounces at math.utexas.edu wrote: -----
>>
>>>Without thinking about this too much, it seems that there is a possibility of using a
>>>(relatively strong) interval arithmetic package to do what sign is supposed to do,
>>Correct me if I'm mistaken, but doing things such as x+y<2 and x-y>5
>>implies y<-3/2 isn't something that interval arithmetic, as generally
>>described, can handle.
>
>You are correct.
>
>>  The sign code needs to be able to do things like this.
>
>Would it be plausible to have a special  "sign of a function of one real variable on a real interval" routine?
>
>>  Also to be useful for sign, intervals need to be open /
>>closed--that might be tedious, but not terribly difficult.
>
>Yes.
>
>>One obstacle is that setting the rounding mode isn't required by
>>CL. For double floats, that makes it difficult to do 100%
>>correct interval arithmetic for all Lisp versions.
>
>Oh, there are many issues that prevent intervals from being "tight".
>
>A more general solution for a function p and  conditions c1, c2, that are all polynomials equalities
>(maybe inequalities too) ...  polynomials in n variables is to do
>"cylindrical algebraic decomposition"  or CAD, which has a large
>literature going back to (at least)  1975. see
>http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1350&context=cstech&sei-redir=1#search=%22cylindrical%20algebraic%20decomposition%20introduction%22
>
>If your problem cannot be reduced to a set of polynomials, this doesn't help.
>
>So far as I know, CAD has not been implemented for Maxima, and it may
>be worthwhile to do so.  I believe that in Mathematica it was first implemented in
>version 5; Mathematica is now on version 8.
>
>A more general Mathematica command is Reduce.  Quoting from the (version 7) manual..
>
>"For polynomial equations or inequalities over the reals, the structure of the result returned by Reduce is typically a cylindrical algebraic decomposition or CAD. Sometimes Reduce can yield a simpler form. But in all cases you can get the complete CAD by using CylindricalDecomposition."
>
>It would be a substantially interesting problem to implement a program similar to Reduce,
>and probably a cutting-edge research project to get it to work beyond polynomials.
>(As, I think, Mathematica now has, to some extent.)
>
>Oh, CAD computations are relatively time-consuming, but computers are fast :)
>
>RJF