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

-----maxima-bounces at math.utexas.edu wrote: -----

>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)?

As I understand it, CAD applied to linear functions and conditions is
equivalent to Fourier elimination. And that we have:

 (%i3) load(fourier_elim)$
 (%i4) fourier_elim([8 < x + y, x + y < 17, -1 < x - y, x-y < 42],[x,y]);
 (%o4) [max(8-y,y-1)<x,x<min(y+42,17-y),-17<y,y<9]

 (%i5) fourier_elim([8 < x + y, x + y < 17, -1 < x - y, x-y < 42],[y,x]);
 (%o5) [max(8-x,x-42)<y,y<min(x+1,17-x),7/2<x,x<59/2]

The simplex method gives similar results, but doesn't triangularize inequalities:

 (%i6) load(simplex)$

 (%i8) maximize_lp(x, [8 < x + y, x + y < 17, -1 < x - y, x-y < 42]);
 (%o8) [59/2,[y=-25/2,x=59/2]]

 (%i9) minimize_lp(x, [8 < x + y, x + y < 17, -1 < x - y, x-y < 42]);
 (%o9) [7/2,[y=9/2,x=7/2]]

Somebody could connect Maxima to QEPCAD (http://www.usna.edu/Users/cs/qepcad/B/QEPCAD.html).
That has its own set of problems (maintenance of qepcad, no standard FFI for CL, writing Lisp 
code that only does Maxima to qepcad communications is boring, ...)

--Barton