Re: Algorithm used by "Reduce" function
- To: mathgroup at smc.vnet.net
- Subject: [mg71846] Re: Algorithm used by "Reduce" function
- From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
- Date: Fri, 1 Dec 2006 06:21:44 -0500 (EST)
- Organization: The Open University, Milton Keynes, UK
- References: <ekme89$8eg$1@smc.vnet.net>
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
http://documents.wolfram.com/mathematica/book/section-A.9.5
"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."
from http://documents.wolfram.com/mathematica/book/section-A.9.5
Regards,
Jean-Marc