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

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