Ask Your Question

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

asked 2011-02-23 21:30:43 +0200

David Ferrone gravatar image

updated 2011-02-26 00:04:27 +0200

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

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2011-03-05 12:16:09 +0200

Volker Braun gravatar image

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.

edit flag offensive delete link more


Thank you very much Volker. This is very clear, and is exactly what I was looking for.

David Ferrone gravatar imageDavid Ferrone ( 2011-03-05 14:54:49 +0200 )edit

answered 2011-02-24 07:21:27 +0200

Volker Braun gravatar image

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2011-02-23 21:30:43 +0200

Seen: 4,582 times

Last updated: Mar 05 '11