# source:sage/rings/multi_polynomial_element.py@1:bf5417bc8931

Revision 1:bf5417bc8931, 26.0 KB checked in by tornaria@…, 7 years ago (diff)

[project @ patch to sage-0.10.13]

Line
1"""
2Multivariate Polynomials
3
4AUTHORS:
5    -- David Joyner: first version
6    -- William Stein: use dict's instead of lists
7    -- Martin Albrecht <malb@informatik.uni-bremen.de>: some functions added
8"""
9
10#*****************************************************************************
11#
12#   SAGE: System for Algebra and Geometry Experimentation
13#
14#       Copyright (C) 2005 William Stein <wstein@ucsd.edu>
15#
17#
18#    This code is distributed in the hope that it will be useful,
19#    but WITHOUT ANY WARRANTY; without even the implied warranty of
20#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21#    General Public License for more details.
22#
23#  The full text of the GPL is available at:
24#
26#*****************************************************************************
27
28import operator
29
30import arith
31
32from sage.structure.element import CommutativeRingElement, Element_cmp_
33from coerce import bin_op, cmp as coerce_cmp
34
35from sage.interfaces.all import singular
36
37import sage.misc.misc as misc
38import integer
39
40import polydict
41
42from sage.structure.factorization import Factorization
43
44import multi_polynomial_ring
45import polynomial_ring
46
47def is_MPolynomialRingElement(x):
48    return isinstance(x, MPolynomial)
49
50class MPolynomial(Element_cmp_, CommutativeRingElement):
51    def __init__(self, parent, x):
52        CommutativeRingElement.__init__(self, parent)
53        self.__element = x
54
55    def _repr_(self):
56        return "%s"%self.__element
57
58    def __call__(self, *x):
59        """
60        Evaluate this multi-variate polynomial at $x$, where $x$ is
61        either the tuple of values to substitute in, or one can use
62        functional notation $f(a_0,a_1,a_2, \ldots)$ to evaluate $f$
63        with the ith variable replaced by $a_i$.
64
65        EXAMPLES:
66            sage: x, y = MPolynomialRing(RationalField(),2).gens()
67            sage: f = x^2 + y^2
68            sage: f(1,2)
69            5
70            sage: f((1,2))
71            5
72
73            sage: x = MPolynomialRing(RationalField(),3).gens()
74            sage: f = x[0] + x[1] - 2*x[1]*x[2]
75            sage: f
76            x_1 - 2*x_1*x_2 + x_0
77            sage: f(1,2,0)
78            3
79            sage: f(1,2,5)
80            -17
81
82        AUTHOR: David Kohel, 2005-09-27
83        """
84        if len(x) == 1 and isinstance(x[0], (list, tuple)):
85            x = x[0]
86        n = self.parent().ngens()
87        if len(x) != n:
88            raise TypeError, "x (=%s) must be of length %s"%(x, n)
89        if n == 0:
90            return self
91        try:
92            K = x[0].parent()
93        except AttributeError:
94            K = self.parent().base_ring()
95        y = K(0)
96        for (m,c) in self.element().dict().iteritems():
97            y += c*misc.mul([ x[i]**m[i] for i in range(n) ])
98        return y
99
100    def _cmp_(self, right):
101        # MAJOR todo -- this should be relative to the term order, but isn't right now.
102        return self.__element.__cmp__(right.__element)
103
104    def _im_gens_(self, codomain, im_gens):
105        """
106        EXAMPLES:
107            sage: R, (x,y) = PolynomialRing(Q, 2, 'xy').objgens()
108            sage: f = R.hom([y,x], R)
109            sage: f(x^2 + 3*y^5)
110            y^2 + 3*x^5
111        """
112        n = self.parent().ngens()
113        if n == 0:
114            return codomain._coerce_(self)
115        y = codomain(0)
116        for (m,c) in self.element().dict().iteritems():
117            y += codomain(c)*misc.mul([ im_gens[i]**m[i] for i in range(n) ])
118        return y
119
120
122        return self.parent()(self.__element + right.__element)
123
124    def _sub_(self, right):
125        return self.parent()(self.__element - right.__element)
126
127    def _mul_(self, right):
128        return self.parent()(self.__element * right.__element)
129
130    def _div_(self, right):
131        return self.parent().fraction_field()(self.__element, right.__element)
132
133    def __pow__(self, n):
134        if not isinstance(n, (int, long, integer.Integer)):
135            raise TypeError, "The exponent (n=%s) must be an integer."%n
136        if n < 0:
137            return 1/(self**(-n))
138        return self.parent()(self.__element**n)
139
140    def __rpow__(self, n):
141        if not isinstance(n, (int, long, integer.Integer)):
142            raise TypeError, "The exponent (n=%s) must be an integer."%n
143        return self.parent()(self.__element**n)
144
145    def element(self):
146        return self.__element
147
148
149
150class MPolynomial_polydict(MPolynomial):
151    def __init__(self, parent, x):
152        """
153        EXAMPLES:
154            sage: R, x = MPolynomialRing(QQ,10).objgens()
155            sage: x
156            (x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9)
158            True
159        """
160        if not isinstance(x, polydict.PolyDict):
161            x = polydict.PolyDict(x, parent.base_ring()(0), remove_zero=True)
162        MPolynomial.__init__(self, parent, x)
163
164    def __neg__(self):
165        return self*(-1)
166
167    def _repr_(self):
168        return self.element().poly_repr(self.parent().variable_names(),
169                                        atomic_coefficients=self.parent().base_ring().is_atomic_repr())
170
171    def _latex_(self):
172        return self.element().latex(self.parent().latex_variable_names(),
173                                    atomic_coefficients=self.parent().base_ring().is_atomic_repr())
174
175    def _repr_with_changed_varnames(self, varnames):
176        return self.element().poly_repr(varnames,
177                                        atomic_coefficients=self.parent().base_ring().is_atomic_repr())
178
179
180    def degree(self, x=None):
181        """
182        Return the degree of self in x, where x must be one of the
183        generators for the parent of self.
184
185        INPUT:
186            x -- multivariate polynmial (a generator of the parent of self)
187                 If x is not specified (or is None), return the total degree,
188                 which is the maximum degree of any monomial.
189
190        OUTPUT:
191            integer
192
193        EXAMPLE:
194            sage: x, y = MPolynomialRing(RationalField(), 2, names = ['x','y']).gens()
195            sage: f = y^2 - x^9 - x
196            sage: f.degree(x)
197            9
198            sage: f.degree(y)
199            2
200            sage: (y^10*x - 7*x^2*y^5 + 5*x^3).degree(x)
201            3
202            sage: (y^10*x - 7*x^2*y^5 + 5*x^3).degree(y)
203            10
204        """
205        if x is None:
206            return self.element().degree(None)
207        if not (isinstance(x, MPolynomial) and x.parent() == self.parent() and x.is_monomial()):
208            raise TypeError, "x (=%s) must be one of the generators of the parent."%x
209        return self.element().degree(x.element())
210
211    def total_degree(self):
212        """
213        Return the total degree of self, which is the
214        maximum degree of any monomial in self.
215
216        EXAMPLES:
217            sage: x,y,z = MPolynomialRing(QQ,3,names=['x','y','z']).gens()
218            sage: f=2*x*y^3*z^2
219            sage: f.total_degree()
220            6
221            sage: f=4*x^2*y^2*z^3
222            sage: f.total_degree()
223            7
224            sage: f=99*x^6*y^3*z^9
225            sage: f.total_degree()
226            18
227            sage: f=x*y^3*z^6+3*x^2
228            sage: f.total_degree()
229            10
230            sage: f=z^3+8*x^4*y^5*z
231            sage: f.total_degree()
232            10
233            sage: f=z^9+10*x^4+y^8*x^2
234            sage: f.total_degree()
235            10
236        """
237        return self.degree()
238
239    def monomial_coefficient(self, mon):
240        """
241        Return the coefficient of the monomial mon in self, where mon
242        must have the same parent as self.
243
244        INPUT:
245            mon -- a monomial
246
247        OUTPUT:
248            ring element
249
250        EXAMPLE:
251            sage: x, y = MPolynomialRing(RationalField(), 2, names = ['x','y']).gens()
252            sage: f = y^2 - x^9 - 7*x + 5*x*y
253            sage: f.monomial_coefficient(y^2)
254            1
255            sage: f.monomial_coefficient(x*y)
256            5
257            sage: f.monomial_coefficient(x^9)
258            -1
259            sage: f.monomial_coefficient(x^10)
260            0
261        """
262        if not (isinstance(mon, MPolynomial) and mon.parent() == self.parent() and mon.is_monomial()):
263            raise TypeError, "mon (=%s) must be a monomial in the parent of self."%mon
264        R = self.parent().base_ring()
265        return R(self.element().monomial_coefficient(mon.element().dict()))
266
267
268    def coefficient(self, mon):
269        """
270        Return the coefficient of mon in self, where mon must have the
271        same parent as self.  The coefficient is defined as follows.
272        If f is this polynomial, then the coefficient is the sum T/mon
273        where the sum is over terms T in f that are exactly divisible
274        by mon.
275
276        INPUT:
277            mon -- a monomial
278
279        OUTPUT:
280            element of the parent of self
281
282        EXAMPLE:
283            sage: x, y = MPolynomialRing(RationalField(), 2, names = ['x','y']).gens()
284            sage: f = y^2 - x^9 - 7*x + 5*x*y
285            sage: f.coefficient(y)
286            5*x
287            sage: f = y - x^9*y - 7*x + 5*x*y
288            sage: f.coefficient(y)
289            1 + 5*x - x^9
290        """
291        if mon == 1:
292            mon = self.parent().gen(0)**0
293        if not (isinstance(mon, MPolynomial) and mon.parent() == self.parent() and mon.is_monomial()):
294            raise TypeError, "mon (=%s) must be a monomial in the parent of self."%mon
295        R = self.parent()
296        return R(self.element().coefficient(mon.element().dict()))
297
298    def is_unit(self):
299        """
300        Return True if self is a unit.
301
302        EXAMPLES:
303            sage: R = PolynomialRing(IntegerRing(), 2, ['x','y']); x,y = R.gens()
304            sage: (x+y).is_unit()
305            False
306            sage: R(0).is_unit()
307            False
308            sage: R(-1).is_unit()
309            True
310            sage: R(-1 + x).is_unit()
311            False
312            sage: R(2).is_unit()
313            False
314        """
315        d = self.element().dict()
316        k = d.keys()
317        if len(k) != 1:
318            return False
319        k = k[0]
320        if k != tuple([0]*self.parent().ngens()):
321            return False
322        return bool(d[k].is_unit())
323
324    def inverse_of_unit(self):
325        d = self.element().dict()
326        k = d.keys()
327        if len(k) != 1:
328            raise ArithmeticError, "is not a unit"
329        k = k[0]
330        if k != tuple([0]*self.parent().ngens()):
331            raise ArithmeticError, "is not a unit"
332        return ~d[k]
333
334    def is_homogeneous(self):
335        """
336        Return True if self is a homogeneous polynomial.
337
338        EXAMPLES:
339            sage: x, y = MPolynomialRing(RationalField(), 2, names=['x', 'y']).gens()
340            sage: (x+y).is_homogeneous()
341            True
342            sage: (x.parent()(0)).is_homogeneous()
343            True
344            sage: (x+y^2).is_homogeneous()
345            False
346            sage: (x^2 + y^2).is_homogeneous()
347            True
348            sage: (x^2 + y^2*x).is_homogeneous()
349            False
350            sage: (x^2*y + y^2*x).is_homogeneous()
351            True
352        """
353        return self.element().is_homogeneous()
354
355    def homogenize(self, var="h"):
356        """
357        Return self is self is homogeneous.  Otherwise return a homogeneous
358        polynomial in one more variable such that setting that variable
359        equal to 1 yields self.
360
361        INPUT:
362            var -- string (default: "h"); a variable name for the new variable
363                   to be added in when homogenizing.
364
365        OUTPUT:
366            a multivariate polynomial
367
368        EXAMPLES:
369            sage: x,y = MPolynomialRing(RationalField(),2,['x','y']).gens()
370            sage: f = x^2 + y + 1 + 5*x*y^10
371            sage: g = f.homogenize('z'); g
372            z^11 + y*z^10 + 5*x*y^10 + x^2*z^9
373            sage: g.parent()
374            Polynomial Ring in x, y, z over Rational Field
375        """
376        if self.is_homogeneous():
377            return self
378        X = self.element().homogenize()
379        R = self.parent()
380        S = multi_polynomial_ring.MPolynomialRing(
381                        R.base_ring(),
382                        R.ngens() + 1,
383                        names=R.variable_names() + (var,),
384                        order = R.term_order())
385        return S(X)
386
387    def is_monomial(self):
388        return len(self.element().dict().keys()) == 1
389
390
391    ############################################################################
392    # Some functions added by Martin Albrecht <malb@informatik.uni-bremen.de>
393    # (and documented by W. Stein)
394    ############################################################################
395
396    def fix(self, fixed):
397        """
398        Fixes some given variables in a given multivariate polynomial and
399        returns the changed multivariate polynomials. The polynomial
400        itself is not affected.  The variable,value pairs for fixing are
401        to be provided as dictionary of the form {variable:value}.
402
403        This is a special case of evaluating the polynomial with some of
404        the variables constants and the others the original variables, but
405        should be much faster.
406
407        INPUT:
408            fixed -- dict with variable:value pairs
409
410        OUTPUT:
411            new MPolynomial
412
413        EXAMPLES:
414            sage: x, y = MPolynomialRing(ZZ,2,'xy').gens()
415            sage: f = x^2 + y + x^2*y^2 + 5
416            sage: f((5,y))
417            30 + y + 25*y^2
418            sage: f.fix({x:5})
419            30 + y + 25*y^2
420        """
421        variables = list(self.parent().gens())
422        for i in range(0,len(variables)):
423            if fixed.has_key(variables[i]):
424                variables[i] = fixed[variables[i]]
425        return self(tuple(variables))
426
427
428    def monomials(self):
429        """
430        Returns a list of all monomials which occure in this
431        multivariate polynomial.
432
433        OUTPUT:
434            list of MPolynomials representing Monomials
435
436        EXAMPLES:
437            sage: x, y = MPolynomialRing(ZZ,2,'xy').gens()
438            sage: f = 3*x^2 - 2*y + 7*x^2*y^2 + 5
439            sage: f.monomials()
440            [y, x^2, 1, x^2*y^2]
441        """
442        x = self.parent().gens()
443        monomials = []
444        for m in self.element().dict().keys():
445            monomials.append(misc.mul([ x[i]**m[i] for i in range(self.parent().ngens()) ]))
446        return monomials
447
448    def constant_coefficient(self):
449        """
450        Return the constant coefficient of this multivariate polynomial.
451
452        EXAMPLES:
453            sage: x, y = ZZ['x,y'].gens()
454            sage: f = 3*x^2 - 2*y + 7*x^2*y^2 + 5
455            sage: f.constant_coefficient()
456            5
457            sage: f = 3*x^2
458            sage: f.constant_coefficient()
459            0
460        """
461        v = (0,)*int(self.parent().ngens())
462        d = self.element().dict()
463        try:
464            return d[v]
465        except KeyError:
466            return self.parent().base_ring()(0)
467
468    def is_univariate(self):
469        """
470        Returns True if this multivariate polynomial is univariate and False otherwise.
471
472        EXAMPLES:
473            sage: x, y = MPolynomialRing(ZZ,2,'xy').gens()
474            sage: f = 3*x^2 - 2*y + 7*x^2*y^2 + 5
475            sage: f.is_univariate()
476            False
477            sage: g = f.fix({x:10}); g
478            305 - 2*y + 700*y^2
479            sage: g.is_univariate()
480            True
481        """
482        degrees = self._MPolynomial__element.dict().keys()
483        try:
484            ngens = len(degrees[0]) # number of generators
485        except:
486            return True        # zero
487        nmons = len(degrees) # number of monomials
488        from sage.matrix.all import MatrixSpace
489        from sage.rings.all import Z
491        all_one = MatrixSpace(Z,nmons,1)([1]*nmons)
492
493        found = 0
494        # use matrix multiplication to add all corresponding variables occurences
495        #
496        # keys of dictionary are exponent tuples so the keys() list is:
497        #
498        # [(2,0,0), |
499        #  (1,1,0), | addition done by transposing and multiplication with (1,1,...)^T
500        #  (0,1,0)]\/
501        # ---------
502        #   3,2,0  if more than one is not zero -> not univariate
503        for elem in (degrees*all_one).list():
504            if(elem!=0):
505                if(found!=0):
506                    return False
507                else:
508                    found = elem
509        return True
510
511
512    def univariate_polynomial(self, R=None):
513        """
514        Returns a univariate polynomial associated to this
515        multivariate polynomial.
516
517        INPUT:
518            R -- (defualt: None) PolynomialRing
519
520        If this polynomial is not in at most one variable, then a
521        ValueError exception is raised.  This is checked using the
522        is_univariate() method.  The new Polynomial is over the same
523        base ring as the given MPolynomial and in the variable 'x' if
524        no ring 'ring' is provided.
525
526        EXAMPLES:
527            sage: x, y = MPolynomialRing(ZZ,2,'xy').gens()
528            sage: f = 3*x^2 - 2*y + 7*x^2*y^2 + 5
529            sage: f.univariate_polynomial()
530            Traceback (most recent call last):
531            ...
532            ValueError: polynomial (=5 - 2*y + 3*x^2 + 7*x^2*y^2) must involve at most one variable
533            sage: g = f.fix({x:10}); g
534            305 - 2*y + 700*y^2
535            sage: g.univariate_polynomial ()
536            700*x^2 - 2*x + 305
537            sage: g.univariate_polynomial(PolynomialRing(QQ,'z'))
538            700*z^2 - 2*z + 305
539            sage: R = PolynomialRing(QQ,'w')
540            sage: R(g)
541            700*w^2 - 2*w + 305
542        """
543        if not self.is_univariate():
544            raise ValueError, "polynomial (=%s) must involve at most one variable"%self
545
546        #construct ring if none
547        if R == None:
548            R =  polynomial_ring.PolynomialRing(self.base_ring(),'x')
549
550        monomial_coefficients = self._MPolynomial__element.dict()
551
552        if( not self.is_constant() ):
553            var_idx = self.__variable_indices()[0] #variable
554        else:
555            var_idx = 0; #constant
556            if( len(monomial_coefficients.keys())==0 ):
557                return 0
558
559        #construct list
560        lookup = [int(0),]*len( monomial_coefficients.keys()[0] )
561        coefficients = []
562        for degree in range( 0 , max([ m[var_idx] for m in monomial_coefficients.keys() ])+1 ):
563            lookup[var_idx]=int(degree);
564            try:
565                coefficients.append( monomial_coefficients[ tuple(lookup) ] ) #if we find something, add the coefficient
566            except KeyError:
567                coefficients.append( 0 ) #else add zero
568
569        #construct polynomial
570        return R(coefficients)
571
572    def __variable_indices(self):
573        m_coefficients = self._MPolynomial__element.dict()
574        variable_dict = dict()
575
576        #get variables
577        for exponents in m_coefficients.keys():
578            for idx in range( 0 , len(exponents) ):
579                if( exponents[idx] != 0 ):
580                    variable_dict[idx] = 1
581
582        return variable_dict.keys()
583
584    def variables(self):
585        """
586        Returns the list of variables occuring in this polynomial.
587
588        EXAMPLES:
589            sage: x, y = MPolynomialRing(ZZ,2,'xy').gens()
590            sage: f = 3*x^2 - 2*y + 7*x^2*y^2 + 5
591            sage: f.variables()
592            [x, y]
593            sage: g = f.fix({x:10}); g
594            305 - 2*y + 700*y^2
595            sage: g.variables()
596            [y]
597        """
598        return [self.parent().gen(index) for index in self.__variable_indices() ]
599
600
601    def variable(self,i):
602        """
603        Returns $i$-th variable occuring in this polynomial.
604
605        EXAMPLES:
606            sage: x, y = MPolynomialRing(ZZ,2,'xy').gens()
607            sage: f = 3*x^2 - 2*y + 7*x^2*y^2 + 5
608            sage: f.variable(0)
609            x
610            sage: f.variable(1)
611            y
612        """
613        return self.variables()[int(i)]
614
615    def nvariables(self):
616        """
617        Number of variables in this polynomial
618
619        EXAMPLES:
620            sage: x, y = MPolynomialRing(ZZ, 2,'xy').gens()
621            sage: f = 3*x^2 - 2*y + 7*x^2*y^2 + 5
622            sage: f.nvariables ()
623            2
624            sage: g = f.fix({x:10}); g
625            305 - 2*y + 700*y^2
626            sage: g.nvariables ()
627            1
628        """
629        return len(self.__variable_indices())
630
631    def is_constant(self):
632        """
633        True if polynomial is constant, and False otherwise.
634
635        EXAMPLES:
636            sage: x, y = MPolynomialRing(ZZ,2,'xy').gens()
637            sage: f = 3*x^2 - 2*y + 7*x^2*y^2 + 5
638            sage: f.is_constant()
639            False
640            sage: g = 10*x^0
641            sage: g.is_constant()
642            True
643        """
644        if( len(self.__variable_indices()) == 0 ):
645            return True
646        else:
647            return False
648
649
650    ############################################################################
651    # END: Some functions added by Martin Albrecht <malb@informatik.uni-bremen.de>
652    ############################################################################
653
654
655###############################################################
656# Useful for some geometry code.
657###############################################################
658
659def degree_lowest_rational_function(r,x):
660    r"""
661    INPUT:
662        r -- a multivariate rational function
663        x -- a multivariate polynomial ring generator x
664
665    OUTPUT:
666        integer -- the degree of r in x and its "leading"
667                   (in the x-adic sense) coefficient.
668
669    EXAMPLES:
670        sage: R1 = MPolynomialRing(FiniteField(5), 3, names = ["a","b","c"])
671        sage: F = FractionField(R1)
672        sage: a,b,c = R1.gens()
673        sage: f = 3*a*b^2*c^3+4*a*b*c
674        sage: g = a^2*b*c^2+2*a^2*b^4*c^7
675
676    Consider the quotient $f/g = \frac{4 + 3 bc^{2}}{ac + 2 ab^{3}c^{6}}$ (note
677    the cancellation).
678        sage: r = f/g; r
679        (4 + 3*b*c^2)/(a*c + 2*a*b^3*c^6)
680        sage: degree_lowest_rational_function(r,a)
681              (-1, 4)
682        sage: degree_lowest_rational_function(r,b)
683              (0, 4)
684        sage: degree_lowest_rational_function(r,c)
685              (-1, 4)
686    """
687    from fraction_field import FractionField
688    R = r.parent()
689    F = FractionField(R)
690    r = F(r)
691    if r == 0:
692        return (0, F(0))
693    L = x.element().dict().keys()[0]
694    for ix in range(len(L)):
695        if L[ix] != 0:
696            break
697    f = r.numerator()
698    g = r.denominator()
699    M = f.element().dict()
700    numtermsf = len(M)
701    degreesf = [M.keys()[j][ix] for j in range(numtermsf)]
702    lowdegf = min(degreesf)
703    cf = M[M.keys()[degreesf.index(lowdegf)]] ## constant coeff of lowest degree term
704    M = g.element().dict()
705    numtermsg = len(M)
706    degreesg = [M.keys()[j][ix] for j in range(numtermsg)]
707    lowdegg = min(degreesg)
708    cg = M[M.keys()[degreesg.index(lowdegg)]] ## constant coeff of lowest degree term
709    return (lowdegf-lowdegg,cf/cg)
710
711
712
713################################################
714class MPolynomial_singular_repr(MPolynomial_polydict):
715    """
716    Multivariate polynomials that are representable in Singular.
717    """
718    def __floordiv__(self,right):
719        """
720        Quotient of division of self by other.  This is denoted //.
721        """
722        Q, _ = self.quo_rem(right)
723        return Q
724
725
726    def _singular_(self, singular=singular):
727        """
728        Return corresponding Singular polynomial.
729
730        EXAMPLES:
731            sage: R = PolynomialRing(GF(7), 2, ['x','y'])
732            sage: x, y = R.gens()
733            sage: f = (x^3 + 2*y^2*x)^7; f
734            2*x^7*y^14 + x^21
735            sage: h = f._singular_(); h
736            x^21+2*x^7*y^14
737            sage: R(h)
738            2*x^7*y^14 + x^21
739            sage: R(h^20) == f^20
740            True
741        """
742        self.parent()._singular_(singular).set_ring()
743        try:
744            if self.__singular.parent() is singular:
745                return self.__singular
746        except AttributeError:
747            pass
748        self.__singular = singular(str(self))
749        return self.__singular
750
751    def factor(self):
752        r"""
753        Compute the irreducible factorization of this polynomial.
754
755        ALGORITHM: Use Singular.
756
757        EXAMPLES:
758            sage: x, y = PolynomialRing(QQ, 2, ['x','y']).gens()
759            sage: f = (x^3 + 2*y^2*x) * (x^2 + x + 1); f
760            2*x*y^2 + 2*x^2*y^2 + x^3 + 2*x^3*y^2 + x^4 + x^5
761            sage: F = f.factor()
762            sage: F
763            x * (2*y^2 + x^2) * (1 + x + x^2)
764
765        Next we factor the same polynomial, but over the finite field of order $3$.
766
767            sage: x, y = PolynomialRing(GF(3), 2, ['x','y']).gens()
768            sage: f = (x^3 + 2*y^2*x) * (x^2 + x + 1); f
769            2*x*y^2 + 2*x^2*y^2 + x^3 + 2*x^3*y^2 + x^4 + x^5
770            sage: F = f.factor()
771            sage: F
772            2 * x * (2 + x)^2 * (y + x) * (y + 2*x)
773
774        Next we factor a larger product involving many variables.
775            sage:
776        """
777        R = self.parent()
778        S = self._singular_().factorize()
779        factors = S[1]
780        exponents = S[2]
781        v = [(R(factors[i+1]), integer.Integer(exponents[i+1])) \
782                        for i in range(len(factors))]
783        v.sort()
784        for i in range(len(v)):
785            if str(v[i][0]) == '1':
786                del v[i]
787                break
788        F = Factorization(v)
789        F.sort()
790        return F
791
792    def gcd(self, f):
793        """
794        Compute the greatest common divisor of this polynomial and f.
795
796        ALGORITHM: Use Singular.
797
798        EXAMPLES:
799            sage: x, y = PolynomialRing(RationalField(), 2, ['x','y']).gens()
800            sage: f = (x^3 + 2*y^2*x)^2
801            sage: g = x^2*y^2
802            sage: f.gcd(g)
803            x^2
804        """
805        if not isinstance(f, MPolynomial) and self.parent() is f.parent():
806            raise TypeError, "self (=%s) and f (=%s) must have the same parent"%(self, f)
807        return self.parent()(self._singular_().gcd(f._singular_()))
808
809    def quo_rem(self, right):
810        if not isinstance(right, MPolynomial) or right.parent() != self.parent():
811            right = self.parent()(right)
812        R = self.parent()
813        X = self._singular_().division(right._singular_())
814        return R(X[1]), R(X[2])
Note: See TracBrowser for help on using the repository browser.