MathGroup Archive 2006

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

Search the Archive

Re: Algorithm used by "Reduce" function

  • To: mathgroup at
  • Subject: [mg71846] Re: Algorithm used by "Reduce" function
  • From: Jean-Marc Gulliet <jeanmarc.gulliet at>
  • Date: Fri, 1 Dec 2006 06:21:44 -0500 (EST)
  • Organization: The Open University, Milton Keynes, UK
  • References: <ekme89$8eg$>

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

See "Exact equation solving and reduction" at

"For polynomial systems Reduce uses cylindrical algebraic decomposition 
for real domains and Gröbner basis methods for complex domains.

With algebraic functions, Reduce constructs equivalent purely polynomial 
systems. With transcendental functions, Reduce generates polynomial 
systems composed with transcendental conditions, then reduces these 
using functional relations and a database of inverse image information. 
With piecewise functions, Reduce does symbolic expansion to construct a 
collection of continuous systems.

CylindricalDecomposition uses the Collins-Hong algorithm with 
Brown-McCallum projection for well-oriented sets and Hong projection for 
other sets. CAD construction is done by Strzebonski's genealogy-based 
method using validated numerics backed up by exact algebraic number 
computation. For zero-dimensional systems Gröbner basis methods are used.

For Diophantine systems, Reduce solves linear equations using Hermite 
normal form, and linear inequalities using Contejean-Devie methods. For 
univariate polynomial equations it uses an improved Cucker-Koiran-Smale 
method, while for bivariate quadratic equations, it uses 
Hardy-Muskat-Williams methods for ellipses, and classical techniques for 
Pell and other cases. Reduce includes specialized methods for about 25 
classes of Diophantine equations, including the Tzanakis-de Weger 
algorithm for Thue equations.

With prime moduli, Reduce uses linear algebra for linear equations and 
Gröbner bases over prime fields for polynomial equations. For composite 
moduli, it uses Hermite normal form and Gröbner bases over integers.

Reduce and related functions use about 350 pages of Mathematica code and 
1400 pages of C code."



  • Prev by Date: Re: please explain why ToExpression[SubscriptBox["x","1"],StandardForm] ...
  • Next by Date: Re: Strange empty set of solutions
  • Previous by thread: Re: Algorithm used by "Reduce" function
  • Next by thread: Re: Use pattern to find minimum without using min