Group Abstract Group Abstract

Message Boards Message Boards

Eliminate produced redundant equations?

Posted 10 years ago
POSTED BY: Daniel Huber
18 Replies

That rewrite requires that the a and b variables be regarded as parameters rather than algebraic variables. Which might or might not be what was intended.

POSTED BY: Daniel Lichtblau

Yes! a and b are regarded as the coefficients!

But Eliminate does not know which are to be regarded as coefficients and which as variables. So this matrix approach is not a faithful representation of the actual elimination.

POSTED BY: Daniel Lichtblau

I started from initial interpretation that a and b are two given vectors, i.e. their coordinates are fixed. But, if we think about coordinates of a and b as variables, the equations are bi-linear that makes equations somewhat simpler for Eliminate[].

Posted 10 years ago
POSTED BY: Daniel Huber
Posted 10 years ago

Eliminates produces a third new equation. Geometrically we get an additional plane containing the intersection of the two first planes. Therefore it is redundant for the problem at hand. But "Eliminate" has produced additional info, what surprises me.
I would like to understand this. Unfortunately I do not understand Groebner basis and what I find in the Wiki is a bit above my head. Can you point me to some simple explanation that a humble physician is able to understand?

POSTED BY: Daniel Huber

There are textbook references for Groebner bases, but even those are far from elementary. The one by Cox, Little, and O'Shea is perhaps most accessible, which still means it takes time and some amount of undergraduate math prerequisite. Possibly a decent place to look would be early articles by Bruno Buchberger (who named them for his thesis advisor).

In very brief terms, Groebner bases generalize both Gaussian elimination (the linear case) and the Euclidean algorithm (the univariate case). Given a set of polynomials they come up with another set generating the same "polynomial space" (ideal, in the language of algebra) but with a certain nice property: any element in the space can be "reduced" to zero, by a form of generalized division by the Groebner basis. This property will not in general hold for the original set. A set with this property gives a nice algorithmic way of determining membership (and that was the original purpose of Buchberger's work, 50+ years ago).

These bases are with respect to what are known as "term orders". It happens that certain term orders can be used for elimination of variables (meaning: the result is a Groebner basis for the subset of polynomials in the original set that do not contain the eliminated variables).

I realize this is probably too brief a description to be helpful. But if one wants to know what elimination of variables is doing, one has to deal with a bit of hard-core algebra (I just hope "deal with" is not "suffer with").

POSTED BY: Daniel Lichtblau
Posted 10 years ago

Thank you Daniel, the " Cox, Little, and O'Shea" seems to be digestible.

POSTED BY: Daniel Huber
Posted 10 years ago
POSTED BY: Daniel Huber

Daniel,

GroebnerBasis by default treats all indeterminates as "variables". To get the ones not listed to be seen as "parameters", use CoefficientDomain->RationalFunctions.

eq2a = {z1 - u1, z2 - u2, z3 - 1 - u3, a1 u1 + a2 u2 + a3 (1 + u3), 
   b1 u1 + b2 u2 + b3 (1 + u3)};
vars = {z1, z2, z3, u1, u2, u3};
gb = GroebnerBasis[eq2a, vars, CoefficientDomain -> RationalFunctions]

(* Out[1198]= {a3 b1 - 
  a1 b3 + (a2 b1 - a1 b2) u2 + (a3 b1 - a1 b3) u3, -a3 b2 + 
  a2 b3 + (a2 b1 - a1 b2) u1 + (-a3 b2 + a2 b3) u3, -1 - u3 + z3, 
 a3 b1 - a1 b3 + (a3 b1 - a1 b3) u3 + (a2 b1 - a1 b2) z2, -a3 b2 + 
  a2 b3 + (-a3 b2 + a2 b3) u3 + (a2 b1 - a1 b2) z1} *)

Here we show that no lead term divides another in Q(a,b).

leadterms = 
 GroebnerBasis`DistributedTermsList[gb, vars, 
   CoefficientDomain -> RationalFunctions][[1, All, 1]]

(* Out[1199]= {{{0, 0, 0, 0, 1, 0}, a2 b1 - a1 b2}, {{0, 0, 0, 1, 0, 0}, 
  a2 b1 - a1 b2}, {{0, 0, 1, 0, 0, 0}, 1}, {{0, 1, 0, 0, 0, 0}, 
  a2 b1 - a1 b2}, {{1, 0, 0, 0, 0, 0}, a2 b1 - a1 b2}} *)

There are a couple of important things to keep in mind. One is that Eliminate is based on ancient design and code. It has no concept of "parameters" and every indeterminate is either a variable to be eliminated or one to be retained (I made a comment to this effect a few days ago in this thread). The other, as noted above, is that GroebnerBasis has a default setting and it might not be the one that is what you implicitly have in mind.

POSTED BY: Daniel Lichtblau
Posted 10 years ago

Daniel, thanks a lot. The hint about "CoefficientDomain" really helps, I do not think I would have realized this myself.

Now the problem with "Eliminate". Is it too naive an approach to simply test the output of Eliminate for linear dependencies and eliminate if necessary. Or is the problem more subtle?

POSTED BY: Daniel Huber
POSTED BY: Daniel Lichtblau
Posted 10 years ago

O.k. I take your advice. GroebnerBasis seems to be the way to go. And it also has a nice psychological aspect by using a new technique just learned. thank's for all, Daniel

POSTED BY: Daniel Huber

I don't see the linear dependency of a1 (b3+b2 u2+b3 u3)==b1 (a3+a2 u2+a3 u3) on the set

{a3+a1 u1+a2 u2+a3 u3==0,
b3+b1 u1+b2 u2+b3 u3==0}
POSTED BY: Daniel Lichtblau
Posted 10 years ago

You are right, I must have made a mistake when checking for dependency. However, now it is even worse,the third equation is additional information. Where does it coming from?

POSTED BY: Daniel Huber

The full result comes from a Groebner basis computation with a term ordering that eliminates the variables requested.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard