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