## "Fossies" - the Fresh Open Source Software Archive

### Member "NZMATH-1.2.0/nzmath/poly/multiutil.py" (19 Nov 2012, 24881 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 "multiutil.py" see the Fossies "Dox" file reference documentation.

```    1 """
2 Multivariate polynomial extenders.
3 """
4
5 from __future__ import division
6 import nzmath.rational as rational
7 import nzmath.ring as ring
8 import nzmath.poly.termorder as termorder
9 import nzmath.poly.ring as poly_ring
10 import nzmath.poly.uniutil as uniutil
11 import nzmath.poly.multivar as multivar
12 import nzmath.poly.ratfunc as ratfunc
13
14
15 _MIXIN_MSG = "%s is mix-in"
16
17
18 class OrderProvider (object):
19     """
20     OrderProvider provides order and related operations.
21     """
22     def __init__(self, order):
23         """
24         Do not instantiate OrderProvider.
25         This initializer should be called from descendant:
26           OrderProvider.__init__(self, order)
27         """
28         if type(self) is OrderProvider:
29             raise NotImplementedError(_MIXIN_MSG % self.__class__.__name__)
30         self.order = order
31
32
33 class NestProvider (object):
34     """
35     Provide nest/unnest pair to convert a multivar polynomial to a
36     univar polynomial of polynomial coefficient and opposite
37     direction.
38     """
40         """
42         among all total degree one terms).
43
44         The leading term varies with term orders, so does the result.
45         The term order can be specified via the attribute 'order'.
46         """
47         if hasattr(self, 'order'):
48             order = self.order
49             pivot, pvar = (1,) + (0,)*(self.number_of_variables - 1), 0
50             for var in range(1, self.number_of_variables):
51                 vindex = (0,)*var + (1,) + (0,)*(self.number_of_variables - var - 1)
52                 if order.cmp(pivot, vindex) < 0:
53                     pivot, pvar = vindex, var
54         else:
55             pvar = 0
56         return pvar
57
58     def nest(self, outer, coeffring):
59         """
60         Nest the polynomial by extracting outer variable at the given
61         position.
62         """
63         combined = {}
64         if self.number_of_variables == 2:
65             itercoeff = lambda coeff: [(i[0], c) for (i, c) in coeff]
66             poly = uniutil.polynomial
67             polyring = poly_ring.PolynomialRing.getInstance(coeffring)
68         elif self.number_of_variables >= 3:
69             itercoeff = lambda coeff: coeff
70             poly = self.__class__
71             polyring = poly_ring.PolynomialRing.getInstance(coeffring, self.number_of_variables - 1)
72         else:
73             raise TypeError("number of variable is not multiple")
74         for index, coeff in self.combine_similar_terms(outer):
75             combined[index] = poly(itercoeff(coeff), coeffring=coeffring)
76         return uniutil.polynomial(combined, coeffring=polyring)
77
78     def unnest(self, q, outer, coeffring):
79         """
80         Unnest the nested polynomial q by inserting outer variable at
81         the given position.
82         """
83         q_coeff = {}
84         for d, cpoly in q:
85             for inner_d, inner_c in cpoly:
86                 if isinstance(inner_d, (int, long)):
87                     inner_d = [inner_d]
88                 else:
89                     inner_d = list(inner_d)
90                 inner_d.insert(outer, d)
91                 q_coeff[tuple(inner_d)] = inner_c
92         return self.__class__(q_coeff, coeffring=coeffring)
93
94
95 class RingElementProvider (ring.CommutativeRingElement):
96     """
97     Provides interfaces for ring.CommutativeRingElement.
98     """
99     def __init__(self):
100         """
101         Do not instantiate RingElementProvider.
102         This initializer should be called from descendant:
103           RingElementProvider.__init__(self)
104         """
105         if type(self) is RingElementProvider:
106             raise NotImplementedError(_MIXIN_MSG % self.__class__.__name__)
107         ring.CommutativeRingElement.__init__(self)
108         self._coefficient_ring = None
109         self._ring = None
110
111     def getRing(self):
112         """
113         Return an object of a subclass of Ring, to which the element
114         belongs.
115         """
116         if self._coefficient_ring is None or self._ring is None:
117             myring = None
118             for c in self.itercoefficients():
119                 cring = ring.getRing(c)
120                 if not myring or myring != cring and myring.issubring(cring):
121                     myring = cring
122                 elif not cring.issubring(myring):
123                     myring = myring.getCommonSuperring(cring)
124             if not myring:
125                 myring = rational.theIntegerRing
126             self.set_coefficient_ring(myring)
127         return self._ring
128
129     def getCoefficientRing(self):
130         """
131         Return the coefficient ring.
132         """
133         return self._coefficient_ring
134
135     def set_coefficient_ring(self, coeffring):
136         if self._coefficient_ring is None:
137             self._coefficient_ring = coeffring
138             self._ring = poly_ring.PolynomialRing.getInstance(self._coefficient_ring, self.number_of_variables)
139
140
141 class PseudoDivisionProvider (object):
142     """
143     PseudoDivisionProvider provides pseudo divisions for multivariate
144     polynomials.  It is assumed that the coefficient ring of the
145     polynomials is a domain.
146
147     The class should be used with NestProvider, RingElementProvider.
148     """
149     def pseudo_divmod(self, other):
150         """
151         self.pseudo_divmod(other) -> (Q, R)
152
153         Q, R are polynomials such that
154         d**(deg(self) - deg(other) + 1) * self == other * Q + R,
155         w.r.t. a fixed variable, where d is the leading coefficient of
156         other.
157
158         The leading coefficient varies with term orders, so does the
159         result.  The term order can be specified via the attribute
160         'order'.
161         """
163         coeffring = self.getCoefficientRing()
164
165         s = self.nest(var, coeffring)
166         o = other.nest(var, coeffring)
167         q, r = s.pseudo_divmod(o)
168         qpoly = self.unnest(q, var, coeffring)
169         rpoly = self.unnest(r, var, coeffring)
170         return qpoly, rpoly
171
172     def pseudo_floordiv(self, other):
173         """
174         self.pseudo_floordiv(other) -> Q
175
176         Q is a polynomial such that
177         d**(deg(self) - deg(other) + 1) * self == other * Q + R,
178         where d is the leading coefficient of other and R is a
179         polynomial.
180
181         The leading coefficient varies with term orders, so does the
182         result.  The term order can be specified via the attribute
183         'order'.
184         """
186         coeffring = self.getCoefficientRing()
187
188         s = self.nest(var, coeffring)
189         o = other.nest(var, coeffring)
190         q = s.pseudo_floordiv(o)
191         return self.unnest(q, var, coeffring)
192
193     def pseudo_mod(self, other):
194         """
195         self.pseudo_mod(other) -> R
196
197         R is a polynomial such that
198         d**(deg(self) - deg(other) + 1) * self == other * Q + R,
199         where d is the leading coefficient of other and Q a
200         polynomial.
201
202         The leading coefficient varies with term orders, so does the
203         result.  The term order can be specified via the attribute
204         'order'.
205         """
207         coeffring = self.getCoefficientRing()
208
209         s = self.nest(var, coeffring)
210         o = other.nest(var, coeffring)
211         r = s.pseudo_mod(o)
212         return self.unnest(r, var, coeffring)
213
214     def __truediv__(self, other):
215         """
216         self / other
217
218         The result is a rational function.
219         """
220         return ratfunc.RationalFunction(self, other)
221
222     def exact_division(self, other):
223         """
224         Return quotient of exact division.
225         """
226         coeffring = self.getCoefficientRing()
227         if other in coeffring:
228             new_coeffs = []
229             keep_ring = True
230             for i, c in self:
231                 ratio = c / other
232                 if keep_ring and ratio not in coeffring:
233                     keep_ring = False
234                     new_coeffring = ratio.getRing()
235                 new_coeffs.append((i, ratio))
236             if keep_ring:
237                 return self.__class__(new_coeffs, coeffring=coeffring)
238             else:
239                 return self.__class__(new_coeffs, coeffring=new_coeffring)
240
242         coeffring = self.getCoefficientRing()
243         s = self.nest(var, coeffring)
244         o = other.nest(var, coeffring)
245         q = s.exact_division(o)
246         return self.unnest(q, var, coeffring)
247
248
249 class GcdProvider (object):
250     """
251     Provides greatest common divisor for multivariate polynomial.
252
253     The class should be used with NestProvider, RingElementProvider.
254     """
255     def gcd(self, other):
256         """
257         Return gcd.
258         The nested polynomials' gcd is used.
259         """
261         coeffring = self.getCoefficientRing()
262         s = self.nest(var, coeffring)
263         o = other.nest(var, coeffring)
264         if hasattr(s, "gcd"):
265             g = s.gcd(o)
266         elif hasattr(s, "subresultant_gcd"):
267             g = s.subresultant_gcd(o)
268         else:
269             raise TypeError("no gcd method available")
270         return self.unnest(g, var, coeffring)
271
272
273 class RingPolynomial (OrderProvider,
274                       NestProvider,
275                       multivar.BasicPolynomial,
276                       RingElementProvider):
277     """
278     General polynomial with commutative ring coefficients.
279     """
280     def __init__(self, coefficients, **kwds):
281         """
282         Initialize the polynomial.
283
284         Required argument:
285         - coefficients: initializer for polynomial coefficients
286
287         Keyword arguments should include:
288         - coeffring: domain
289         - number_of_variables: the number of variables
290         """
291         if "number_of_variables" not in kwds:
292             coefficients = dict(coefficients)
293             for i in coefficients.iterkeys():
294                 kwds["number_of_variables"] = len(i)
295                 break
296         multivar.BasicPolynomial.__init__(self, coefficients, **kwds)
297         NestProvider.__init__(self)
298         PseudoDivisionProvider.__init__(self)
299         RingElementProvider.__init__(self)
300         coeffring = None
301         if "coeffring" in kwds:
302             coeffring = kwds["coeffring"]
303         else:
304             coeffring = uniutil.init_coefficient_ring(self._coefficients)
305         if coeffring is not None:
306             self.set_coefficient_ring(coeffring)
307         else:
308             raise TypeError("argument `coeffring' is required")
309         if "order" in kwds:
310             order = kwds["order"]
311         else:
312             order = termorder.lexicographic_order
313         OrderProvider.__init__(self, order)
314
315     def getRing(self):
316         """
317         Return an object of a subclass of Ring, to which the element
318         belongs.
319         """
320         # short-cut self._ring is None case
321         return self._ring
322
323     def getCoefficientRing(self):
324         """
325         Return an object of a subclass of Ring, to which the all
326         coefficients belong.
327         """
328         # short-cut self._coefficient_ring is None case
329         return self._coefficient_ring
330
331     def __repr__(self): # debug
332         return "%s(%s)" % (self.__class__.__name__, self._coefficients)
333
335         try:
337         except (AttributeError, TypeError):
338             one = self.getRing().one
339             try:
340                 return multivar.BasicPolynomial.__add__(self, other * one)
341             except Exception:
342                 return NotImplemented
343
345         one = self.getRing().one
346         try:
347             return other * one + self
348         except Exception:
349             return NotImplemented
350
351     def __sub__(self, other):
352         try:
353             return multivar.BasicPolynomial.__sub__(self, other)
354         except (AttributeError, TypeError):
355             one = self.getRing().one
356             try:
357                 return multivar.BasicPolynomial.__sub__(self, other * one)
358             except Exception:
359                 return NotImplemented
360
361     def __rsub__(self, other):
362         one = self.getRing().one
363         try:
364             return other * one - self
365         except Exception:
366             return NotImplemented
367
368
369 class DomainPolynomial (PseudoDivisionProvider,
370                         RingPolynomial):
371     """
372     Polynomial with domain coefficients.
373     """
374     def __init__(self, coefficients, **kwds):
375         """
376         Initialize the polynomial.
377
378         - coefficients: initializer for polynomial coefficients
379         - coeffring: domain
380         """
381         RingPolynomial.__init__(self, coefficients, **kwds)
382         if not self._coefficient_ring.isdomain():
383             raise TypeError("coefficient ring has to be a domain")
384         PseudoDivisionProvider.__init__(self)
385
386
387 class UniqueFactorizationDomainPolynomial (GcdProvider,
388                                            DomainPolynomial):
389     """
390     Polynomial with unique factorization domain coefficients.
391     """
392     def __init__(self, coefficients, **kwds):
393         """
394         Initialize the polynomial.
395
396         - coefficients: initializer for polynomial coefficients
397         - coeffring: unique factorization domain
398         """
399         DomainPolynomial.__init__(self, coefficients, **kwds)
400         if not self._coefficient_ring.isufd():
401             raise TypeError("coefficient ring has to be a UFD")
402         GcdProvider.__init__(self)
403
404     def resultant(self, other, var):
405         """
406         Return resultant of two polynomials of the same ring, with
407         respect to the variable specified by its position var.
408         """
409         cring = self._coefficient_ring
410         return self.nest(var, cring).resultant(other.nest(var, cring))
411
412
413 class PolynomialRingAnonymousVariables (ring.CommutativeRing):
414     """
415     The class of multivariate polynomial ring.
416     There's no need to specify the variable names.
417     """
418
419     _instances = {}
420
421     def __init__(self, coeffring, number_of_variables):
422         if not isinstance(coeffring, ring.Ring):
423             raise TypeError("%s should not be passed as ring" % coeffring.__class__)
424         ring.CommutativeRing.__init__(self)
425         self._coefficient_ring = coeffring
426         if self._coefficient_ring.isufd():
427             self.properties.setIsufd(True)
428         if self._coefficient_ring.isnoetherian():
429             self.properties.setIsnoetherian(True)
430         elif self._coefficient_ring.isdomain() in (True, False):
431             self.properties.setIsdomain(self._coefficient_ring.isdomain())
432         self.number_of_variables = number_of_variables
433
434     def getCoefficientRing(self):
435         """
436         Return the coefficient ring.
437         """
438         return self._coefficient_ring
439
440     def getQuotientField(self):
441         """
442         getQuotientField returns the quotient field of the ring
443         if coefficient ring has its quotient field.  Otherwise,
444         an exception will be raised.
445         """
446         coefficientField = self._coefficient_ring.getQuotientField()
447         variables = ["x%d" % i for i in range(self.number_of_variables)]
448         return ratfunc.RationalFunctionField(coefficientField, variables)
449
450     def __eq__(self, other):
451         if self is other:
452             return True
453         if (isinstance(other, PolynomialRingAnonymousVariables) and
454             self._coefficient_ring == other._coefficient_ring and
455             self.number_of_variables == other.number_of_variables):
456             return True
457         return False
458
459     def __repr__(self):
460         """
461         Return 'PolynomialRingAnonymousVariables(Ring, #vars)'
462         """
463         return "%s(%s, %d)" % (self.__class__.__name__, repr(self._coefficient_ring), self.number_of_variables)
464
465     def __str__(self):
466         """
467         Return R[][]
468         """
469         return str(self._coefficient_ring) + "[]" * self.number_of_variables
470
471     def __hash__(self):
472         """
473         hash(self)
474         """
475         return (hash(self._coefficient_ring) ^ (self.number_of_variables * hash(self.__class__.__name__) + 1)) & 0x7fffffff
476
477     def __contains__(self, element):
478         """
479         `in' operator is provided for checking the element be in the
480         ring.
481         """
482         if element in self._coefficient_ring:
483             return True
484         elem_ring = ring.getRing(element)
485         if elem_ring is not None and elem_ring.issubring(self):
486             return True
487         return False
488
489     def issubring(self, other):
490         """
491         reports whether another ring contains this polynomial ring.
492         """
493         if isinstance(other, poly_ring.PolynomialRing):
494             if (self._coefficient_ring.issubring(other.getCoefficientRing()) and
495                 self.number_of_variables <= other.number_of_variables):
496                 return True
497         elif isinstance(other, poly_ring.RationalFunctionField):
498             if (len(other.vars) >= self.number_of_variables and
499                 other.coefficientField.issuperring(self._coefficient_ring)):
500                 return True
501         try:
502             return other.issuperring(self)
503         except RuntimeError:
504             # reach max recursion by calling each other
505             return False
506
507     def issuperring(self, other):
508         """
509         reports whether this polynomial ring contains another ring.
510         """
511         if self._coefficient_ring.issuperring(other):
512             return True
513         if isinstance(other, poly_ring.PolynomialRing):
514             return (self._coefficient_ring.issuperring(other.getCoefficientRing()) and
515                     self.number_of_variables >= other.number_of_variables)
516         try:
517             return other.issubring(self)
518         except RuntimeError:
519             # reach max recursion by calling each other
520             return False
521
522     def getCommonSuperring(self, other):
523         """
524         Return common superring of two rings.
525         """
526         if self.issuperring(other):
527             return self
528         elif other.issuperring(self):
529             return other
530         elif (not isinstance(other, PolynomialRingAnonymousVariables) and
531               other.issuperring(self._coefficient_ring)):
532             return self.__class__(other, self.number_of_variables)
533         try:
534             if hasattr(other, "getCommonSuperring"):
535                 return other.getCommonSuperring(self)
536         except RuntimeError:
537             # reached recursion limit by calling on each other
538             pass
539         raise TypeError("no common super ring")
540
541     def createElement(self, seed):
542         """
543         Return an element of the polynomial ring made from seed
544         overriding ring.createElement.
545         """
546         if not seed:
547             return polynomial((), coeffring=self._coefficient_ring, number_of_variables=self.number_of_variables)
548         elif seed in self._coefficient_ring:
549             return polynomial([((0,)*self.number_of_variables, seed)], coeffring=self._coefficient_ring)
550         # implementation should be replaced later
551         raise NotImplementedError("unclear which type of polynomial be chosen")
552
553     def _getOne(self):
554         "getter for one"
555         if self._one is None:
556             self._one = self.createElement(self._coefficient_ring.one)
557         return self._one
558
559     one = property(_getOne, None, None, "multiplicative unit")
560
561     def _getZero(self):
562         "getter for zero"
563         if self._zero is None:
564             self._zero = self.createElement(self._coefficient_ring.zero)
565         return self._zero
566
567     zero = property(_getZero, None, None, "additive unit")
568
569     def gcd(self, a, b):
570         """
571         Return the greatest common divisor of given polynomials.
572         The polynomials must be in the polynomial ring.
573         If the coefficient ring is a field, the result is monic.
574         """
575         if hasattr(a, "gcd"):
576             return a.gcd(b)
577         elif hasattr(a, "subresultant_gcd"):
578             return a.subresultant_gcd(b)
579         raise NotImplementedError("no gcd")
580
581     def extgcd(self, a, b):
582         """
583         Return the tuple (u, v, d): d is the greatest common divisor
584         of given polynomials, and they satisfy d = u*a + v*b. The
585         polynomials must be in the polynomial ring.  If the
586         coefficient ring is a field, the result is monic.
587         """
588         if hasattr(a, "extgcd"):
589             return a.extgcd(b)
590         raise NotImplementedError("no extgcd")
591
592     @classmethod
593     def getInstance(cls, coeffring, number_of_variables):
594         """
595         Return an instance of the class with specified coefficient ring
596         and number of variables.
597         """
598         if (coeffring, number_of_variables) not in cls._instances:
599             cls._instances[coeffring, number_of_variables] = cls(coeffring, number_of_variables)
600         return cls._instances[coeffring, number_of_variables]
601
602
603 class PolynomialIdeal (ring.Ideal):
604     """
605     Multivariate polynomial ideal.
606     """
607     def __init__(self, generators, aring):
608         """
609         Initialize a polynomial ideal.
610         """
611         ring.Ideal.__init__(self, generators, aring)
612
613     def __contains__(self, elem):
614         """
615         Return whether elem is in the ideal or not.
616         """
617         if not elem.getRing().issubring(self.ring):
618             return False
619         if self.generators == [self.ring.zero]:
620             return elem == self.ring.zero
621         return not self.reduce(elem)
622
623     def __nonzero__(self):
624         """
625         Report whether the ideal is zero ideal or not.  Of course,
626         False is for zero ideal.
627         """
628         return self.generators and self.generators != [self.ring.zero]
629
630     def __repr__(self):
631         """
632         Return repr string.
633         """
634         return "%s(%r, %r)" % (self.__class__.__name__, self.generators, self.ring)
635
636     def __str__(self):
637         """
638         Return str string.
639         """
640         return "(%s)%s" % (", ".join([str(g) for g in self.generators]), self.ring)
641
642
643 # factories
644
645 special_ring_table = {}
646
647 def polynomial(coefficients, coeffring, number_of_variables=None):
648     """
649     Return a polynomial.
650     - coefficients has to be a initializer for dict, whose keys are
651       variable indices and values are coefficients at the indices.
652     - coeffring has to be an object inheriting ring.Ring.
653     - number_of_variables has to be the number of variables.
654
655     One can override the way to choose a polynomial type from a
656     coefficient ring, by setting:
657     special_ring_table[coeffring_type] = polynomial_type
658     before the function call.
659     """
660     if type(coeffring) in special_ring_table:
661         poly_type = special_ring_table[type(coeffring)]
662     elif coeffring.isufd():
663         poly_type = UniqueFactorizationDomainPolynomial
664     elif coeffring.isdomain():
665         poly_type = DomainPolynomial
666     else:
667         poly_type = multivar.BasicPolynomial
668     if number_of_variables is None:
669         coefficients = dict(coefficients)
670         for k in coefficients:
671             number_of_variables = len(k)
672             break
673     return poly_type(coefficients, coeffring=coeffring, number_of_variables=number_of_variables)
674
675 def MultiVariableSparsePolynomial(coefficient, variable, coeffring=None):
676     """
677     MultiVariableSparsePolynomial(coefficient, variable [,coeffring])
678
679     - coefficient has to be a dictionary of form {(i1,...,ik): c}
680     - variable has to be a list of character strings.
681     - coeffring has to be, if specified, an object inheriting ring.Ring.
682
683     This function is provided for backward compatible way of defining
684     multivariate polynomial.  The variable names are ignored, but
685     their number is used.
686     """
687     if not isinstance(variable, list) or not isinstance(coefficient, dict):
688         raise ValueError("You must input MultiVariableSparsePolynomial(dict, list) but (%s, %s)." % (coefficient.__class__, variable.__class__))
689     if coeffring is None:
690         coeffring = uniutil.init_coefficient_ring(coefficient)
691     return polynomial(coefficient, coeffring=coeffring, number_of_variables=len(variable))
692
693 def prepare_indeterminates(names, ctx, coeffring=None):
694     """
695     From space separated names of indeterminates, prepare variables
696     representing the indeterminates.  The result will be stored in ctx
697     dictionary.
698
699     The variables should be prepared at once, otherwise wrong aliases
700     of variables may confuse you in later calculation.
701
702     If an optional coeffring is not given, indeterminates will be
703     initialized as integer coefficient polynomials.
704
705     Example:
706     >>> prepare_indeterminates("X Y Z", globals())
707     >>> Y
708     UniqueFactorizationDomainPolynomial({(0, 1, 0): 1})
709
710     """
711     split_names = names.split()
712     number_of_variables = len(split_names)
713     if coeffring is None:
714         coeffring = uniutil.init_coefficient_ring({1:1})
715     for i, name in enumerate(split_names):
716         e_i = tuple([0] * i + [1] + [0] * (number_of_variables - i - 1))
717         ctx[name] = polynomial({e_i: 1}, coeffring, number_of_variables)
718
```