Symbolic GCD
Gaëtan Bisson
I would like to do some symbolic computation using SAGE, namely, to
compute the extended GCD of two polynomials, one of them having symbolic
coefficients.
Here is a short example:
sage: R.<a,b>=PolynomialRing(RationalField(),2);
sage: S.<x>=PolynomialRing(R);
sage: xgcd(x^2,a+x*b)
As an answer, I would expect:
(b^2/a^2, 1, -x/a+b/a^2)
However, this raises the error:
<type 'exceptions.TypeError'>: cannot coerce nonconstant polynomial
Am I missing a way of actually doing the computation in SAGE or is this
just not implemented yet?
Thanks for your help,
--Gaetan Bisson
Gaëtan Bisson
> Here is a short example:
> sage: R.<a,b>=PolynomialRing(RationalField(),2);
> sage: S.<x>=PolynomialRing(R);
> sage: xgcd(x^2,a+x*b)
>
I've forgotten to mention which versions of SAGE I'm using:
SAGE Version 3.0, Release Date: 2008-04-23
SAGE Version 3.0.1, Release Date: 2008-05-04
--
Gaetan Bisson
Carl Witty
> Dear SAGE community,
>
> I would like to do some symbolic computation using SAGE, namely, to
> compute the extended GCD of two polynomials, one of them having symbolic
> coefficients.
>
> Here is a short example:
> sage: R.<a,b>=PolynomialRing(RationalField(),2);
> sage: S.<x>=PolynomialRing(R);
> sage: xgcd(x^2,a+x*b)
>
> As an answer, I would expect:
> (b^2/a^2, 1, -x/a+b/a^2)
sage: R.<a,b> = QQ[]
sage: S.<x> = R.fraction_field()[]
sage: xgcd(x^2, a*x+b)
(b^2/a^2, 1, ((-1)/a)*x + b/a^2)
Carl
Gaëtan Bisson
> You need to explicitly use the field of fractions of R:
>
> sage: R.<a,b> = QQ[]
> sage: S.<x> = R.fraction_field()[]
> sage: xgcd(x^2, a*x+b)
> (b^2/a^2, 1, ((-1)/a)*x + b/a^2)
Thanks. Is it possible to do the same computation over a number field
(instead of QQ)?
For instance:
R.<a,b> = NumberField(x^2-3,'g')[]
S.<y> = R.fraction_field()[]
xgcd(y^2, a*y+b)
returns the error: (more below)
<type 'exceptions.TypeError'>: unsupported operand type(s) for %: 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic' and 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic'
Thanks again,
--Gaetan Bisson
-------- Expanded Error --------
<type 'exceptions.TypeError'> Traceback (most recent call last)
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/<ipython console> in <module>()
/localdisk/tmp/sage-3.0/local/lib/python2.5/site-packages/sage/rings/arith.py in xgcd(a, b)
1236 """
1237 try:
-> 1238 return a.xgcd(b)
1239 except AttributeError:
1240 pass
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/element.pyx in sage.structure.element.PrincipalIdealDomainElement.xgcd (sage/structure/element.c:11868)()
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial._xgcd (sage/rings/polynomial/polynomial_element.c:23536)()
/localdisk/tmp/sage-3.0/local/lib/python2.5/site-packages/sage/rings/polynomial/polynomial_element_generic.py in quo_rem(self, other)
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/element.pyx in sage.structure.element.ModuleElement.__isub__ (sage/structure/element.c:5647)()
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/coerce.pxi in sage.structure.element._sub_c (sage/structure/element.c:15663)()
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/element.pyx in sage.structure.element.ModuleElement._sub_ (sage/structure/element.c:5575)()
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial_generic_dense._sub_c_impl (sage/rings/polynomial/polynomial_element.c:28087)()
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/element.pyx in sage.structure.element.ModuleElement.__sub__ (sage/structure/element.c:5410)()
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/coerce.pxi in sage.structure.element._sub_c (sage/structure/element.c:15663)()
/localdisk/tmp/sage-3.0/local/lib/python2.5/site-packages/sage/rings/fraction_field_element.py in _sub_(self, right)
292 gcd_denom = self.__denominator.gcd(right.__denominator)
293 if not gcd_denom.is_unit():
--> 294 right_mul = self.__denominator // gcd_denom
295 self_mul = right.__denominator // gcd_denom
296 numer = self.__numerator * self_mul - right.__numerator * right_mul
/localdisk/tmp/sage-3.0/local/lib/python2.5/site-packages/sage/rings/polynomial/multi_polynomial_element.py in __floordiv__(self, right)
/usr/local/sage-3.0/sage/devel/sage-main/sage/rings/element.pyx in sage.structure.element.CommutativeRingElement.divides (sage/structure/element.c:10099)()
<type 'exceptions.TypeError'>: unsupported operand type(s) for %: 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic' and 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic'
Carl Witty
> Carl Witty wrote:
> > You need to explicitly use the field of fractions of R:
>
> > sage: R.<a,b> = QQ[]
> > sage: S.<x> = R.fraction_field()[]
> > sage: xgcd(x^2, a*x+b)
> > (b^2/a^2, 1, ((-1)/a)*x + b/a^2)
>
> Thanks. Is it possible to do the same computation over a number field
> (instead of QQ)?
>
> For instance:
> R.<a,b> = NumberField(x^2-3,'g')[]
> S.<y> = R.fraction_field()[]
> xgcd(y^2, a*y+b)
>
> returns the error: (more below)
> <type 'exceptions.TypeError'>: unsupported operand type(s) for %: 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic' and 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic'
call it a missing feature instead). I've posted a patch here,
http://trac.sagemath.org/sage_trac/ticket/3327 so this will work in
some future version of Sage (likely the next version, assuming that
somebody positively reviews my patch).
Carl
Gaëtan Bisson
> >
> > For instance:
> > R.<a,b> = NumberField(x^2-3,'g')[]
> > S.<y> = R.fraction_field()[]
> > xgcd(y^2, a*y+b)
> >
> > returns the error: (more below)
> > <type 'exceptions.TypeError'>: unsupported operand type(s) for %: 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic' and 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic'
>
> This should work, but doesn't due to a bug (well, perhaps you could
> call it a missing feature instead). I've posted a patch here,
> http://trac.sagemath.org/sage_trac/ticket/3327 so this will work in
> some future version of Sage (likely the next version, assuming that
> somebody positively reviews my patch).
Thank you so much. The patch is indeed working fine.
I still have issues when involving a tower of number fields, though.
That is, the following code:
R.<a,b> = NumberField(x^2-3,'g').extension(x^2-7,'h')[]
h = R.base_ring().gen()
S.<y> = R.fraction_field()[]
xgcd(y^2, a*h*y+b)
raises the error:
NameError: name 'h' is not defined
Note, however, that when the first line is replaced by:
R.<a,b> = NumberField(x^2-3,'h')[]
computations run flawlessly and SAGE outputs the result:
(b^2/(3*a^2), 1, ((-1)/(h*a))*y + b/(3*a^2))
Do I have to define 'h' in a more "robust" way to avoid that
or is this unrelated to the way it's defined?
Thanks again,
--Gaetan
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
/users/cacao/bissogae/<ipython console> in <module>()
/usr/local/sage-3.0.2/sage/local/lib/python2.5/site-packages/sage/rings/arith.py in xgcd(a, b)
1243 """
1244 try:
-> 1245 return a.xgcd(b)
1246 except AttributeError:
1247 pass
/users/cacao/bissogae/element.pyx in sage.structure.element.PrincipalIdealDomainElement.xgcd (sage/structure/element.c:11861)()
/users/cacao/bissogae/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial._xgcd (sage/rings/polynomial/polynomial_element.c:23441)()
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/polynomial/polynomial_element_generic.py in quo_rem(self, other)
/users/cacao/bissogae/element.pyx in sage.structure.element.RingElement.__mul__ (sage/structure/element.c:8544)()
/users/cacao/bissogae/coerce.pyx in sage.structure.coerce.CoercionModel_cache_maps.bin_op_c (sage/structure/coerce.c:5027)()
/users/cacao/bissogae/action.pyx in sage.categories.action.Action._call_c (sage/categories/action.c:1682)()
/users/cacao/bissogae/coerce.pyx in sage.structure.coerce.LeftModuleAction._call_c_impl (sage/structure/coerce.c:12298)()
/users/cacao/bissogae/coerce.pxi in sage.structure.coerce._rmul_c (sage/structure/coerce.c:2411)()
/users/cacao/bissogae/element.pyx in sage.structure.element.ModuleElement._rmul_ (sage/structure/element.c:6770)()
/users/cacao/bissogae/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial_generic_dense._rmul_c_impl (sage/rings/polynomial/polynomial_element.c:28474)()
/users/cacao/bissogae/element.pyx in sage.structure.element.RingElement.__mul__ (sage/structure/element.c:8527)()
/users/cacao/bissogae/coerce.pxi in sage.structure.element._mul_c (sage/structure/element.c:16109)()
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/fraction_field_element.py in _mul_(self, right)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/fraction_field_element.py in __init__(self, parent, numerator, denominator, coerce, reduce)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/fraction_field_element.py in reduce(self)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/polynomial/multi_polynomial_element.py in quo_rem(self, right)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/polynomial/multi_polynomial_ring.py in __call__(self, x, check)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/interfaces/singular.py in sage_poly(self, R, kcache)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.py in __call__(self, x)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.py in __call__(self, x)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.py in _coerce_from_str(self, x)
/localdisk/tmp/sage-3.0.2/local/lib/python2.5/site-packages/sage/misc/sage_eval.py in sage_eval(source, locals)
/users/cacao/bissogae/<string> in <module>()
NameError: name 'h' is not defined
Carl Witty
> Carl Witty wrote :
>
>
>
> > > For instance:
> > > R.<a,b> = NumberField(x^2-3,'g')[]
> > > S.<y> = R.fraction_field()[]
> > > xgcd(y^2, a*y+b)
>
> > > returns the error: (more below)
> > > <type 'exceptions.TypeError'>: unsupported operand type(s) for %: 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic' and 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic'
>
> > This should work, but doesn't due to a bug (well, perhaps you could
> > call it a missing feature instead). I've posted a patch here,
> > somebody positively reviews my patch).
>
> Thank you so much. The patch is indeed working fine.
>
> I still have issues when involving a tower of number fields, though.
> That is, the following code:
>
> R.<a,b> = NumberField(x^2-3,'g').extension(x^2-7,'h')[]
> h = R.base_ring().gen()
> S.<y> = R.fraction_field()[]
> xgcd(y^2, a*h*y+b)
>
> raises the error:
> NameError: name 'h' is not defined
>
> Note, however, that when the first line is replaced by:
> R.<a,b> = NumberField(x^2-3,'h')[]
> computations run flawlessly and SAGE outputs the result:
> (b^2/(3*a^2), 1, ((-1)/(h*a))*y + b/(3*a^2))
>
> Do I have to define 'h' in a more "robust" way to avoid that
> or is this unrelated to the way it's defined?
Sage keeps its fraction field elements in reduced form, by performing
GCDs between the numerator and denominator. Sage uses Singular to
find the GCD of multivariate polynomials, but Singular does not
support towers of number fields. The above traceback shows Sage
trying, and failing, to use Singular with towers of number fields.
I've opened a couple of bug reports for this example,
http://trac.sagemath.org/sage_trac/ticket/3329 and
http://trac.sagemath.org/sage_trac/ticket/3330; the first just says
there should be a better error message, and the second requests an
actual implementation.
Until somebody fixes the code (maybe you want to work on it
yourself?), probably the best solution is to convert your tower of
number fields into a single absolute number field and do the
computation with this single field. You can do this with
the .absolute_field() method, and convert back and forth using the
isomorphisms from the .structure() method on the absolute field.
sage: K = NumberField(x^2-3,'g').extension(x^2-7,'h')
sage: Kabs = K.absolute_field('j'); Kabs
Number Field in j with defining polynomial x^4 - 20*x^2 + 16
sage: Kabs.structure()
(Isomorphism from Number Field in j with defining polynomial x^4 -
20*x^2 + 16 to Number Field in h with defining polynomial x^2 - 7 over
its base field,
Isomorphism from Number Field in h with defining polynomial x^2 - 7
over its base field to Number Field in j with defining polynomial x^4
- 20*x^2 + 16)
Carl
Gaëtan Bisson
>
> I've opened a couple of bug reports for this example,
> http://trac.sagemath.org/sage_trac/ticket/3329 and
> http://trac.sagemath.org/sage_trac/ticket/3330; the first just says
> there should be a better error message, and the second requests an
> actual implementation.
>
> Until somebody fixes the code (maybe you want to work on it
> yourself?), probably the best solution is to convert your tower of
> number fields into a single absolute number field and do the
> computation with this single field. You can do this with
> the .absolute_field() method, and convert back and forth using the
> isomorphisms from the .structure() method on the absolute field.
Unfortunately, I'm don't think I have the skills it would take
to fix the code. Thanks for the workaround.
--
Gaetan