Method for solving a large system of under-determined equations?

Question

I am trying to parametrize and find a family of solutions to some equations. (I am using the solve([eqns],vars) function.) Unfortunately, the equations are just complicated enough so that rather than parametrize, sage gives up and outputs the equations themselves.

Here is a (partial) particular example that I had in mind. My real equation is actually a bit more complicated. But this is a point where it went from solving to simply spitting out the original equations. Here is the output:

10 equations, and 12 unknowns. {s0 + s2 + s4: 1} {s5: 0} {s0 + s1 + s2 + s3 + s4 + s5: 2} {w0: s5} {w1: -s4} {w2: s3} {(s0*w0 + s1*w1)*(s0*w0 + s1*w1 + s2*w2): s2*w0 + s3*w1} {w3: -s2} {w4: s1} {w5: -s0}

Is there anything I can do? I've read the solve and x.solve pages, but I don't see a clear method I should try...

===========

Edit: I'm looking for the simplest representation of this system of equations. I would like Sage to parametrize a few of the variables and solve for the others. For instance, a linear system example would be the following:

eq1=a+b+c==2
eq2=b==1
solve([eq1,eq2],a,b,c)
The output would be:
a=1-r1, b=1, c=r1

Sage can do this using the solve function for small simple situations, even if they're non-linear equations. I want it to classify the family of all possible (real) solutions which satisfy all of the equations simultaneously. But it's stopping when I have a complicated system of equations.

In essence I want it to "solve" the system of equations. Clearly this requires a few parameters, since there are more variables than equations... and since it's not a linear system I can't just ask a linear algebra student to do it. ;-)

Accepted Answer

There is no closed form for the roots of a polynomial in general. So we'll have to assume that you can somehow compute roots.

One nice trick to get a parametrization is to compute a Groebner basis in lexicographic order. You need to put your parameters last in the order of variables. Say,

sage: R.<x,y,z> = PolynomialRing(QQ, order='lex')
sage: I = R.ideal([5*x - 1/3*y^2 - 2*y*z + y - 5/4*z^2, -3/2*x - 1/13*y*z + 4])

These are two (random) polynomial equations in three variables, so we expect the solution to be a curve. Indeed, it is:

sage: I.dimension()
1

It is also an irreducible curve, that is, not two curves that are disjoint or intersect in a point:

sage: I.primary_decomposition()
[Ideal (52*y^2 + 352*y*z - 156*y + 195*z^2 - 2080, 39*x + 2*y*z - 104) of Multivariate Polynomial Ring in x, y, z over Rational Field]

The Groebner basis in the given lexicographic order is:

sage: I.groebner_basis()
[x + 2/39*y*z - 8/3, 
 y^2 + 88/13*y*z - 3*y + 15/4*z^2 - 40]

The last variable (in the lexicographic order) is z, which we take to be the parameter. The second equation in the Groebner basis depends only on y and z, so if you plug in a value for z then it is a polynomial equation in a single variable. Solving this univariate polynomial equation yields multiple (in this case, two) solutions for y. Then plug y,z into the first equation of the Groebner basis. You get one polynomial equation in x, which you have to solve again. Hence, you have determined y(z) and x(y(z),z), that is, parametrized your curve by z.

Thank you very much Volker. This is very clear, and is exactly what I was looking for. David Ferrone (Mar 05 '11)

Answer 2

If you have an underdetermined polynomial system of equations, you should probably think of the solution as an algebraic variety.

sage: AA.<x,y> = AffineSpace(QQ, 2)
sage: X = AA.subscheme(x^2+y^2-1)
sage: X
Closed subscheme of Affine Space of dimension 2 over Rational Field defined by:
  x^2 + y^2 - 1
sage: X.dimension()
1

Its not clear to me what you mean by "solve"... You should rephrase your question as either a geometric property of the variety or an algebraic property of the defining ideal.

Method for solving a large system of under-determined equations?

2 Answers:

Your answer

Question tools

Tags:

Stats:

Related questions