ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 11 Nov 2018 09:08:28 -0600I.variety() : missing solution valueshttp://ask.sagemath.org/question/26654/ivariety-missing-solution-values/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 I've solved it using HOM4PS2 without issue: http://www.math.nsysu.edu.tw/~leetsung/works/HOM4PS_soft_files/HOM4PS_Linux.htm ). Why isn't Sage finding and/or reporting all of this system's solutions? Under lex order, is it perhaps placing the system into a suitable Groebner basis, solving the univariate x5 equation(s), and then giving up on the x1-x4's, but not telling us that it's doing so? Or is it just suppressing some of the output for some reason? (or.. something else entirely that I haven't thought of!)
Thanks for your time!
p.s. Using the singular_console() in Sage and adapting this example (: http://www.singular.uni-kl.de/Manual/latest/sing_887.htm#SEC938 ) to the present case seems to work perfectly, so perhaps this is just a limitation of Sage's implementation of Buchberger's algorithm & variety-solving? I'd assumed I.variety() would implement a wrapper to some appropriate Singular technique, but maybe that's not the case.Mon, 27 Apr 2015 01:03:00 -0500http://ask.sagemath.org/question/26654/ivariety-missing-solution-values/Answer by tmonteil for <div class="snippet"><p>Hi there!</p>
<p>The following code:</p>
<pre><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()
</code></pre>
<p>produces</p>
<pre><code>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}]
</code></pre>
<p>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).</p>
<p>If I change the order from <em>lex</em> to <em>degrevlex</em>, I.variety() fails with the following error message:</p>
<pre><code>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()
</code></pre>
<p>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.</p>
<p>I know this system has 10 real solutions (it's an example from HOM4PS2's documentation, and ...<span class="expander"> <a>(more)</a></span></p></div> http://ask.sagemath.org/question/26654/ivariety-missing-solution-values/?answer=44240#post-id-44240To 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.Sun, 11 Nov 2018 09:08:28 -0600http://ask.sagemath.org/question/26654/ivariety-missing-solution-values/?answer=44240#post-id-44240Answer by jipilab for <div class="snippet"><p>Hi there!</p>
<p>The following code:</p>
<pre><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()
</code></pre>
<p>produces</p>
<pre><code>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}]
</code></pre>
<p>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).</p>
<p>If I change the order from <em>lex</em> to <em>degrevlex</em>, I.variety() fails with the following error message:</p>
<pre><code>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()
</code></pre>
<p>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.</p>
<p>I know this system has 10 real solutions (it's an example from HOM4PS2's documentation, and ...<span class="expander"> <a>(more)</a></span></p></div> http://ask.sagemath.org/question/26654/ivariety-missing-solution-values/?answer=44236#post-id-44236According 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/reference/interfaces/sage/interfaces/phc.htmlSun, 11 Nov 2018 07:06:37 -0600http://ask.sagemath.org/question/26654/ivariety-missing-solution-values/?answer=44236#post-id-44236