Re: Algorithm used by "Reduce" function

*To*: mathgroup at smc.vnet.net*Subject*: [mg71874] Re: [mg71823] Algorithm used by "Reduce" function*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Fri, 1 Dec 2006 06:22:33 -0500 (EST)*References*: <200611301105.GAA08472@smc.vnet.net>

On 30 Nov 2006, at 20:05, Jim Smith wrote: > Hello, > > Does anyone happen to know the algorithm used by the "Reduce" > function? > For instance: > > In[1]:= Reduce[{10x + 5y + z == 10, x + y + z == 1, x ³ 0, y ³ 0, > z ³ 0}, {x, y, z}] > > Out[1]= x == 1 && y == 0 && z == -y > > How does it achieve this answer? > > Thanks, > Jim > It uses many algorithms, but for this particular example (very trivial one) it calls up an algorithm from "real algebraic geometry" called CylindricalAlgebraicDecomposition (due to G.E. Collins). In[1]:= CylindricalDecomposition[{10*x + 5*y + z == 10, x + y + z == 1, x >= 0, y >= 0, z >= 0}, {x, y, z}] Out[1]= x == 1 && y == 0 && z == 0 Note that the form of the answer above is equivalent but slightly different from the one given by Reduce, which is due to the multi- algorithm nature of Reduce. Andrzej Kozlowski