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

i like this post (click again to cancel)
i dont like this post (click again to cancel)

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:

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. ;-)

asked Feb 23 '11

David Ferrone gravatar image David Ferrone
141 4 6 12

updated Feb 25 '11

2 Answers:

i like this answer (click again to cancel)
i dont like this answer (click again to cancel) David Ferrone has selected this answer as correct

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()

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.


posted Mar 05 '11

Volker Braun gravatar image Volker Braun
2701 9 24 60
Thank you very much Volker. This is very clear, and is exactly what I was looking for. David Ferrone (Mar 05 '11)
i like this answer (click again to cancel)
i dont like this answer (click again to cancel)

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()

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.


posted Feb 24 '11

Volker Braun gravatar image Volker Braun
2701 9 24 60

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!
Login/Signup to Post

Question tools



Asked: Feb 23 '11

Seen: 706 times

Last updated: Mar 05 '11

powered by ASKBOT version 0.7.22
Copyright Sage, 2010. Some rights reserved under creative commons license.