"Fossies" - the Fresh Open Source Software Archive

Member "NZMATH-1.2.0/nzmath/poly/ring.py" (19 Nov 2012, 22988 Bytes) of package /linux/misc/old/NZMATH-1.2.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "ring.py" see the Fossies "Dox" file reference documentation.

    1 """
    2 base classes for polynomial rings and rational function fields.
    3 """
    4 
    5 from __future__ import division
    6 import nzmath.ring as ring
    7 import nzmath.poly.termorder as termorder
    8 import nzmath.poly.univar as univar
    9 import nzmath.poly.multivar as multivar
   10 
   11 
   12 class PolynomialRing(ring.CommutativeRing):
   13     """
   14     The class of uni-/multivariate polynomial ring.
   15     There's no need to specify the variable names.
   16     """
   17 
   18     _instances = {}
   19 
   20     def __init__(self, coeffring, number_of_variables=1):
   21         """
   22         PolynomialRing(coeffring)
   23         creates a polynomial ring for univariate polynomials, while
   24         PolynomialRing(coeffring, n)
   25         creates a polynomial ring for multivariate polynomials.
   26         """
   27         if not isinstance(coeffring, ring.Ring):
   28             raise TypeError("%s should not be passed as ring" % coeffring.__class__)
   29         ring.CommutativeRing.__init__(self)
   30         self._coefficient_ring = coeffring
   31         if number_of_variables == 1 and self._coefficient_ring.isfield():
   32             self.properties.setIseuclidean(True)
   33         if self._coefficient_ring.isufd():
   34             self.properties.setIsufd(True)
   35         if self._coefficient_ring.isnoetherian():
   36             self.properties.setIsnoetherian(True)
   37         elif self._coefficient_ring.isdomain() in (True, False):
   38             self.properties.setIsdomain(self._coefficient_ring.isdomain())
   39         self.number_of_variables = number_of_variables
   40 
   41     def getCoefficientRing(self):
   42         """
   43         Return the coefficient ring.
   44         """
   45         return self._coefficient_ring
   46 
   47     def getQuotientField(self):
   48         """
   49         Return the quotient field of the ring if coefficient ring has
   50         its quotient field.  Otherwise, an exception will be raised.
   51         """
   52         coefficientField = self._coefficient_ring.getQuotientField()
   53         return RationalFunctionField(coefficientField, self.number_of_variables)
   54 
   55     def __eq__(self, other):
   56         """
   57         equality test
   58         """
   59         if self is other:
   60             return True
   61         if (isinstance(other, PolynomialRing) and
   62             self._coefficient_ring == other._coefficient_ring and
   63             self.number_of_variables == other.number_of_variables):
   64             return True
   65         return False
   66 
   67     def __ne__(self, other):
   68         """
   69         not equal
   70         """
   71         return not self.__eq__(other)
   72 
   73     def __hash__(self):
   74         """
   75         hash(self)
   76         """
   77         return (hash(self._coefficient_ring) ^ (self.number_of_variables * hash(self.__class__.__name__) + 1)) & 0x7fffffff
   78 
   79     def __repr__(self):
   80         """
   81         Return 'PolynomialRing(Ring, #vars)'
   82         """
   83         if self.number_of_variables == 1:
   84             return "%s(%s)" % (self.__class__.__name__, repr(self._coefficient_ring))
   85         return "%s(%s, %d)" % (self.__class__.__name__, repr(self._coefficient_ring), self.number_of_variables)
   86 
   87     def __str__(self):
   88         """
   89         Return R[][]
   90         """
   91         return str(self._coefficient_ring) + "[]" * self.number_of_variables
   92 
   93     def __contains__(self, element):
   94         """
   95         `in' operator is provided for checking the element be in the
   96         ring.
   97         """
   98         if element in self._coefficient_ring:
   99             return True
  100         elem_ring = ring.getRing(element)
  101         if elem_ring is not None and elem_ring.issubring(self):
  102             return True
  103         return False
  104 
  105     def issubring(self, other):
  106         """
  107         reports whether another ring contains this polynomial ring.
  108         """
  109         if self is other:
  110             return True
  111         elif isinstance(other, PolynomialRing):
  112             if (self._coefficient_ring.issubring(other.getCoefficientRing()) and
  113                 self.number_of_variables <= other.number_of_variables):
  114                 return True
  115         elif other.issubring(self._coefficient_ring):
  116             return False
  117         try:
  118             return other.issuperring(self)
  119         except RuntimeError:
  120             # reach max recursion by calling each other
  121             return False
  122 
  123     def issuperring(self, other):
  124         """
  125         reports whether this polynomial ring contains another ring.
  126         """
  127         if self is other:
  128             return True
  129         elif self._coefficient_ring.issuperring(other):
  130             return True
  131         elif isinstance(other, PolynomialRing):
  132             return (self._coefficient_ring.issuperring(other.getCoefficientRing()) and
  133                     self.number_of_variables >= other.number_of_variables)
  134         try:
  135             return other.issubring(self)
  136         except RuntimeError:
  137             # reach max recursion by calling each other
  138             return False
  139 
  140     def getCommonSuperring(self, other):
  141         """
  142         Return common superring of two rings.
  143         """
  144         if self.issuperring(other):
  145             return self
  146         elif other.issuperring(self):
  147             return other
  148         elif (not isinstance(other, PolynomialRing) and
  149               other.issuperring(self._coefficient_ring)):
  150             return self.__class__(other, self.number_of_variables)
  151         try:
  152             return other.getCommonSuperring(self)
  153         except RuntimeError:
  154             # reached recursion limit by calling on each other
  155             raise TypeError("no common super ring")
  156         except AttributeError:
  157             # other doesn't have getCommonSuperring
  158             raise TypeError("%s is not a ring" % str(other))
  159 
  160     def getCharacteristic(self):
  161         """
  162         Return characteristic of the ring.
  163         """
  164         return self._coefficient_ring.getCharacteristic()
  165 
  166     def createElement(self, seed):
  167         """
  168         Return an element in the ring made from seed.
  169         """
  170         if ring.getRing(seed) == self:
  171             return seed
  172         elif not seed:
  173             return self._zero_polynomial()
  174         elif seed in self._coefficient_ring:
  175             return self._constant_polynomial(seed)
  176         else:
  177             return self._prepared_polynomial(seed)
  178 
  179     def _zero_polynomial(self):
  180         """
  181         Return the zero polynomial in the polynomial ring.
  182         """
  183         if self.number_of_variables == 1:
  184             import nzmath.poly.uniutil as uniutil
  185             return uniutil.polynomial((), self._coefficient_ring)
  186         else:
  187             import nzmath.poly.multiutil as multiutil
  188             return multiutil.polynomial((), coeffring=self._coefficient_ring, number_of_variables=self.number_of_variables)
  189 
  190     def _constant_polynomial(self, seed):
  191         """
  192         Return a constant polynomial made from a constant seed.
  193         seed should not be zero.
  194         """
  195         if self.number_of_variables == 1:
  196             import nzmath.poly.uniutil as uniutil
  197             return uniutil.polynomial({0: seed}, self._coefficient_ring)
  198         else:
  199             import nzmath.poly.multiutil as multiutil
  200             const = (0,) * self.number_of_variables
  201             return multiutil.polynomial({const: seed}, self._coefficient_ring)
  202 
  203     def _prepared_polynomial(self, preparation):
  204         """
  205         Return a polynomial from given preparation, which is suited
  206         for the first argument of uni-/multi-variable polynomials.
  207         """
  208         if self.number_of_variables == 1:
  209             import nzmath.poly.uniutil as uniutil
  210             return uniutil.polynomial(preparation, self._coefficient_ring)
  211         else:
  212             import nzmath.poly.multiutil as multiutil
  213             return multiutil.polynomial(preparation, self._coefficient_ring)
  214 
  215     def _get_one(self):
  216         "getter for one"
  217         if self._one is None:
  218             self._one = self._constant_polynomial(self._coefficient_ring.one)
  219         return self._one
  220 
  221     one = property(_get_one, None, None, "multiplicative unit")
  222 
  223     def _get_zero(self):
  224         "getter for zero"
  225         if self._zero is None:
  226             self._zero = self._zero_polynomial()
  227         return self._zero
  228 
  229     zero = property(_get_zero, None, None, "additive unit")
  230 
  231     def gcd(self, a, b):
  232         """
  233         Return the greatest common divisor of given polynomials.
  234         The polynomials must be in the polynomial ring.
  235         If the coefficient ring is a field, the result is monic.
  236         """
  237         if hasattr(a, "gcd"):
  238             return a.gcd(b)
  239         elif hasattr(a, "subresultant_gcd"):
  240             return a.subresultant_gcd(b)
  241         raise NotImplementedError("no gcd")
  242 
  243     def extgcd(self, a, b):
  244         """
  245         Return the tuple (u, v, d): d is the greatest common divisor
  246         of given polynomials, and they satisfy d = u*a + v*b. The
  247         polynomials must be in the polynomial ring.  If the
  248         coefficient ring is a field, the result is monic.
  249         """
  250         if hasattr(a, "extgcd"):
  251             return a.extgcd(b)
  252         raise NotImplementedError("no extgcd")
  253 
  254     @classmethod
  255     def getInstance(cls, coeffring, number_of_variables=1):
  256         """
  257         Return an instance of the class with specified coefficient ring
  258         and number of variables.
  259         """
  260         if (coeffring, number_of_variables) not in cls._instances:
  261             cls._instances[coeffring, number_of_variables] = cls(coeffring, number_of_variables)
  262         return cls._instances[coeffring, number_of_variables]
  263 
  264 
  265 class PolynomialIdeal(ring.Ideal):
  266     """
  267     A class to represent an ideal of univariate polynomial ring.
  268     """
  269     def __init__(self, generators, polyring):
  270         """
  271         Initialize an ideal in the given polyring (polynomial ring).
  272 
  273         generators: a generator polynomial or a list of polynomials
  274         """
  275         if type(polyring) is not PolynomialRing:
  276             raise TypeError("polyring has to be an instance of PolynomialRing")
  277         ring.Ideal.__init__(self, generators, polyring)
  278         self._normalize_generators()
  279 
  280     def __contains__(self, elem):
  281         """
  282         Return whether elem is in the ideal or not.
  283         """
  284         if not elem.getRing().issubring(self.ring):
  285             return False
  286         if self.generators == [self.ring.zero]:
  287             return elem == self.ring.zero
  288         return not self.reduce(elem)
  289 
  290     def __nonzero__(self):
  291         """
  292         Report whether the ideal is zero ideal or not.  Of course,
  293         False is for zero ideal.
  294         """
  295         return self.generators and self.generators != [self.ring.zero]
  296 
  297     def __repr__(self):
  298         """
  299         Return repr string.
  300         """
  301         return "%s(%r, %r)" % (self.__class__.__name__, self.generators, self.ring)
  302 
  303     def __str__(self):
  304         """
  305         Return str string.
  306         """
  307         return "(%s)%s" % (", ".join([termorder.ascending_order.format(g) for g in self.generators]), self.ring)
  308 
  309     def issubset(self, other):
  310         """
  311         Report whether another ideal contains this ideal.
  312         """
  313         if self is other:
  314             return True
  315         for g in self.generators:
  316             if g not in other:
  317                 return False
  318         return True
  319 
  320     def issuperset(self, other):
  321         """
  322         Report whether this ideal contains another ideal.
  323         """
  324         if self is other:
  325             return True
  326         for g in other.generators:
  327             if g not in self:
  328                 return False
  329         return True
  330 
  331     def reduce(self, element):
  332         """
  333         Reduce the given element by the ideal.  The result is an
  334         element of the class which represents the equivalent class.
  335         """
  336         order = termorder.ascending_order
  337         if isinstance(element, univar.PolynomialInterface):
  338             reduced = element
  339         else:
  340             reduced = self.ring.createElement(element)
  341         if not self:
  342             if not reduced:
  343                 reduced = self.ring.zero
  344         elif len(self.generators) == 1:
  345             g = self.generators[0]
  346             if self.ring.iseuclidean():
  347                 if isinstance(g, univar.PolynomialInterface):
  348                     reduced %= g
  349                 else: # g is element of a field
  350                     reduced = self.ring.zero
  351             elif self.ring.getCoefficientRing().iseuclidean():
  352                 # higher degree to lower degree
  353                 # subtract euclid quotient of lc * generator
  354                 if isinstance(g, univar.PolynomialInterface):
  355                     g_degree, lc = order.leading_term(g)
  356                     degree = order.degree(reduced)
  357                     for d in range(degree, g_degree - 1, -1):
  358                         q = reduced[d] // lc
  359                         reduced -= g.term_mul((d - g_degree, q))
  360                 else:
  361                     reduced = reduced.coefficients_map(lambda c: c % g)
  362         elif self.ring.getCoefficientRing().iseuclidean():
  363             # assert that the generators are sorted descending order
  364             # of degrees.
  365             for g in self.generators:
  366                 reduced = self._euclidean_reduce(reduced, g)
  367         else:
  368             raise NotImplementedError("should be implemented")
  369         return reduced
  370 
  371     def _euclidean_reduce(self, element, g):
  372         """
  373         Reduce an element of the ring by a polynomial g.
  374         The coefficient ring has to be a Euclidean domain.
  375         """
  376         order = termorder.ascending_order
  377         coeffring = self.ring.getCoefficientRing()
  378         reduced = element
  379         g_degree, g_lc = order.leading_term(g)
  380         degree, lc = order.leading_term(reduced)
  381         while degree >= g_degree:
  382             if not (lc % g_lc):
  383                 reduced -= g.term_mul((degree - g_degree, lc // g_lc))
  384             else:
  385                 u, v, common_divisor = coeffring.extgcd(lc, g_lc)
  386                 reduced = reduced.scalar_mul(u) + g.term_mul((degree - g_degree, v))
  387                 break
  388             degree, lc = order.leading_term(reduced)
  389         return reduced
  390 
  391     def _normalize_generators(self):
  392         """
  393         Normalize generators
  394         """
  395         order = termorder.ascending_order
  396         if len(self.generators) > 1 and self.ring.ispid():
  397             g = self.generators[0]
  398             for t in self.generators:
  399                 g = self.ring.gcd(g, t)
  400             self.generators = [g]
  401         elif self.ring.getCoefficientRing().iseuclidean():
  402             coeffring = self.ring.getCoefficientRing()
  403             degree = order.degree
  404             lc = order.leading_coefficient
  405             cand_stack = list(self.generators)
  406             tentative = []
  407             while cand_stack:
  408                 next = cand_stack.pop()
  409                 if not tentative:
  410                     tentative.append(next)
  411                     continue
  412                 next_degree = degree(next)
  413                 while tentative:
  414                     last = tentative.pop()
  415                     last_degree = degree(last)
  416                     if last_degree > next_degree:
  417                         cand_stack.append(last)
  418                         continue
  419                     next_lc, last_lc = lc(next), lc(last)
  420                     if last_degree == next_degree:
  421                         u, v, d = coeffring.extgcd(next_lc, last_lc)
  422                         # make new polynomial whose lc = d
  423                         head = next.scalar_mul(u) + last.scalar_mul(v)
  424                         next -= head.scalar_mul(next_lc // d)
  425                         last -= head.scalar_mul(last_lc // d)
  426                         assert degree(next) < next_degree
  427                         assert degree(last) < last_degree
  428                         cand_stack.append(head)
  429                         if next:
  430                             cand_stack.append(next)
  431                         if last:
  432                             cand_stack.append(last)
  433                         break
  434                     elif not (next_lc % last_lc):
  435                         next -= last.scalar_mul(next_lc // last_lc)
  436                         cand_stack.append(next)
  437                         break
  438                     elif last_lc % next_lc:
  439                         u, v, d = coeffring.extgcd(next_lc, last_lc)
  440                         next = next.scalar_mul(u) + last.term_mul((next_degree - last_degree, v))
  441                     tentative.append(last)
  442                     tentative.append(next)
  443                     break
  444                 else:
  445                     tentative.append(next)
  446             self.generators = tentative
  447         else:
  448             degree = order.degree
  449             # sort in descending order
  450             self.generators.sort(cmp=lambda a, b: cmp(degree(b), degree(a)))
  451 
  452 
  453 class RationalFunctionField(ring.QuotientField):
  454     """
  455     The class for rational function fields.
  456     """
  457     _instances = {}
  458 
  459     def __init__(self, field, number_of_variables):
  460         """
  461         RationalFunctionField(field, number_of_variables)
  462 
  463         field: The field of coefficients.
  464         number_of_variables: The number of variables.
  465         """
  466         if isinstance(field, ring.QuotientField):
  467             basedomain = PolynomialRing(field.basedomain, number_of_variables)
  468         else:
  469             basedomain = PolynomialRing(field, number_of_variables)
  470         ring.QuotientField.__init__(self, basedomain)
  471         self.coefficient_field = field
  472         self.number_of_variables = number_of_variables
  473 
  474     def __repr__(self):
  475         """
  476         Return 'RationalFunctionField(Field, #vars)'
  477         """
  478         return "%s(%s, %d)" % (self.__class__.__name__, repr(self.coefficient_field), self.number_of_variables)
  479 
  480     def __str__(self):
  481         """
  482         Return K()()
  483         """
  484         return str(self.coefficient_field) + "()" * self.number_of_variables
  485 
  486     def __eq__(self, other):
  487         """
  488         equality test
  489         """
  490         if self is other:
  491             return True
  492         if not isinstance(other, RationalFunctionField):
  493             return False
  494         if (self.coefficient_field == other.coefficient_field and
  495             self.number_of_variables == other.number_of_variables):
  496             return True
  497         elif isinstance(self.coefficient_field, RationalFunctionField):
  498             return self.unnest() == other
  499         elif isinstance(other.coefficient_field, RationalFunctionField):
  500             return self == other.unnest()
  501         return False
  502 
  503     def __contains__(self, element):
  504         """
  505         Return True if an element is in the field.
  506         """
  507         if ring.getRing(element).issubring(self):
  508             return True
  509         return False
  510 
  511     def __hash__(self):
  512         """
  513         Return hash corresponding to equality.
  514         """
  515         return hash(self.coefficient_field) + self.number_of_variables
  516 
  517     def getQuotientField(self):
  518         """
  519         Return the quotient field (the field itself).
  520         """
  521         return self
  522 
  523     def getCoefficientRing(self):
  524         """
  525         Return the coefficient field.
  526         This method is provided for common interface with PolynomialRing.
  527         """
  528         return self.coefficient_field
  529 
  530     def issubring(self, other):
  531         """
  532         Return True if self is a subring of the other.
  533         """
  534         if self is other:
  535             return True
  536         elif (isinstance(other, RationalFunctionField) and
  537               self.coefficient_field.issubring(other.coefficient_field) and
  538               self.number_of_variables <= other.number_of_variables):
  539             return True
  540         return False
  541 
  542     def issuperring(self, other):
  543         """
  544         Return True if self is a superring of the other.
  545         """
  546         if self is other:
  547             return True
  548         elif (isinstance(other, RationalFunctionField) and
  549               self.coefficient_field.issuperring(other.coefficient_field) and
  550               self.number_of_variables >= other.number_of_variables):
  551             return True
  552         elif self.coefficient_field.issuperring(other):
  553             return True
  554         else:
  555             try:
  556                 if self.issuperring(other.getQuotientField()):
  557                     return True
  558             except Exception:
  559                 return False
  560             return False
  561 
  562     def getCharacteristic(self):
  563         """
  564         The characteristic of a rational function field is same as of
  565         its coefficient field.
  566         """
  567         return self.coefficient_field.getCharacteristic()
  568 
  569     def getCommonSuperring(self, other):
  570         """
  571         Return common superring.
  572         """
  573         if self.issuperring(other):
  574             return self
  575         elif other.issuperring(self):
  576             return other
  577         elif isinstance(other, (PolynomialRing, RationalFunctionField)):
  578             return RationalFunctionField(self.coefficient_field.getCommonSuperring(other.getCoefficientRing()), max(self.number_of_variables, other.number_of_variables))
  579         try:
  580             return other.getCommonSuperring(self)
  581         except RuntimeError:
  582             # reached recursion limit by calling on each other
  583             raise TypeError("no common super ring")
  584         except AttributeError:
  585             # other doesn't have getCommonSuperring
  586             raise TypeError("%s is not a ring" % str(other))
  587 
  588     def unnest(self):
  589         """
  590         if self is a nested RationalFunctionField i.e. its
  591         coefficientField is also a RationalFunctionField, then the
  592         function returns one level unnested RationalFunctionField.
  593 
  594         For example:
  595         RationalFunctionField(RationalFunctionField(Q, 1), 1).unnest()
  596         returns
  597         RationalFunctionField(Q, 2).
  598         """
  599         return RationalFunctionField(self.coefficient_field.coefficient_field, self.coefficient_field.number_of_variables + self.number_of_variables)
  600 
  601     def createElement(self, *seedarg, **seedkwd):
  602         """
  603         Return an element of the field made from seed.
  604         """
  605         import nzmath.poly.ratfunc as ratfunc
  606         return ratfunc.RationalFunction(*seedarg, **seedkwd)
  607 
  608     def _get_one(self):
  609         """
  610         getter for one
  611         """
  612         if self._one is None:
  613             import nzmath.poly.ratfunc as ratfunc
  614             poly_one = self.basedomain.one
  615             self._one = ratfunc.RationalFunction(poly_one, poly_one)
  616         return self._one
  617 
  618     one = property(_get_one, None, None, "multiplicative unit.")
  619 
  620     def _get_zero(self):
  621         "getter for zero"
  622         if self._zero is None:
  623             import nzmath.poly.ratfunc as ratfunc
  624             poly_one = self.basedomain.one
  625             poly_zero = self.basedomain.zero
  626             self._zero = ratfunc.RationalFunction(poly_zero, poly_one)
  627         return self._zero
  628 
  629     zero = property(_get_zero, None, None, "additive unit.")
  630 
  631     @classmethod
  632     def getInstance(cls, coefffield, number_of_variables):
  633         """
  634         Return an instance of the class with specified coefficient ring
  635         and number of variables.
  636         """
  637         if (coefffield, number_of_variables) not in cls._instances:
  638             cls._instances[coefffield, number_of_variables] = cls(coefffield, number_of_variables)
  639         return cls._instances[coefffield, number_of_variables]