MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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 


  • Prev by Date: Bug in Algebra`Horner` Mathematica 5.2 (Win) Package
  • Next by Date: Re: Strange empty set of solutions
  • Previous by thread: Re: Algorithm used by "Reduce" function
  • Next by thread: Re: Algorithm used by "Reduce" function