From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: (Q) Solution of simultaneous equations
Date: 21 Jul 1998 06:16:29 GMT
Keywords: algorithm equations

Timothy Murphy <tim@maths.tcd.ie> wrote:
>Is there an algorithm for determining
>if a set of simultaneous polynomial equations over the reals
>has a real solution ?

This is the import of Tarski's Elimination of Quantifiers. You may
think about this algebraically (use elimination to reduce to one
equation in several unknowns) or think about it geometrically (the
equations define a variety; you can check for points by looking for
points in the projection to a quotient space).

>If so, is there an implementation of the algorithm
>in a computer program ?
>
>[The polynomial equations have integer coefficients.]

I don't know of software which is designed for this specific purpose.
I suppose most commonly one computes a Groebner basis for the
ideal defining the variety (or better: for the radical of this ideal);
this will in effect compute the projections of the variety to a
flag of quotient spaces, and one may proceed from the smaller spaces to
the larger, either computing each real coordinate of a point in turn,
or showing that none exists. This is easier to interpret in the case
the variety is zero-dimensional, but I think it can be carried out in
the general case too.

dave