source: sage/categories/pushout.py @ 6689:a41950b6ab70

Revision 6689:a41950b6ab70, 23.0 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

massive merge and some bug fixes.
Line 
1from functor import Functor
2from category_types import *
3
4# TODO, think through the rankings, and override pushout where necessary.
5
6class ConstructionFunctor(Functor):
7    def __mul__(self, other):
8        if not isinstance(self, ConstructionFunctor) and not isinstance(other, ConstructionFunctor):
9            raise TypeError, "Non-constructive product"
10        return CompositConstructionFunctor(other, self)
11       
12    def pushout(self, other):
13        if self.rank > other.rank:
14            return self * other
15        else:
16            return other * self
17           
18    def __cmp__(self, other):
19        """
20        Equality here means that they are mathematically equivalent, though they may have specific implementation data.
21        See the \code{merge} function.
22        """
23        return cmp(type(self), type(other))
24       
25    def __str__(self):
26        s = str(type(self))
27        import re
28        return re.sub("<.*'.*\.([^.]*)'>", "\\1", s)
29       
30    def __repr__(self):
31        return str(self)
32       
33    def merge(self, other):
34        if self == other:
35            return self
36        else:
37            return None
38           
39    def commutes(self, other):
40        return False
41       
42class CompositConstructionFunctor(ConstructionFunctor):
43    def __init__(self, first, second):
44        Functor.__init__(self, first.domain(), second.codomain())
45        self._first = first
46        self._second = second
47
48    def __call__(self, R):
49        return self._second(self._first(R))
50
51    def __cmp__(self, other):
52        c = cmp(self._first, other._first)
53        if c == 0:
54            c = cmp(self._second, other._second)
55        return c
56   
57    def __str__(self):
58        return "%s(%s)" % (self._second, self._first)
59       
60class IdentityConstructionFunctor(ConstructionFunctor):
61    def __init__(self):
62        Functor.__init__(self, Sets(), Sets())
63        self.rank = -100
64    def __call__(self, R):
65        return R
66    def __mul__(self, other):
67        if isinstance(self, IdentityConstructionFunctor):
68            return other
69        else:
70            return self
71
72class PolynomialFunctor(ConstructionFunctor):
73    def __init__(self, var, multi_variate=False):
74        Functor.__init__(self, Rings(), Rings())
75        self.var = var
76        self.multi_variate = multi_variate
77        self.rank = 9
78    def __call__(self, R):
79        from sage.rings.polynomial.polynomial_ring import PolynomialRing, is_PolynomialRing
80        from sage.rings.polynomial.multi_polynomial_ring_generic import is_MPolynomialRing
81        if self.multi_variate and (is_MPolynomialRing(R) or is_PolynomialRing(R)):
82            return PolynomialRing(R.base_ring(), (list(R.variable_names()) + [self.var]))
83        else:
84            return PolynomialRing(R, self.var)
85    def __cmp__(self, other):
86        c = cmp(type(self), type(other))
87        if c == 0:
88            c = cmp(self.var, other.var)
89        return c
90    def merge(self, other):
91        if self == other:
92            return PolynomialFunctor(self.var, (self.multi_variate or other.multi_variate))
93        else:
94            return None
95#    def __str__(self):
96#        return "Poly(%s)" % self.var
97       
98class MatrixFunctor(ConstructionFunctor):
99    def __init__(self, nrows, ncols, is_sparse=False):
100#        if nrows == ncols:
101#            Functor.__init__(self, Rings(), RingModules()) # takes a basering
102#        else:
103#            Functor.__init__(self, Rings(), MatrixAlgebras()) # takes a basering
104        Functor.__init__(self, Rings(), Rings())
105        self.nrows = nrows
106        self.ncols = ncols
107        self.is_sparse = is_sparse
108        self.rank = 10
109    def __call__(self, R):
110        from sage.matrix.matrix_space import MatrixSpace
111        return MatrixSpace(R, self.nrows, self.ncols, sparse=self.is_sparse)
112    def __cmp__(self, other):
113        c = cmp(type(self), type(other))
114        if c == 0:
115            c = cmp((self.nrows, self.ncols), (other.nrows, other.ncols))
116        return c
117    def merge(self, other):
118        if self != other:
119            return None
120        else:
121            return MatrixFunctor(self.nrows, self.ncols, self.is_sparse and other.is_sparse)
122       
123class VectorFunctor(ConstructionFunctor):
124    def __init__(self, n, is_sparse=False, inner_product_matrix=None):
125#        if nrows == ncols:
126#            Functor.__init__(self, Rings(), RingModules()) # takes a basering
127#        else:
128#            Functor.__init__(self, Rings(), MatrixAlgebras()) # takes a basering
129        Functor.__init__(self, Rings(), Rings())
130        self.n = n
131        self.is_sparse = is_sparse
132        self.inner_product_matrix = inner_product_matrix
133        self.rank = 10 # ranking of functor, not rank of module
134    def __call__(self, R):
135        from sage.modules.free_module import FreeModule
136        return FreeModule(R, self.n, sparse=self.is_sparse, inner_product_matrix=self.inner_product_matrix)
137    def __cmp__(self, other):
138        c = cmp(type(self), type(other))
139        if c == 0:
140            c = cmp(self.n, other.n)
141        return c
142    def merge(self, other):
143        if self != other:
144            return None
145        else:
146            return VectorFunctor(self.n, self.is_sparse and other.is_sparse)
147       
148class SubspaceFunctor(ConstructionFunctor):
149    def __init__(self, basis):
150        self.basis = basis
151        self.rank = 11 # ranking of functor, not rank of module
152    def __call__(self, ambient):
153        return ambient.span_of_basis(self.basis)
154    def __cmp__(self, other):
155        c = cmp(type(self), type(other))
156        if c == 0:
157            c = cmp(self.basis, other.basis)
158        return c
159    def merge(self, other):
160        if isinstance(other, SubspaceFunctor):
161            return SubspaceFunctor(self.basis + other.basis) # TODO: remove linear dependancies
162        else:
163            return None
164
165       
166class FractionField(ConstructionFunctor):
167    def __init__(self):
168        Functor.__init__(self, Rings(), Fields())
169        self.rank = 5
170    def __call__(self, R):
171        return R.fraction_field()
172       
173class LocalizationFunctor(ConstructionFunctor):
174    def __init__(self, t):
175        Functor.__init__(self, Rings(), Rings())
176        self.t = t
177        self.rank = 6
178    def __call__(self, R):
179        return R.localize(t)
180    def __cmp__(self, other):
181        c = cmp(type(self), type(other))
182        if c == 0:
183            c = cmp(self.t, other.t)
184        return c
185       
186class CompletionFunctor(ConstructionFunctor):
187    def __init__(self, p, prec, extras=None):
188        Functor.__init__(self, Rings(), Rings())
189        self.p = p
190        self.prec = prec
191        self.extras = extras
192        self.rank = 4
193    def __call__(self, R):
194        return R.completion(self.p, self.prec, self.extras)
195    def __cmp__(self, other):
196        c = cmp(type(self), type(other))
197        if c == 0:
198            c = cmp(self.p, other.p)
199        return c
200    def merge(self, other):
201        if self.p == other.p:
202            if self.prec == other.prec:
203                extras = self.extras.copy()
204                extras.update(other.extras)
205                return CompletionFunctor(self.p, self.prec, extras)
206            elif self.prec < other.prec:
207                return self
208            else: # self.prec > other.prec
209                return other
210        else:
211            return None
212       
213class QuotientFunctor(ConstructionFunctor):
214    def __init__(self, I):
215        Functor.__init__(self, Rings(), Rings()) # much more general...
216        self.I = I
217        self.rank = 7
218    def __call__(self, R):
219        I = self.I
220        if I.ring() != R:
221            I.base_extend(R)
222        return R.quo(I)
223    def __cmp__(self, other):
224        c = cmp(type(self), type(other))
225        if c == 0:
226            c = cmp(self.I, other.I)
227        return c
228    def merge(self, other):
229        if self == other:
230            return self
231        try:
232            gcd = self.I + other.I
233        except (TypeError, NotImplementedError):
234            return None
235        if gcd.is_trivial() and not gcd.is_zero():
236            # quotient by gcd would result in the trivial ring/group/...
237            # Rather than create the zero ring, we claim they can't be merged
238            # TODO: Perhaps this should be detected at a higher level...
239            raise TypeError, "Trivial quotient intersection."
240        return QuotientFunctor(gcd)
241
242class AlgebraicExtensionFunctor(ConstructionFunctor):
243    def __init__(self, poly, name, elt=None):
244        Functor.__init__(self, Rings(), Rings())
245        self.poly = poly
246        self.name = name
247        self.elt = elt
248        self.rank = 3
249    def __call__(self, R):
250        return R.extension(self.poly, self.name)
251    def __cmp__(self, other):
252        c = cmp(type(self), type(other))
253        if c == 0:
254            c = cmp(self.poly, other.poly)
255        return c
256       
257def BlackBoxConstructionFunctor(ConstructionFunctor):
258    def __init__(self, box):
259        self.box = box
260        self.rank = 100
261    def __call__(self, R):
262        return box(R)
263    def __cmp__(self, other):
264        return self.box == other.box
265       
266       
267def pushout(R, S):
268    """
269    Given a pair of Objects R and S, try and construct a
270    reasonable object $Y$ and return maps such that
271    cannonically $R \leftarrow Y \rightarrow S$.
272   
273    ALGORITHM:
274       This incorperates the idea of functors discussed SAGE Days 4.
275       Every object $R$ can be viewed as an initial object and
276       a series of functors (e.g. polynomial, quotient, extension,
277       completion, vector/matrix, etc.) Call the series of
278       increasingly-simple rings (with the associated functors)
279       the "tower" of $R$. The \code{construction} method is used to
280       create the tower.
281       
282       Given two objects $R$ and $S$, try and find a common initial
283       object $Z$. If the towers of $R$ and $S$ meet, let $Z$ be their
284       join. Otherwise, see if the top of one coerces naturally into
285       the other.
286       
287       Now we have an initial object and two \emph{ordered} lists of
288       functors to apply. We wish to merge these in an unambiguous order,
289       popping elements off the top of one or the other tower as we
290       apply them to $Z$.
291       
292       - If the functors are distinct types, there is an absolute ordering
293           given by the rank attribute. Use this.
294       - Otherwise:
295          - If the tops are equal, we (try to) merge them.
296          - If \emph{exactly} one occurs lower in the other tower
297              we may unambiguously apply the other (hoping for a later merge).
298          - If the tops commute, we can apply either first.
299          - Otherwise fail due to ambiguity.
300             
301    EXAMPLES:
302        Here our "towers" are $R = Complete_7(Frac(\Z)$ and $Frac(Poly_x(\Z))$, which give us $Frac(Poly_x(Complete_7(Frac(\Z)))$
303            sage: from sage.categories.pushout import pushout
304            sage: pushout(Qp(7), Frac(ZZ['x']))
305            Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20
306           
307        Note we get the same thing with
308            sage: pushout(Zp(7), Frac(QQ['x']))
309            Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20
310            sage: pushout(Zp(7)['x'], Frac(QQ['x']))
311            Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20           
312
313        Note that polynomial variable ordering must be unambiguously determined.
314            sage: pushout(ZZ['x,y,z'], QQ['w,z,t'])
315            Traceback (most recent call last):
316            ...
317            TypeError: Ambiguous Base Extension
318            sage: pushout(ZZ['x,y,z'], QQ['w,x,z,t'])
319            Multivariate Polynomial Ring in w, x, y, z, t over Rational Field
320
321        Some other examples
322            sage: pushout(Zp(7)['y'], Frac(QQ['t'])['x,y,z'])
323            Multivariate Polynomial Ring in x, y, z over Fraction Field of Univariate Polynomial Ring in t over 7-adic Field with capped relative precision 20
324            sage: pushout(ZZ['x,y,z'], Frac(ZZ['x'])['y'])
325            Multivariate Polynomial Ring in y, z over Fraction Field of Univariate Polynomial Ring in x over Integer Ring
326            sage: pushout(MatrixSpace(RDF, 2, 2), Frac(ZZ['x']))
327            Full MatrixSpace of 2 by 2 dense matrices over Fraction Field of Univariate Polynomial Ring in x over Real Double Field
328            sage: pushout(ZZ, MatrixSpace(ZZ[['x']], 3, 3))
329            Full MatrixSpace of 3 by 3 dense matrices over Power Series Ring in x over Integer Ring
330            sage: pushout(QQ['x,y'], ZZ[['x']])
331            Univariate Polynomial Ring in y over Power Series Ring in x over Rational Field
332            sage: pushout(Frac(ZZ['x']), QQ[['x']])
333            Laurent Series Ring in x over Rational Field
334
335    AUTHORS:
336       -- Robert Bradshaw
337    """
338    if R == S:
339        return R
340   
341    if isinstance(R, type):
342        R = type_to_parent(R)
343
344    if isinstance(S, type):
345        S = type_to_parent(S)
346
347    R_tower = construction_tower(R)
348    S_tower = construction_tower(S)
349    Rs = [c[1] for c in R_tower]
350    Ss = [c[1] for c in S_tower]
351   
352    if R in Ss:
353        return S
354    elif S in Rs:
355        return R
356       
357#    print Rs
358#    print Ss
359   
360    if R_tower[-1][1] in Ss:
361      Rs, Ss = Ss, Rs
362      R_tower, S_tower = S_tower, R_tower
363     
364    # look for join
365    if Ss[-1] in Rs:
366        if Rs[-1] == Ss[-1]:
367            while Rs[-1] == Ss[-1]:
368                Rs.pop()
369                Z = Ss.pop()
370        else:
371            Rs = Rs[:Rs.index(Ss[-1])]
372            Z = Ss.pop()
373           
374    # look for topmost coercion
375    elif S.has_coerce_map_from(Rs[-1]):
376        while not Ss[-1].has_coerce_map_from(Rs[-1]):
377            Ss.pop()
378        while len(Rs) > 0 and Ss[-1].has_coerce_map_from(Rs[-1]):
379            Rs.pop()
380        Z = Ss.pop()
381       
382    elif R.has_coerce_map_from(Ss[-1]):
383        while not Rs[-1].has_coerce_map_from(Ss[-1]):
384            Rs.pop()
385        while len(Ss) > 0 and Rs[-1].has_coerce_map_from(Ss[-1]):
386            Ss.pop()
387        Z = Rs.pop()
388       
389    else:
390        raise TypeError, "No common base"
391   
392    # Rc is a list of functors from Z to R and Sc is a list of functors from Z to S
393    Rc = [c[0] for c in R_tower[1:len(Rs)+1]]
394    Sc = [c[0] for c in S_tower[1:len(Ss)+1]]
395   
396    while len(Rc) > 0 or len(Sc) > 0:
397        # print Z
398        # if we are out of functors in either tower, there is no ambiguity
399        if len(Sc) == 0:
400            c = Rc.pop()
401            Z = c(Z)
402        elif len(Rc) == 0:
403            c = Sc.pop()
404            Z = c(Z)
405        # if one of the functors has lower rank, do it first
406        elif Rc[-1].rank < Sc[-1].rank:
407            c = Rc.pop()
408            Z = c(Z)
409        elif Sc[-1].rank < Rc[-1].rank:
410            c = Sc.pop()
411            Z = c(Z)
412        else:
413            # the ranks are the same, so things are a bit subtler
414            if Rc[-1] == Sc[-1]:
415                # If they are indeed the same operation, we only do it once.
416                # The \code{merge} function here takes into account non-mathematical
417                # distinctions (e.g. single vs. multivariate polynomials)
418                cR = Rc.pop()
419                cS = Sc.pop()
420                c = cR.merge(cS) or cS.merge(cR)
421                if c:
422                    Z = c(Z)
423                else:
424                    raise TypeError, "Incompatable Base Extension %r, %r (on %r, %r)" % (R, S, cR, cS)
425            else:
426                # Now we look ahead to see if either top functor is
427                # applied later on in the other tower.
428                # If this is the case for exactly one of them, we unambiguously
429                # postpone that operation, but if both then we abort.
430                if Rc[-1] in Sc:
431                    if Sc[-1] in Rc:
432                        raise TypeError, "Ambiguous Base Extension"
433                    else:
434                        c = Sc.pop()
435                        Z = c(Z)
436                elif Sc[-1] in Rc:
437                    c = Rc.pop();
438                    Z = c(Z)
439                # If, perchance, the two functors commute, then we may do them in any order.
440                elif Rc[-1].commutes(Sc[-1]):
441                    c = Rc.pop()
442                    Z = c(Z)
443                    c = Sc.pop()
444                    Z = c(Z)
445                else:
446                    # try and merge (default merge is failure for unequal functors)
447                    cR = Rc.pop()
448                    cS = Sc.pop()
449                    c = cR.merge(cS) or cS.merge(cR)
450                    if c is not None:
451                        Z = c(Z)
452                    else:
453                        # Otherwise, we cannot proceed.
454                        raise TypeError, "Ambiguous Base Extension"
455    return Z
456   
457
458   
459def pushout_lattice(R, S):
460    """
461    Given a pair of Objects R and S, try and construct a
462    reasonable object $Y$ and return maps such that
463    cannonically $R \leftarrow Y \rightarrow S$.
464   
465    ALGORITHM:
466       This is based on the model that arose from much discussion at SAGE Days 4.
467       Going up the tower of constructions of $R$ and $S$ (e.g. the reals
468       come from the rationals come from the integers) try and find a
469       common parent, and then try and fill in a lattice with these
470       two towers as sides with the top as the common ancestor and
471       the bottom will be the desired ring.
472       
473       See the code for a specific worked-out example.
474       
475    EXAMPLES:
476        sage: from sage.categories.pushout import pushout_lattice
477        sage: A, B = pushout_lattice(Qp(7), Frac(ZZ['x']))
478        sage: A.codomain()
479        Fraction Field of Univariate Polynomial Ring in x over 7-adic Field with capped relative precision 20
480        sage: A.codomain() is B.codomain()
481        True
482        sage: A, B = pushout_lattice(ZZ, MatrixSpace(ZZ[['x']], 3, 3))
483        sage: B
484        Identity endomorphism of Full MatrixSpace of 3 by 3 dense matrices over Power Series Ring in x over Integer Ring
485       
486    AUTHOR:
487       -- Robert Bradshaw
488    """
489    R_tower = construction_tower(R)
490    S_tower = construction_tower(S)
491    Rs = [c[1] for c in R_tower]
492    Ss = [c[1] for c in S_tower]
493   
494    # look for common ancestor
495    start = None
496    for Z in Rs:
497        if Z in Ss:
498            start = Z
499    if start is None:
500        # Should I test for a map between the tops of the towers?
501        # Or, if they're both not ZZ, is it hopeless?
502        return None
503       
504    # truncate at common ancestor
505    R_tower = list(reversed(R_tower[:Rs.index(start)+1]))
506    S_tower = list(reversed(S_tower[:Ss.index(start)+1]))
507    Rs = [c[1] for c in R_tower] # the list of objects
508    Ss = [c[1] for c in S_tower] 
509    Rc = [c[0] for c in R_tower] # the list of functors
510    Sc = [c[0] for c in S_tower]
511   
512    # Here we try and construct a 2-dimensional lattice as follows.
513    # Suppose our towers are Z -> Q -> Qp = R and Z -> Z[t] -> Frac(Z[t]) = S
514    lattice = {}
515    # First we fill in the sides
516    #
517    #         Z
518    #       /   \
519    #      Q    Z[t]
520    #    /         \
521    #   Qp       Frac(Z[t])
522    #
523    for i in range(len(Rs)):
524        lattice[i,0] = Rs[i]
525    for j in range(len(Ss)):
526        lattice[0,j] = Ss[j]
527
528    # Now we attempt to fill in the center, one (diagonal) row at a time,
529    # one commuting square at a time.
530    #
531    #          Z
532    #       /    \
533    #      Q     Z[t]
534    #    /   \  /    \
535    #   Qp   Q[t]   Frac(Z[t])
536    #    \   /
537    #    Qp[t]
538    #
539    # There is always exactly one "correct" path/order in which to apply operations
540    # from the top to the bottom. In our example, this is down the far left side.
541    # We keep track of which that is by clearing out Rc and Sc as we go along.
542    #
543    # Note that when applying the functors in the correct order, base extension
544    # is not needed (though it may occur in the resulting morphisms).
545    #
546    for i in range(len(Rc)-1):
547        for j in range(len(Sc)-1):
548            try:
549                if lattice[i,j+1] == lattice[i+1,j]:
550                    # In this case we have R <- S -> R
551                    # We don't want to perform the operation twice
552                    # and all subsequent squares will come from objects
553                    # where the operation was already performed (either
554                    # to the left or right)
555                    Rc[i] = Sc[j] = None # IdentityConstructionFunctor()
556                    lattice[i+1,j+1] = lattice[i,j+1]
557                elif Rc[i] is None and Sc[j] is None:
558                    lattice[i+1,j+1] = lattice[i,j+1]
559                elif Rc[i] is None:
560                    lattice[i+1,j+1] = Sc[j](lattice[i+1,j])
561                elif Sc[j] is None:
562                    lattice[i+1,j+1] = Rc[i](lattice[i,j+1])
563                else:
564                    # For now, we just look at the rank.
565                    # TODO: be more sophisticated and query the functors themselves
566                    if Rc[i].rank < Sc[j].rank:
567                        lattice[i+1,j+1] = Sc[j](lattice[i+1,j])
568                        Rc[i] = None # force us to use pre-applied Rc[i]
569                    else:
570                        lattice[i+1,j+1] = Rc[i](lattice[i,j+1])
571                        Sc[j] = None # force us to use pre-applied Sc[i]
572            except (AttributeError, NameError):
573                print i, j
574                pp(lattice)
575                raise TypeError, "%s does not support %s" % (lattice[i,j], 'F')
576           
577    # If we are successful, we should have something that looks like this.
578    #
579    #          Z
580    #       /    \
581    #      Q     Z[t]
582    #    /   \  /    \
583    #   Qp   Q[t]   Frac(Z[t])
584    #    \   /  \    /
585    #    Qp[t]  Frac(Q[t])
586    #      \      /
587    #     Frac(Qp[t])
588    #
589    R_loc = len(Rs)-1
590    S_loc = len(Ss)-1
591   
592    # Find the composition coercion morphisms along the bottom left...
593    if S_loc > 0:
594        R_map = lattice[R_loc,1].coerce_map_from(R)
595        for i in range(1, S_loc):
596            map = lattice[R_loc, i+1].coerce_map_from(lattice[R_loc, i]) # The functor used is implicit here, should it be?
597            R_map = map * R_map
598    else:
599        R_map = R.coerce_map_from(R) # id
600   
601    # ... and bottom right
602    if R_loc > 0:
603        S_map = lattice[1, S_loc].coerce_map_from(S)
604        for i in range(1, R_loc):
605            map = lattice[i+1, S_loc].coerce_map_from(lattice[i, S_loc])
606            S_map = map * S_map
607    else:
608        S_map = S.coerce_map_from(S) # id
609           
610    return R_map, S_map
611   
612   
613def pp(lattice):
614    """
615    Used in debugging to print the current lattice.
616    """
617    for i in range(100):
618        for j in range(100):
619            try:
620                R = lattice[i,j]
621                print i, j, R
622            except KeyError:
623                break
624
625def construction_tower(R):
626    tower = [(None, R)]
627    c = R.construction()
628    while c is not None:
629        f, R = c
630        if not isinstance(f, ConstructionFunctor):
631            f = BlackBoxConstructionFunctor(f)
632        tower.append((f,R))
633        c = R.construction()
634    return tower
635
636
637
638def type_to_parent(P):
639    import sage.rings.all
640    if P in [int, long]:
641        return sage.rings.all.ZZ
642    elif P is float:
643        return sage.rings.all.RDF
644    elif P is complex:
645        return sage.rings.all.CDF
646    else:
647        raise TypeError, "Not a scalar type."
Note: See TracBrowser for help on using the repository browser.