Ask Your Question
3

I.variety() : missing solution values

asked 2015-04-27 08:03:00 +0100

NeverConvex gravatar image

updated 2015-04-28 02:11:41 +0100

Hi there!

The following code:

sage: R.<x1,x2,x3,x4,x5> = PolynomialRing(RR,5,order='lex')

sage: f1=x1+x2+x3+x4+x5

sage: f2=x1*x2+x2*x3+x3*x4+x4*x5+x1*x5

sage: f3=x1*x2*x3+x2*x3*x4+x3*x4*x5+x4*x5*x1+x5*x1*x2

sage: f4=x1*x2*x3*x4+x2*x3*x4*x5+x3*x4*x5*x1+x4*x5*x1*x2+x5*x1*x2*x3

sage: f5=x1*x2*x3*x4*x5-1

sage: I = Ideal(f1,f2,f3,f4,f5)

sage: I.variety()

produces

verbose 0 (2403: multi_polynomial_ideal.py, variety) Warning: falling back to very slow toy implementation.

[{x5: -2.61803398874989}, {x5: -0.381966011250105}, {x5: 1.00000000000000}]

which seems to be missing a large number of solution values, and only producing values for x5 even in those solutions in reports on, for some reason. A similar problem occurs if I solve over CC rather than RR (but involves a lot more text, so this seemed nicer to copy/paste).

If I change the order from lex to degrevlex, I.variety() fails with the following error message:

verbose 0 (2403: multi_polynomial_ideal.py, variety) Warning: falling back to very slow toy implementation.
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-479-cb6d916bc8b3> in <module>()
----> 1 I.variety()

/Applications/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.pyc in __call__(self, *args, **kwds)
    603         if not R.base_ring().is_field():
    604             raise ValueError("Coefficient ring must be a field for function '%s'."%(self.f.__name__))
--> 605         return self.f(self._instance, *args, **kwds)
    606 
    607 require_field = RequireField

/Applications/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.pyc in variety(self, ring)
   2667           if self.ring().term_order().is_global():
   2668             verbose("Warning: falling back to very slow toy implementation.", level=0)
-> 2669             T = toy_variety.triangular_factorization(self.groebner_basis())
   2670           else:
   2671             raise TypeError("Local/unknown orderings not supported by 'toy_buchberger' implementation.")

/Applications/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/toy_variety.pyc in triangular_factorization(B, n)
    279   # recursively build the family,
    280   # looping through the factors of p
--> 281   for (q,a) in p.factor():
    282     # Construct an analog to I in (R.quotient(R.ideal(q)))[x_0,x_1,...x_{n-1}]
    283     I = R.ideal([each.reduce([q]) for each in G])

/Applications/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_element.pyc in factor(self, proof)
   1662                 raise NotImplementedError("Factorization of multivariate polynomials over prime fields with characteristic > 2^29 is not implemented.")
   1663         if proof:
-> 1664             raise NotImplementedError("proof = True factorization not implemented.  Call factor with proof=False.")
   1665 
   1666         R._singular_().set_ring()

which is kind've mystifying, since we're working over either RR or CC, both of which have characteristic 0, and neither of which is a prime field. I thought maybe this is related to I.variety()'s odd behavior under lex order somehow, though, so it'd be worth including here.

I know this system has 10 real solutions (it's an example from HOM4PS2's documentation, and ... (more)

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
2

answered 2018-11-11 16:08:28 +0100

tmonteil gravatar image

updated 2018-11-12 22:47:25 +0100

To complement @jipilab's answer, since your equations have only integer coefficients you will not miss points by looking at algebraic solutions.

So, the first idea is to replace RR with QQbar in the definition of R. Unfortunately, we currently do not ship fast implementation of groebner bases in over this field, so that it will be very slow:

sage: R.<x1,x2,x3,x4,x5> = PolynomialRing(QQbar,5,order='lex')
sage: f1=x1+x2+x3+x4+x5
sage: f2=x1*x2+x2*x3+x3*x4+x4*x5+x1*x5
sage: f3=x1*x2*x3+x2*x3*x4+x3*x4*x5+x4*x5*x1+x5*x1*x2
sage: f4=x1*x2*x3*x4+x2*x3*x4*x5+x3*x4*x5*x1+x4*x5*x1*x2+x5*x1*x2*x3
sage: f5=x1*x2*x3*x4*x5-1
sage: I = Ideal(f1,f2,f3,f4,f5)
sage: I.variety()
verbose 0 (3452: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
[...stalled...]

The trick is to define the equations over the rational and pass to the algebraics only when asking for the variety:

sage: R.<x1,x2,x3,x4,x5> = PolynomialRing(QQ,5,order='lex')
sage: f1=x1+x2+x3+x4+x5
sage: f2=x1*x2+x2*x3+x3*x4+x4*x5+x1*x5
sage: f3=x1*x2*x3+x2*x3*x4+x3*x4*x5+x4*x5*x1+x5*x1*x2
sage: f4=x1*x2*x3*x4+x2*x3*x4*x5+x3*x4*x5*x1+x4*x5*x1*x2+x5*x1*x2*x3
sage: f5=x1*x2*x3*x4*x5-1
sage: I = Ideal(f1,f2,f3,f4,f5)
sage: V = I.variety(QQbar)
sage: len(V)
70

So, you get that there are 70 solutions to your system of polynomial equations.

edit flag offensive delete link more
1

answered 2018-11-11 14:06:37 +0100

jipilab gravatar image

According to the documentation of

sage: I.variety?

we read:

Note that with "ring=RR" or "CC", computation is done numerically and potentially inaccurately; in particular, the number of points in the real variety may be miscomputed. With "ring=AA" or "QQbar", computation is done exactly (which may be much slower, of course).

Being miscomputed might also include "missing solutions"... This triangular decomposition also highly depends on the ideal and its groebner basis computation.

Currently, it seems indeed that getting a 0-dimensional variety out of an ideal is rather hazardous.

I am using Bertini to do such computations, eventually is could be interfaced in Sage.

Otherwise, maybe the interface to PHC could do the thing:

http://doc.sagemath.org/html/en/refer...

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

1 follower

Stats

Asked: 2015-04-27 08:03:00 +0100

Seen: 1,033 times

Last updated: Nov 12 '18