r"""
Commutative Differential Graded Algebras

An algebra is said to be *graded commutative* if it is endowed with a
grading and its multiplication satisfies the Koszul sign convention:
`yx = (-1)^{ij} xy` if `x` and `y` are homogeneous of degrees `i` and
`j`, respectively. Thus the multiplication is anticommutative for odd
degree elements, commutative otherwise. *Commutative differential
graded algebras* are graded commutative algebras endowed with a graded
differential of degree 1. These algebras can be graded over the
integers or they can be multi-graded (i.e., graded over a finite rank
free abelian group `\ZZ^n`); if multi-graded, the total degree is used
in the Koszul sign convention, and the differential must have total
degree 1.

EXAMPLES:

All of these algebras may be constructed with the function
:func:`GradedCommutativeAlgebra`. For most users, that will be the
main function of interest. See its documentation for many more
examples.

We start by constructing some graded commutative algebras. Generators
have degree 1 by default::

    sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ)
    sage: x.degree()
    1
    sage: x^2
    0
    sage: y*x
    -x*y
    sage: B.<a,b> = GradedCommutativeAlgebra(QQ, degrees = (2,3))
    sage: a.degree()
    2
    sage: b.degree()
    3

Once we have defined a graded commutative algebra, it is easy to
define a differential on it using the :meth:`GCAlgebra.cdg_algebra` method::

    sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,2))
    sage: B = A.cdg_algebra({x: x*y, y: -x*y})
    sage: B
    Commutative Differential Graded Algebra with generators ('x', 'y', 'z') in degrees (1, 1, 2) over Rational Field with differential:
        x --> x*y
        y --> -x*y
        z --> 0
    sage: B.cohomology(3)
    Free module generated by {[x*z + y*z]} over Rational Field
    sage: B.cohomology(4)
    Free module generated by {[z^2]} over Rational Field

We can also compute algebra generators for the cohomology in a range
of degrees, and in this case we compute up to degree 10::

    sage: B.cohomology_generators(10)
    {1: [x + y], 2: [z]}

AUTHORS:

- Miguel Marco, John Palmieri (2014-07): initial version
"""

# ****************************************************************************
#       Copyright (C) 2014 Miguel Marco <mmarco@unizar.es>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 2 of the License, or
# (at your option) any later version.
#                  https://www.gnu.org/licenses/
# ****************************************************************************
from __future__ import print_function, absolute_import
from six import string_types

from sage.misc.six import with_metaclass
from sage.structure.unique_representation import UniqueRepresentation
from sage.structure.sage_object import SageObject
from sage.misc.cachefunc import cached_method
from sage.misc.inherit_comparison import InheritComparisonClasscallMetaclass
from sage.misc.functional import is_odd, is_even
from sage.misc.misc_c import prod
from sage.categories.algebras import Algebras
from sage.categories.morphism import Morphism
from sage.categories.modules import Modules
from sage.categories.homset import Hom

from sage.algebras.free_algebra import FreeAlgebra
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.combinat.free_module import CombinatorialFreeModule
from sage.combinat.integer_vector_weighted import WeightedIntegerVectors
from sage.groups.additive_abelian.additive_abelian_group import AdditiveAbelianGroup
from sage.matrix.constructor import matrix
from sage.modules.free_module import VectorSpace
from sage.modules.free_module_element import vector
from sage.rings.all import ZZ
from sage.rings.homset import RingHomset_generic
from sage.rings.morphism import RingHomomorphism_im_gens
from sage.rings.polynomial.term_order import TermOrder
from sage.rings.quotient_ring import QuotientRing_nc
from sage.rings.quotient_ring_element import QuotientRingElement
from sage.misc.cachefunc import cached_function


class Differential(with_metaclass(
        InheritComparisonClasscallMetaclass, UniqueRepresentation, Morphism)):
    r"""
    Differential of a commutative graded algebra.

    INPUT:

    - ``A`` -- algebra where the differential is defined
    - ``im_gens`` -- tuple containing the image of each generator

    EXAMPLES::

        sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 2, 3))
        sage: B = A.cdg_algebra({x: x*y, y: -x*y , z: t})
        sage: B
        Commutative Differential Graded Algebra with generators ('x', 'y', 'z', 't') in degrees (1, 1, 2, 3) over Rational Field with differential:
            x --> x*y
            y --> -x*y
            z --> t
            t --> 0
        sage: B.differential()(x)
        x*y
    """
    @staticmethod
    def __classcall__(cls, A, im_gens):
        r"""
        Normalize input to ensure a unique representation.

        TESTS::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 2, 3))
            sage: d1 = A.cdg_algebra({x: x*y, y: -x*y, z: t}).differential()
            sage: d2 = A.cdg_algebra({x: x*y, z: t, y: -x*y, t: 0}).differential()
            sage: d1 is d2
            True
        """
        if isinstance(im_gens, (list, tuple)):
            im_gens = {A.gen(i): x for i, x in enumerate(im_gens)}

        R = A.cover_ring()
        I = A.defining_ideal()
        if A.base_ring().characteristic() != 2:
            squares = R.ideal([R.gen(i)**2 for i, d in enumerate(A._degrees)
                               if is_odd(d)], side='twosided')
        else:
            squares = R.ideal(0, side='twosided')

        if I != squares:
            A_free = GCAlgebra(A.base(), names=A._names, degrees=A._degrees)
            free_diff = {A_free(a): A_free(im_gens[a]) for a in im_gens}
            B = A_free.cdg_algebra(free_diff)
            IB = B.ideal([B(g) for g in I.gens()])
            BQ = GCAlgebra.quotient(B, IB)
            # We check that the differential respects the
            # relations in the quotient method, but we also have
            # to check this here, in case a GCAlgebra with
            # relations is defined first, and then a differential
            # imposed on it.
            for g in IB.gens():
                if not BQ(g.differential()).is_zero():
                    raise ValueError("The differential does not preserve the ideal")

        im_gens = {A(a): A(im_gens[a]) for a in im_gens}

        for i in im_gens:
            x = im_gens[i]
            if (not x.is_zero()
                    and (not x.is_homogeneous()
                         or total_degree(x.degree())
                         != total_degree(i.degree()) + 1)):
                raise ValueError("The given dictionary does not determine a degree 1 map")

        im_gens = tuple(im_gens.get(x, A.zero()) for x in A.gens())
        return super(Differential, cls).__classcall__(cls, A, im_gens)

    def __init__(self, A, im_gens):
        r"""
        Initialize ``self``.

        INPUT:

        - ``A`` -- algebra where the differential is defined

        - ``im_gens`` -- tuple containing the image of each generator

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ)
            sage: B = A.cdg_algebra({x: x*y, y: x*y, z: z*t, t: t*z})
            sage: [B.cohomology(i).dimension() for i in range(6)]
            [1, 2, 1, 0, 0, 0]
            sage: d = B.differential()

        We skip the category test because homsets/morphisms aren't
        proper parents/elements yet::

            sage: TestSuite(d).run(skip="_test_category")

        An error is raised if the differential `d` does not have
        degree 1 or if `d \circ d` is not zero::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,2,3))
            sage: A.cdg_algebra({a:b, b:c})
            Traceback (most recent call last):
            ...
            ValueError: The given dictionary does not determine a valid differential
        """
        self._dic_ = {A.gen(i): x for i, x in enumerate(im_gens)}
        Morphism.__init__(self, Hom(A, A, category=Modules(A.base_ring())))

        for i in A.gens():
            if not self(self(i)).is_zero():
                raise ValueError("The given dictionary does not determine a valid differential")

    def _call_(self, x):
        r"""
        Apply the differential to ``x``.

        INPUT:

        - ``x`` -- an element of the domain of this differential

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ)
            sage: B = A.cdg_algebra({x: x*y, y: x*y, z: z*t, t: t*z})
            sage: D = B.differential()
            sage: D(x*t+1/2*t*x*y) # indirect doctest
            -1/2*x*y*z*t + x*y*t + x*z*t

        Test positive characteristic::

            sage: A.<x,y> = GradedCommutativeAlgebra(GF(17), degrees=(2, 3))
            sage: B = A.cdg_algebra(differential={x:y})
            sage: B.differential()(x^17)
            0
        """
        if x.is_zero():
            return self.codomain().zero()
        res = self.codomain().zero()
        dic = x.dict()
        for key in dic:
            keyl = list(key)
            coef = dic[key]
            idx = 0
            while keyl:
                exp = keyl.pop(0)
                if exp > 0:
                    v1 = (exp * self._dic_[x.parent().gen(idx)]
                          * x.parent().gen(idx)**(exp - 1))
                    v2 = prod(x.parent().gen(i + idx + 1)**keyl[i] for i in
                              range(len(keyl)))
                    res += coef * v1 * v2
                    coef *= ((-1) ** total_degree(x.parent()._degrees[idx])
                             * x.parent().gen(idx)**exp)
                idx += 1
        return res

    def _repr_defn(self):
        r"""
        Return a string showing where ``self`` sends each generator.

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ)
            sage: B = A.cdg_algebra({x: x*y, y: x*y, z: z*t, t: t*z})
            sage: D = B.differential()
            sage: print(D._repr_defn())
            x --> x*y
            y --> x*y
            z --> z*t
            t --> -z*t
        """
        return '\n'.join("{} --> {}".format(i, self(i))
                         for i in self.domain().gens())

    def _repr_(self):
        r"""
        Return a string representation of ``self``.

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ)
            sage: D = A.differential({x: x*y, y: x*y, z: z*t, t: t*z})
            sage: D
            Differential of Graded Commutative Algebra with generators ('x', 'y', 'z', 't') in degrees (1, 1, 1, 1) over Rational Field
              Defn: x --> x*y
                    y --> x*y
                    z --> z*t
                    t --> -z*t
        """
        if self.domain() is None:
            return "Defunct morphism"

        s = "Differential of {}".format(self.domain()._base_repr())
        s += "\n  Defn: " + '\n        '.join(self._repr_defn().split('\n'))
        return s

    @cached_method
    def differential_matrix(self, n):
        r"""
        The matrix that gives the differential in degree ``n``.

        INPUT:

        - ``n`` -- degree

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(GF(5), degrees=(2, 2, 3, 4))
            sage: d = A.differential({t: x*z, x: z, y: z})
            sage: d.differential_matrix(4)
            [2 0]
            [1 1]
            [0 2]
            [1 0]
            sage: A.inject_variables()
            Defining x, y, z, t
            sage: d(t)
            x*z
            sage: d(y^2)
            2*y*z
            sage: d(x*y)
            x*z + y*z
            sage: d(x^2)
            2*x*z
        """
        A = self.domain()
        dom = A.basis(n)
        cod = A.basis(n + 1)
        cokeys = [next(iter(a.lift().dict().keys())) for a in cod]
        m = matrix(A.base_ring(), len(dom), len(cod))
        for i in range(len(dom)):
            im = self(dom[i])
            dic = im.lift().dict()
            for j in dic.keys():
                k = cokeys.index(j)
                m[i, k] = dic[j]
        m.set_immutable()
        return m

    def coboundaries(self, n):
        r"""
        The ``n``-th coboundary group of the algebra.

        This is a vector space over the base field `F`, and it is
        returned as a subspace of the vector space `F^d`, where the
        ``n``-th homogeneous component has dimension `d`.

        INPUT:

        - ``n`` -- degree

        EXAMPLES::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 2))
            sage: d = A.differential({z: x*z})
            sage: d.coboundaries(2)
            Vector space of degree 2 and dimension 0 over Rational Field
            Basis matrix:
            []
            sage: d.coboundaries(3)
            Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [1 0]
            sage: d.coboundaries(1)
            Vector space of degree 2 and dimension 0 over Rational Field
            Basis matrix:
            []

        """
        A = self.domain()
        F = A.base_ring()
        if n == 0:
            return VectorSpace(F, 0)
        if n == 1:
            V0 = VectorSpace(F, len(A.basis(1)))
            return V0.subspace([])
        M = self.differential_matrix(n - 1)
        V0 = VectorSpace(F, M.nrows())
        V1 = VectorSpace(F, M.ncols())
        mor = V0.Hom(V1)(M)
        return mor.image()

    def cocycles(self, n):
        r"""
        The ``n``-th cocycle group of the algebra.

        This is a vector space over the base field `F`, and it is
        returned as a subspace of the vector space `F^d`, where the
        ``n``-th homogeneous component has dimension `d`.

        INPUT:

        - ``n`` -- degree

        EXAMPLES::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 2))
            sage: d = A.differential({z: x*z})
            sage: d.cocycles(2)
            Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [1 0]
        """
        A = self.domain()
        F = A.base_ring()
        if n == 0:
            return VectorSpace(F, 1)
        M = self.differential_matrix(n)
        V0 = VectorSpace(F, M.nrows())
        V1 = VectorSpace(F, M.ncols())
        mor = V0.Hom(V1)(M)
        return mor.kernel()

    def cohomology_raw(self, n):
        r"""
        The ``n``-th cohomology group of ``self``.

        This is a vector space over the base ring, and it is returned
        as the quotient cocycles/coboundaries.

        INPUT:

        - ``n`` -- degree

        .. SEEALSO::

            :meth:`cohomology`

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(2, 2, 3, 4))
            sage: d = A.differential({t: x*z, x: z, y: z})
            sage: d.cohomology_raw(4)
            Vector space quotient V/W of dimension 2 over Rational Field where
            V: Vector space of degree 4 and dimension 2 over Rational Field
            Basis matrix:
            [   1    0    0   -2]
            [   0    1 -1/2   -1]
            W: Vector space of degree 4 and dimension 0 over Rational Field
            Basis matrix:
            []

        Compare to :meth:`cohomology`::

            sage: d.cohomology(4)
            Free module generated by {[x^2 - 2*t], [x*y - 1/2*y^2 - t]} over Rational Field
        """
        return self.cocycles(n).quotient(self.coboundaries(n))

    def cohomology(self, n):
        r"""
        The ``n``-th cohomology group of ``self``.

        This is a vector space over the base ring, defined as the
        quotient cocycles/coboundaries. The elements of the quotient
        are lifted to the vector space of cocycles, and this is
        described in terms of those lifts.

        INPUT:

        - ``n`` -- degree

        .. SEEALSO::

            :meth:`cohomology_raw`

        EXAMPLES::

            sage: A.<a,b,c,d,e> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 1, 1, 1))
            sage: d = A.differential({d: a*b, e: b*c})
            sage: d.cohomology(2)
            Free module generated by {[a*c], [a*d], [b*d], [c*d - a*e], [b*e], [c*e]} over Rational Field

        Compare to :meth:`cohomology_raw`::

            sage: d.cohomology_raw(2)
            Vector space quotient V/W of dimension 6 over Rational Field where
            V: Vector space of degree 10 and dimension 8 over Rational Field
            Basis matrix:
            [ 1  0  0  0  0  0  0  0  0  0]
            [ 0  1  0  0  0  0  0  0  0  0]
            [ 0  0  1  0  0  0  0  0  0  0]
            [ 0  0  0  1  0  0  0  0  0  0]
            [ 0  0  0  0  1  0  0  0  0  0]
            [ 0  0  0  0  0  1 -1  0  0  0]
            [ 0  0  0  0  0  0  0  1  0  0]
            [ 0  0  0  0  0  0  0  0  1  0]
            W: Vector space of degree 10 and dimension 2 over Rational Field
            Basis matrix:
            [1 0 0 0 0 0 0 0 0 0]
            [0 0 1 0 0 0 0 0 0 0]
        """
        H = self.cohomology_raw(n)
        H_basis_raw = [H.lift(H.basis()[i]) for i in range(H.dimension())]
        A = self.domain()
        B = A.basis(n)
        H_basis = [sum(c * b for (c, b) in zip(coeffs, B)) for coeffs in
                   H_basis_raw]
        # Put brackets around classes.
        H_basis_brackets = [CohomologyClass(b) for b in H_basis]
        return CombinatorialFreeModule(A.base_ring(), H_basis_brackets)

    def _is_nonzero(self):
        """
        Return ``True`` iff this morphism is nonzero.

        This is used by the :meth:`Morphism.__nonzero__` method, which
        in turn is used by the :func:`TestSuite` test
        ``_test_nonzero_equal``.

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 2, 3))
            sage: B = A.cdg_algebra({x: x*y, y: -x*y , z: t})
            sage: B.differential()._is_nonzero()
            True
            sage: bool(B.differential())
            True
            sage: C = A.cdg_algebra({x: 0, y: 0, z: 0})
            sage: C.differential()._is_nonzero()
            False
            sage: bool(C.differential())
            False
        """
        return any(x for x in self._dic_.values())


class Differential_multigraded(Differential):
    """
    Differential of a commutative multi-graded algebra.
    """
    def __init__(self, A, im_gens):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1, 0), (0, 1), (0, 2)))
            sage: d = A.differential({a: c})

        We skip the category test because homsets/morphisms aren't
        proper parents/elements yet::

            sage: TestSuite(d).run(skip="_test_category")
        """
        Differential.__init__(self, A, im_gens)

        # Check that the differential has a well-defined degree.
        # diff_deg = [self(x).degree() - x.degree() for x in A.gens()]
        diff_deg = []
        for x in A.gens():
            y = self(x)
            if y != 0:
                diff_deg.append(y.degree() - x.degree())
        if len(set(diff_deg)) > 1:
            raise ValueError("The differential does not have a well-defined degree")
        self._degree_of_differential = diff_deg[0]

    @cached_method
    def differential_matrix_multigraded(self, n, total=False):
        """
        The matrix that gives the differential in degree ``n``.

        .. TODO::

            Rename this to ``differential_matrix`` once inheritance,
            overriding, and cached methods work together better. See
            :trac:`17201`.

        INPUT:

        - ``n`` -- degree
        - ``total`` -- (default: ``False``) if ``True``,
          return the matrix corresponding to total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1, 0), (0, 1), (0, 2)))
            sage: d = A.differential({a: c})
            sage: d.differential_matrix_multigraded((1, 0))
            [1]
            sage: d.differential_matrix_multigraded(1, total=True)
            [0 1]
            [0 0]
            sage: d.differential_matrix_multigraded((1, 0), total=True)
            [0 1]
            [0 0]
            sage: d.differential_matrix_multigraded(1)
            [0 1]
            [0 0]
        """
        if total or n in ZZ:
            return Differential.differential_matrix(self, total_degree(n))

        A = self.domain()
        G = AdditiveAbelianGroup([0] * A._grading_rank)
        n = G(vector(n))
        dom = A.basis(n)
        cod = A.basis(n + self._degree_of_differential)
        cokeys = [next(iter(a.lift().dict().keys())) for a in cod]
        m = matrix(self.base_ring(), len(dom), len(cod))
        for i in range(len(dom)):
            im = self(dom[i])
            dic = im.lift().dict()
            for j in dic.keys():
                k = cokeys.index(j)
                m[i, k] = dic[j]
        m.set_immutable()
        return m

    def coboundaries(self, n, total=False):
        """
        The ``n``-th coboundary group of the algebra.

        This is a vector space over the base field `F`, and it is
        returned as a subspace of the vector space `F^d`, where the
        ``n``-th homogeneous component has dimension `d`.

        INPUT:

        - ``n`` -- degree
        - ``total`` (default ``False``) -- if ``True``, return the
          coboundaries in total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1, 0), (0, 1), (0, 2)))
            sage: d = A.differential({a: c})
            sage: d.coboundaries((0, 2))
            Vector space of degree 1 and dimension 1 over Rational Field
            Basis matrix:
            [1]
            sage: d.coboundaries(2)
            Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [0 1]
        """
        if total or n in ZZ:
            return Differential.coboundaries(self, total_degree(n))

        A = self.domain()
        G = AdditiveAbelianGroup([0] * A._grading_rank)
        n = G(vector(n))
        F = A.base_ring()
        if total_degree(n) == 0:
            return VectorSpace(F, 0)
        if total_degree(n) == 1:
            return VectorSpace(F, 0)
        M = self.differential_matrix_multigraded(n - self._degree_of_differential)
        V0 = VectorSpace(F, M.nrows())
        V1 = VectorSpace(F, M.ncols())
        mor = V0.Hom(V1)(M)
        return mor.image()

    def cocycles(self, n, total=False):
        r"""
        The ``n``-th cocycle group of the algebra.

        This is a vector space over the base field `F`, and it is
        returned as a subspace of the vector space `F^d`, where the
        ``n``-th homogeneous component has dimension `d`.

        INPUT:

        - ``n`` -- degree
        - ``total`` -- (default: ``False``) if ``True``, return the
          cocycles in total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1, 0), (0, 1), (0, 2)))
            sage: d = A.differential({a: c})
            sage: d.cocycles((0, 1))
            Vector space of degree 1 and dimension 1 over Rational Field
            Basis matrix:
            [1]
            sage: d.cocycles((0, 1), total=True)
            Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [0 1]
        """
        if total or n in ZZ:
            return Differential.cocycles(self, total_degree(n))

        A = self.domain()
        G = AdditiveAbelianGroup([0] * A._grading_rank)
        n = G(vector(n))
        F = A.base_ring()
        if total_degree(n) == 0:
            return VectorSpace(F, 1)
        M = self.differential_matrix_multigraded(n)
        V0 = VectorSpace(F, M.nrows())
        V1 = VectorSpace(F, M.ncols())
        mor = V0.Hom(V1)(M)
        return mor.kernel()

    def cohomology_raw(self, n, total=False):
        r"""
        The ``n``-th cohomology group of the algebra.

        This is a vector space over the base ring, and it is returned
        as the quotient cocycles/coboundaries.

        INPUT:

        - ``n`` -- degree
        - ``total`` -- (default: ``False``) if ``True``, return the
          cohomology in total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        .. SEEALSO::

            :meth:`cohomology`

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1, 0), (0, 1), (0, 2)))
            sage: d = A.differential({a: c})
            sage: d.cohomology_raw((0, 2))
            Vector space quotient V/W of dimension 0 over Rational Field where
            V: Vector space of degree 1 and dimension 1 over Rational Field
            Basis matrix:
            [1]
            W: Vector space of degree 1 and dimension 1 over Rational Field
            Basis matrix:
            [1]

            sage: d.cohomology_raw(1)
            Vector space quotient V/W of dimension 1 over Rational Field where
            V: Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [0 1]
            W: Vector space of degree 2 and dimension 0 over Rational Field
            Basis matrix:
            []
        """
        return self.cocycles(n, total).quotient(self.coboundaries(n, total))

    def cohomology(self, n, total=False):
        r"""
        The ``n``-th cohomology group of the algebra.

        This is a vector space over the base ring, defined as the
        quotient cocycles/coboundaries. The elements of the quotient
        are lifted to the vector space of cocycles, and this is
        described in terms of those lifts.

        INPUT:

        - ``n`` -- degree
        - ``total`` -- (default: ``False``) if ``True``, return the
          cohomology in total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        .. SEEALSO::

            :meth:`cohomology_raw`

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1, 0), (0, 1), (0, 2)))
            sage: d = A.differential({a: c})
            sage: d.cohomology((0, 2))
            Free module generated by {} over Rational Field

            sage: d.cohomology(1)
            Free module generated by {[b]} over Rational Field
        """
        H = self.cohomology_raw(n, total)
        H_basis_raw = [H.lift(H.basis()[i]) for i in range(H.dimension())]
        A = self.domain()
        B = A.basis(n, total)
        H_basis = [sum(c * b for (c, b) in zip(coeffs, B))
                   for coeffs in H_basis_raw]
        # Put brackets around classes.
        H_basis_brackets = [CohomologyClass(b) for b in H_basis]
        return CombinatorialFreeModule(A.base_ring(), H_basis_brackets)


###########################################################
#  Commutative graded algebras

class GCAlgebra(UniqueRepresentation, QuotientRing_nc):
    r"""
    A graded commutative algebra.

    INPUT:

    - ``base`` -- the base field

    - ``names`` -- (optional) names of the generators: a list of
      strings or a single string with the names separated by
      commas. If not specified, the generators are named "x0", "x1",
      ...

    - ``degrees`` -- (optional) a tuple or list specifying the degrees
      of the generators; if omitted, each generator is given degree
      1, and if both ``names`` and ``degrees`` are omitted, an error is
      raised.

    - ``R`` (optional, default None) -- the ring over which the
      algebra is defined: if this is specified, the algebra is defined
      to be ``R/I``.

    - ``I`` (optional, default None) -- an ideal in ``R``. It is
      should include, among other relations, the squares of the
      generators of odd degree

    As described in the module-level documentation, these are graded
    algebras for which oddly graded elements anticommute and evenly
    graded elements commute.

    The arguments ``R`` and ``I`` are primarily for use by the
    :meth:`quotient` method.

    These algebras should be graded over the integers; multi-graded
    algebras should be constructed using
    :class:`GCAlgebra_multigraded` instead.

    EXAMPLES::

        sage: A.<a,b> = GradedCommutativeAlgebra(QQ, degrees = (2, 3))
        sage: a.degree()
        2
        sage: B = A.quotient(A.ideal(a**2*b))
        sage: B
        Graded Commutative Algebra with generators ('a', 'b') in degrees (2, 3) with relations [a^2*b] over Rational Field
        sage: A.basis(7)
        [a^2*b]
        sage: B.basis(7)
        []

    Note that the function :func:`GradedCommutativeAlgebra` can also be used to
    construct these algebras.
    """
    # TODO: This should be a __classcall_private__?
    @staticmethod
    def __classcall__(cls, base, names=None, degrees=None, R=None, I=None):
        r"""
        Normalize the input for the :meth:`__init__` method and the
        unique representation.

        INPUT:

        - ``base`` -- the base ring of the algebra

        - ``names`` -- the names of the variables; by default, set to ``x1``,
          ``x2``, etc.

        - ``degrees`` -- the degrees of the generators; by default, set to 1

        - ``R`` -- an underlying `g`-algebra; only meant to be used by the
          quotient method

        - ``I`` -- a two-sided ideal in ``R``, with the desired relations;
          Only meant to be used by the quotient method

        TESTS::

            sage: A1 = GradedCommutativeAlgebra(GF(2), 'x,y', (3, 6))
            sage: A2 = GradedCommutativeAlgebra(GF(2), ['x', 'y'], [3, 6])
            sage: A1 is A2
            True

        Testing the single generator case (:trac:`25276`)::

            sage: A3.<z> = GradedCommutativeAlgebra(QQ)
            sage: z**2 == 0
            True
            sage: A4.<z> = GradedCommutativeAlgebra(QQ, degrees=[4])
            sage: z**2 == 0
            False
            sage: A5.<z> = GradedCommutativeAlgebra(GF(2))
            sage: z**2 == 0
            False
        """
        if names is None:
            if degrees is None:
                raise ValueError("You must specify names or degrees")
            else:
                n = len(degrees)
            names = tuple('x{}'.format(i) for i in range(n))
        elif isinstance(names, string_types):
            names = tuple(names.split(','))
            n = len(names)
        else:
            n = len(names)
            names = tuple(names)

        if degrees is None:
            degrees = tuple([1 for i in range(n)])
        else:
            # Deal with multigrading: convert lists and tuples to elements
            # of an additive abelian group.
            if len(degrees) > 0:
                multigrade = False
                try:
                    rank = len(list(degrees[0]))
                    G = AdditiveAbelianGroup([0] * rank)
                    degrees = [G(vector(d)) for d in degrees]
                    multigrade = True
                except TypeError:
                    # The entries of degrees are not iterables, so
                    # treat as singly-graded.
                    pass
                if multigrade:
                    if sorted(map(sum, degrees)) != list(map(sum, degrees)):
                        raise ValueError("the generators should be ordered in increased total degree")
                else:
                    if sorted(degrees) != list(degrees):
                        raise ValueError("the generators should be ordered in increasing degree")
            degrees = tuple(degrees)
        if not R or not I:
            if n > 1:
                F = FreeAlgebra(base, n, names)
            else:  # n = 1
                F = PolynomialRing(base, n, names)
            gens = F.gens()
            rels = {}
            tot_degs = [total_degree(d) for d in degrees]
            for i in range(len(gens) - 1):
                for j in range(i + 1, len(gens)):
                    rels[gens[j] * gens[i]] = ((-1)**(tot_degs[i] * tot_degs[j])
                                               * gens[i] * gens[j])
            if n > 1:
                R = F.g_algebra(rels, order=TermOrder('wdegrevlex', tot_degs))
            else:   # n = 1
                R = F.quotient(rels)
            if base.characteristic() == 2:
                I = R.ideal(0, side='twosided')
            else:
                I = R.ideal([R.gen(i)**2
                             for i in range(n) if is_odd(tot_degs[i])],
                            side='twosided')

        return super(GCAlgebra, cls).__classcall__(cls, base=base, names=names,
                                                   degrees=degrees, R=R, I=I)

    def __init__(self, base, R=None, I=None, names=None, degrees=None):
        """
        Initialize ``self``.

        INPUT:

        - ``base`` -- the base field

        - ``R`` -- (optional) the ring over which the algebra is defined

        - ``I`` -- (optional) an ideal over the corresponding `g`-algebra;
          it is meant to include, among other relations, the squares of the
          generators of odd degree

        - ``names`` -- (optional) the names of the generators; if omitted,
          this uses the names ``x0``, ``x1``, ...

        - ``degrees`` -- (optional) the degrees of the generators; if
          omitted, they are given degree 1

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ)
            sage: TestSuite(A).run()
            sage: A = GradedCommutativeAlgebra(QQ, ('x','y','z'), [2,3,4])
            sage: TestSuite(A).run()
            sage: A = GradedCommutativeAlgebra(QQ, ('x','y','z','t'), [1,2,3,4])
            sage: TestSuite(A).run()
        """
        self._degrees = tuple(degrees)
        cat = Algebras(R.base_ring()).Graded()
        QuotientRing_nc.__init__(self, R, I, names, category=cat)

    def _repr_(self):
        """
        Print representation.

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=[1, 2, 3, 4])
            sage: A
            Graded Commutative Algebra with generators ('x', 'y', 'z', 't') in degrees (1, 2, 3, 4) over Rational Field
            sage: A.quotient(A.ideal(3*x*t - 2*y*z))
            Graded Commutative Algebra with generators ('x', 'y', 'z', 't') in degrees (1, 2, 3, 4) with relations [-2*y*z + 3*x*t] over Rational Field
        """
        s = "Graded Commutative Algebra with generators {} in degrees {}".format(self._names, self._degrees)
        # Find any nontrivial relations.
        I = self.defining_ideal()
        R = self.cover_ring()
        degrees = self._degrees
        if self.base().characteristic() != 2:
            squares = [R.gen(i)**2
                       for i in range(len(degrees)) if is_odd(degrees[i])]
        else:
            squares = [R.zero()]
        relns = [g for g in I.gens() if g not in squares]
        if relns:
            s = s + " with relations {}".format(relns)
        return s + " over {}".format(self.base_ring())

    _base_repr = _repr_

    @cached_method
    def _basis_for_free_alg(self, n):
        r"""
        Basis of the associated free commutative DGA in degree ``n``.

        That is, ignore the relations when computing the basis:
        compute the basis of the free commutative DGA with generators
        in degrees given by ``self._degrees``.

        INPUT:

        - ``n`` -- integer

        OUTPUT:

        Tuple of basis elements in degree ``n``, as tuples of exponents.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,2,3))
            sage: A._basis_for_free_alg(3)
            [(0, 0, 1), (1, 1, 0)]
            sage: B = A.quotient(A.ideal(a*b, b**2+a*c))
            sage: B._basis_for_free_alg(3)
            [(0, 0, 1), (1, 1, 0)]

            sage: GradedCommutativeAlgebra(QQ, degrees=(1,1))._basis_for_free_alg(3)
            []
            sage: GradedCommutativeAlgebra(GF(2), degrees=(1,1))._basis_for_free_alg(3)
            [(0, 3), (1, 2), (2, 1), (3, 0)]

            sage: A = GradedCommutativeAlgebra(GF(2), degrees=(4,8,12))
            sage: A._basis_for_free_alg(399)
            []
        """
        if n == 0:
            return ((0,) * len(self._degrees),)
        if self.base_ring().characteristic() == 2:
            return [tuple(_) for _ in WeightedIntegerVectors(n, self._degrees)]

        even_degrees = []
        odd_degrees = []
        for a in self._degrees:
            if is_even(a):
                even_degrees.append(a)
            else:
                odd_degrees.append(a)

        if not even_degrees:  # No even generators.
            return [tuple(_)
                    for _ in exterior_algebra_basis(n, tuple(odd_degrees))]
        if not odd_degrees:  # No odd generators.
            return [tuple(_)
                    for _ in WeightedIntegerVectors(n, tuple(even_degrees))]

        # General case: both even and odd generators.
        result = []
        for dim in range(n + 1):
            # First find the even part of the basis.
            if dim == 0:
                even_result = [[0] * len(even_degrees)]
            else:
                even_result = WeightedIntegerVectors(dim, tuple(even_degrees))
            # Now find the odd part of the basis.
            for even_mono in even_result:
                deg = n - dim
                odd_result = exterior_algebra_basis(deg, tuple(odd_degrees))
                for odd_mono in odd_result:
                    temp_even = list(even_mono)
                    temp_odd = list(odd_mono)
                    mono = []
                    for a in self._degrees:
                        if is_even(a):
                            mono.append(temp_even.pop(0))
                        else:
                            mono.append(temp_odd.pop(0))
                    result.append(tuple(mono))
        return result

    def basis(self, n):
        """
        Return a basis of the ``n``-th homogeneous component of ``self``.

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(1, 2, 2, 3))
            sage: A.basis(2)
            [y, z]
            sage: A.basis(3)
            [x*y, x*z, t]
            sage: A.basis(4)
            [y^2, y*z, z^2, x*t]
            sage: A.basis(5)
            [x*y^2, x*y*z, x*z^2, y*t, z*t]
            sage: A.basis(6)
            [y^3, y^2*z, y*z^2, z^3, x*y*t, x*z*t]
        """
        free_basis = self._basis_for_free_alg(n)
        fb_reversed_entries = [list(reversed(e)) for e in free_basis]
        fb_reversed_entries.sort()
        free_basis = [tuple(reversed(e)) for e in fb_reversed_entries]
        basis = []
        for v in free_basis:
            el = prod([self.gen(i)**v[i] for i in range(len(v))])
            di = el.dict()
            if len(di) == 1:
                k, = di.keys()
                if tuple(k) == v:
                    basis.append(el)
        return basis

    def quotient(self, I, check=True):
        """
        Create the quotient of this algebra by a two-sided ideal ``I``.

        INPUT:

        - ``I`` -- a two-sided homogeneous ideal of this algebra

        - ``check`` -- (default: ``True``) if ``True``, check whether
          ``I`` is generated by homogeneous elements

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(GF(5), degrees=(2, 2, 3, 4))
            sage: I = A.ideal([x*t+z^2, x*y - t])
            sage: B = A.quotient(I)
            sage: B
            Graded Commutative Algebra with generators ('x', 'y', 'z', 't') in degrees (2, 2, 3, 4) with relations [x*t, x*y - t] over Finite Field of size 5
            sage: B(x*t)
            0
            sage: B(x*y)
            t
            sage: A.basis(7)
            [x^2*z, x*y*z, y^2*z, z*t]
            sage: B.basis(7)
            [x^2*z, y^2*z, z*t]
        """
        if check and any(not i.is_homogeneous() for i in I.gens()):
            raise ValueError("The ideal must be homogeneous")
        NCR = self.cover_ring()
        gens1 = list(self.defining_ideal().gens())
        gens2 = [i.lift() for i in I.gens()]
        gens = [g for g in gens1 + gens2 if g != NCR.zero()]
        J = NCR.ideal(gens, side='twosided')
        return GCAlgebra(self.base_ring(), self._names, self._degrees, NCR, J)

    def _coerce_map_from_(self, other):
        r"""
        Returns ``True`` if there is a coercion map from ``R`` to ``self``.

        EXAMPLES::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,2))
            sage: B = A.cdg_algebra({y:x*y, x: x*y})
            sage: A._coerce_map_from_(B)
            True
            sage: B._coerce_map_from_(A)
            True
            sage: B._coerce_map_from_(QQ)
            True
            sage: B._coerce_map_from_(GF(3))
            False
        """
        if isinstance(other, GCAlgebra):
            if self._names != other._names or self._degrees != other._degrees:
                return False
            if set(self.defining_ideal().gens()) != set(other
                                                        .defining_ideal()
                                                        .gens()):
                return False
            return self.cover_ring().has_coerce_map_from(other.cover_ring())
        return super(GCAlgebra, self)._coerce_map_from_(other)

    def _element_constructor_(self, x, coerce=True):
        r"""
        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(2, 2, 3, 4))
            sage: A({(1,3,0,1): 2, (2,2,1,2): 3})
            3*x^2*y^2*z*t^2 + 2*x*y^3*t
            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(GF(5))
            sage: A({(1,3,0,1): 2, (2,2,1,2): 3})
            0
        """
        if isinstance(x, QuotientRingElement):
            if x.parent() is self:
                return x
            x = x.lift()
        if isinstance(x, dict):
            res = self.zero()
            for i in x.keys():
                mon = prod(self.gen(j)**i[j] for j in range(len(i)))
                res += x[i] * mon
            return res
        if coerce:
            R = self.cover_ring()
            x = R(x)

        from sage.interfaces.singular import is_SingularElement
        if is_SingularElement(x):
            # self._singular_().set_ring()
            x = self.element_class(self, x.sage_poly(self.cover_ring()))
            return x

        return self.element_class(self, x)

    def _Hom_(self, B, category):
        """
        Return the homset from ``self`` to ``B`` in the category ``category``.

        INPUT:

        - ``B`` -- a graded commutative algebra
        - ``category`` -- a subcategory of graded algebras or ``None``

        EXAMPLES::

            sage: A.<x,y> = GradedCommutativeAlgebra(QQ)
            sage: B.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,2,3))
            sage: C.<d> = GradedCommutativeAlgebra(GF(17))
            sage: Hom(A,A)
            Set of Homomorphisms from Graded Commutative Algebra with generators ('x', 'y') in degrees (1, 1) over Rational Field to Graded Commutative Algebra with generators ('x', 'y') in degrees (1, 1) over Rational Field
            sage: Hom(A,B)
            Set of Homomorphisms from Graded Commutative Algebra with generators ('x', 'y') in degrees (1, 1) over Rational Field to Graded Commutative Algebra with generators ('a', 'b', 'c') in degrees (1, 2, 3) over Rational Field
            sage: Hom(A,C)
            Traceback (most recent call last):
            ...
            NotImplementedError: homomorphisms of graded commutative algebras have only been implemented when the base rings are the same
        """
        R = self.base_ring()
        # The base rings need to be checked before the categories, or
        # else the function sage.categories.homset.Hom catches the
        # TypeError and uses the wrong category (the meet of the
        # categories for self and B, which might be the category of
        # rings).
        if R != B.base_ring():
            raise NotImplementedError('homomorphisms of graded commutative '
                                      'algebras have only been implemented '
                                      'when the base rings are the same')
        cat = Algebras(R).Graded()
        if category is not None and not category.is_subcategory(cat):
            raise TypeError("{} is not a subcategory of graded algebras"
                            .format(category))
        return GCAlgebraHomset(self, B, category=category)

    def differential(self, diff):
        """
        Construct a differential on ``self``.

        INPUT:

        - ``diff`` -- a dictionary defining a differential

        The keys of the dictionary are generators of the algebra, and
        the associated values are their targets under the
        differential. Any generators which are not specified are
        assumed to have zero differential.

        EXAMPLES::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 2))
            sage: A.differential({y:x*y, x: x*y})
            Differential of Graded Commutative Algebra with generators ('x', 'y', 'z') in degrees (1, 1, 2) over Rational Field
              Defn: x --> x*y
                    y --> x*y
                    z --> 0
            sage: B.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1, 2, 2))
            sage: d = B.differential({b:a*c, c:a*c})
            sage: d(b*c)
            a*b*c + a*c^2
        """
        return Differential(self, diff)

    def cdg_algebra(self, differential):
        r"""
        Construct a differential graded commutative algebra from ``self``
        by specifying a differential.

        INPUT:

        - ``differential`` -- a dictionary defining a differential or
          a map defining a valid differential

        The keys of the dictionary are generators of the algebra, and
        the associated values are their targets under the
        differential. Any generators which are not specified are
        assumed to have zero differential. Alternatively, the
        differential can be defined using the :meth:`differential`
        method; see below for an example.

        .. SEEALSO::

            :meth:`differential`

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 1))
            sage: B = A.cdg_algebra({a: b*c, b: a*c})
            sage: B
            Commutative Differential Graded Algebra with generators ('a', 'b', 'c') in degrees (1, 1, 1) over Rational Field with differential:
                a --> b*c
                b --> a*c
                c --> 0

        Note that ``differential`` can also be a map::

            sage: d = A.differential({a: b*c, b: a*c})
            sage: d
            Differential of Graded Commutative Algebra with generators ('a', 'b', 'c') in degrees (1, 1, 1) over Rational Field
              Defn: a --> b*c
                    b --> a*c
                    c --> 0
            sage: A.cdg_algebra(d) is B
            True
        """
        return DifferentialGCAlgebra(self, differential)

    # TODO: Do we want a fully spelled out alias?
    # commutative_differential_graded_algebra = cdg_algebra

    class Element(QuotientRingElement):
        r"""
        An element of a graded commutative algebra.
        """
        def __init__(self, A, rep):
            r"""
            Initialize ``self``.

            INPUT:

            - ``parent`` -- the graded commutative algebra in which
              this element lies, viewed as a quotient `R / I`

            - ``rep`` -- a representative of the element in `R`; this is used
              as the internal representation of the element

            EXAMPLES::

                sage: B.<x,y> = GradedCommutativeAlgebra(QQ, degrees=(2, 2))
                sage: a = B({(1,1): -3, (2,5): 1/2})
                sage: a
                1/2*x^2*y^5 - 3*x*y
                sage: TestSuite(a).run()

                sage: b = x^2*y^3+2
                sage: b
                x^2*y^3 + 2
            """
            QuotientRingElement.__init__(self, A, rep)

        def degree(self, total=False):
            r"""
            The degree of this element.

            If the element is not homogeneous, this returns the
            maximum of the degrees of its monomials.

            INPUT:

            - ``total`` -- ignored, present for compatibility with the
              multi-graded case

            EXAMPLES::

                sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(1, 2, 3, 3))
                sage: el = z*t+2*x*y-y^2*z
                sage: el.degree()
                7
                sage: el.monomials()
                [y^2*z, z*t, x*y]
                sage: [i.degree() for i in el.monomials()]
                [7, 6, 3]

                sage: A(0).degree()
                Traceback (most recent call last):
                ...
                ValueError: The zero element does not have a well-defined degree
            """
            if self.is_zero():
                raise ValueError("The zero element does not have a well-defined degree")
            exps = self.lift().dict().keys()
            degrees = self.parent()._degrees
            n = self.parent().ngens()
            l = [sum(e[i] * degrees[i] for i in range(n)) for e in exps]
            return max(l)

        def is_homogeneous(self, total=False):
            r"""
            Return ``True`` if ``self`` is homogeneous and ``False`` otherwise.

            INPUT:

            - ``total`` -- boolean (default ``False``); only used in the
              multi-graded case, in which case if ``True``, check to see
              if ``self`` is homogeneous with respect to total degree

            EXAMPLES::

                sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(1, 2, 3, 3))
                sage: el = z*t + 2*x*y - y^2*z
                sage: el.degree()
                7
                sage: el.monomials()
                [y^2*z, z*t, x*y]
                sage: [i.degree() for i in el.monomials()]
                [7, 6, 3]
                sage: el.is_homogeneous()
                False
                sage: em = y^3 - 5*z*t + 3/2*x*y*t
                sage: em.is_homogeneous()
                True
                sage: em.monomials()
                [y^3, x*y*t, z*t]
                sage: [i.degree() for i in em.monomials()]
                [6, 6, 6]

            The element 0 is homogeneous, even though it doesn't have
            a well-defined degree::

                sage: A(0).is_homogeneous()
                True

            A multi-graded example::

                sage: B.<c,d> = GradedCommutativeAlgebra(QQ, degrees=((2, 0), (0, 4)))
                sage: (c^2 - 1/2 * d).is_homogeneous()
                False
                sage: (c^2 - 1/2 * d).is_homogeneous(total=True)
                True
            """
            degree = None
            for m in self.monomials():
                if degree is None:
                    degree = m.degree(total)
                else:
                    if degree != m.degree(total):
                        return False
            return True

        def homogenous_parts(self):
            r"""
            Return the homogenous parts of the element. The result is given as
            a dictionary indexed by degree.


            EXAMPLES::

                sage: A.<e1,e2,e3,e4,e5> = GradedCommutativeAlgebra(QQ)
                sage: a = e1*e3*e5-3*e2*e3*e5 + e1*e2 -2*e3 + e5
                sage: a.homogenous_parts()
                {1: -2*e3 + e5, 2: e1*e2, 3: e1*e3*e5 - 3*e2*e3*e5}
            """
            dic = self.dict()
            terms = [self.parent()({t: dic[t]}) for t in dic.keys()]
            res = {}
            for term in terms:
                deg = term.degree()
                if deg in res:
                    res[deg] += term
                else:
                    res[deg] = term
            return {i: res[i] for i in sorted(res.keys())}

        def dict(self):
            r"""
            A dictionary that determines the element.

            The keys of this dictionary are the tuples of exponents of each
            monomial, and the values are the corresponding coefficients.

            EXAMPLES::

                sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(1, 2, 2, 3))
                sage: dic = (x*y - 5*y*z + 7*x*y^2*z^3*t).dict()
                sage: sorted(dic.items())
                [((0, 1, 1, 0), -5), ((1, 1, 0, 0), 1), ((1, 2, 3, 1), 7)]
            """
            return self.lift().dict()

        def basis_coefficients(self, total=False):
            """
            Return the coefficients of this homogeneous element with
            respect to the basis in its degree.

            For example, if this is the sum of the 0th and 2nd basis
            elements, return the list ``[1, 0, 1]``.

            Raise an error if the element is not homogeneous.

            INPUT:

            - ``total`` -- boolean (default ``False``); this
              is only used in the multi-graded case, in which case if
              ``True``, it returns the coefficients with respect to
              the basis for the total degree of this element

            OUTPUT:

            A list of elements of the base field.

            EXAMPLES::

                sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(1, 2, 2, 3))
                sage: A.basis(3)
                [x*y, x*z, t]
                sage: (t + 3*x*y).basis_coefficients()
                [3, 0, 1]
                sage: (t + x).basis_coefficients()
                Traceback (most recent call last):
                ...
                ValueError: This element is not homogeneous

                sage: B.<c,d> = GradedCommutativeAlgebra(QQ, degrees=((2,0), (0,4)))
                sage: B.basis(4)
                [c^2, d]
                sage: (c^2 - 1/2 * d).basis_coefficients(total=True)
                [1, -1/2]
                sage: (c^2 - 1/2 * d).basis_coefficients()
                Traceback (most recent call last):
                ...
                ValueError: This element is not homogeneous
            """
            if not self.is_homogeneous(total):
                raise ValueError('This element is not homogeneous')

            basis = self.parent().basis(self.degree(total))
            lift = self.lift()
            return [lift.monomial_coefficient(x.lift()) for x in basis]


class GCAlgebra_multigraded(GCAlgebra):
    """
    A multi-graded commutative algebra.

    INPUT:

    - ``base`` -- the base field

    - ``degrees`` -- a tuple or list specifying the degrees of the
      generators

    - ``names`` -- (optional) names of the generators: a list of
      strings or a single string with the names separated by
      commas; if not specified, the generators are named ``x0``,
      ``x1``, ...

    - ``R`` -- (optional) the ring over which the algebra is defined

    - ``I`` -- (optional) an ideal in ``R``; it should include, among
      other relations, the squares of the generators of odd degree

    When defining such an algebra, each entry of ``degrees`` should be
    a list, tuple, or element of an additive (free) abelian
    group. Regardless of how the user specifies the degrees, Sage
    converts them to group elements.

    The arguments ``R`` and ``I`` are primarily for use by the
    :meth:`GCAlgebra.quotient` method.

    EXAMPLES::

        sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0,1), (1,1)))
        sage: A
        Graded Commutative Algebra with generators ('a', 'b', 'c') in degrees ((1, 0), (0, 1), (1, 1)) over Rational Field
        sage: a**2
        0
        sage: c.degree(total=True)
        2
        sage: c**2
        c^2
        sage: c.degree()
        (1, 1)

    Although the degree of ``c`` was defined using a Python tuple, it
    is returned as an element of an additive abelian group, and so it
    can be manipulated via arithmetic operations::

        sage: type(c.degree())
        <class 'sage.groups.additive_abelian.additive_abelian_group.AdditiveAbelianGroup_fixed_gens_with_category.element_class'>
        sage: 2 * c.degree()
        (2, 2)
        sage: (a*b).degree() == a.degree() + b.degree()
        True

    The :meth:`basis` method and the :meth:`Element.degree` method both accept
    the boolean keyword ``total``. If ``True``, use the total degree::

        sage: A.basis(2, total=True)
        [a*b, c]
        sage: c.degree(total=True)
        2
    """
    def __init__(self, base, degrees, names=None, R=None, I=None):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0,1), (1,1)))
            sage: TestSuite(A).run()
            sage: B.<w> = GradedCommutativeAlgebra(GF(2), degrees=((3,2),))
            sage: TestSuite(B).run()
            sage: C = GradedCommutativeAlgebra(GF(7), degrees=((3,2),))
            sage: TestSuite(C).run()
        """
        total_degs = [total_degree(d) for d in degrees]
        GCAlgebra.__init__(self, base, R=R, I=I, names=names, degrees=total_degs)
        self._degrees_multi = degrees
        self._grading_rank = len(list(degrees[0]))

    def _repr_(self):
        """
        Print representation.

        EXAMPLES::

            sage: GradedCommutativeAlgebra(QQ, degrees=((1,0,0), (0,0,1), (1,1,1)))
            Graded Commutative Algebra with generators ('x0', 'x1', 'x2') in degrees ((1, 0, 0), (0, 0, 1), (1, 1, 1)) over Rational Field
        """
        s = GCAlgebra._repr_(self)
        old = '{}'.format(self._degrees)
        new = '{}'.format(self._degrees_multi)
        return s.replace(old, new)

    _base_repr = _repr_

    def quotient(self, I, check=True):
        """
        Create the quotient of this algebra by a two-sided ideal ``I``.

        INPUT:

        - ``I`` -- a two-sided homogeneous ideal of this algebra

        - ``check`` -- (default: ``True``) if ``True``, check whether
          ``I`` is generated by homogeneous elements

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(GF(5), degrees=(2, 2, 3, 4))
            sage: I = A.ideal([x*t+z^2, x*y - t])
            sage: B = A.quotient(I)
            sage: B
            Graded Commutative Algebra with generators ('x', 'y', 'z', 't') in degrees (2, 2, 3, 4) with relations [x*t, x*y - t] over Finite Field of size 5
            sage: B(x*t)
            0
            sage: B(x*y)
            t
            sage: A.basis(7)
            [x^2*z, x*y*z, y^2*z, z*t]
            sage: B.basis(7)
            [x^2*z, y^2*z, z*t]
        """
        if check and any(not i.is_homogeneous() for i in I.gens()):
            raise ValueError("The ideal must be homogeneous")
        NCR = self.cover_ring()
        gens1 = list(self.defining_ideal().gens())
        gens2 = [i.lift() for i in I.gens()]
        gens = [g for g in gens1 + gens2 if g != NCR.zero()]
        J = NCR.ideal(gens, side='twosided')
        return GCAlgebra_multigraded(self.base_ring(), self._names,
                                     self._degrees_multi, NCR, J)

    def _coerce_map_from_(self, other):
        r"""
        Returns ``True`` if there is a coercion map from ``R`` to ``self``.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: B = A.cdg_algebra({a: c})
            sage: B._coerce_map_from_(A)
            True
            sage: B._coerce_map_from_(QQ)
            True
            sage: B._coerce_map_from_(GF(3))
            False
        """
        if isinstance(other, GCAlgebra_multigraded):
            if self._degrees_multi != other._degrees_multi:
                return False
        elif isinstance(other, GCAlgebra):   # Not multigraded
            return False
        return super(GCAlgebra_multigraded, self)._coerce_map_from_(other)

    def basis(self, n, total=False):
        """
        Basis in degree ``n``.

        - ``n`` -- degree or integer
        - ``total`` (optional, default False) -- if True, return the
          basis in total degree ``n``.

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(GF(2), degrees=((1,0), (0,1), (1,1)))
            sage: A.basis((1,1))
            [a*b, c]
            sage: A.basis(2, total=True)
            [a^2, a*b, b^2, c]

        Since 2 is a not a multi-index, we don't need to specify ``total=True``::

            sage: A.basis(2)
            [a^2, a*b, b^2, c]

        If ``total==True``, then ``n`` can still be a tuple, list,
        etc., and its total degree is used instead::

            sage: A.basis((1,1), total=True)
            [a^2, a*b, b^2, c]
        """
        tot_basis = GCAlgebra.basis(self, total_degree(n))
        if total or n in ZZ:
            return tot_basis
        G = AdditiveAbelianGroup([0] * self._grading_rank)
        n = G(vector(n))
        return [b for b in tot_basis if b.degree() == n]

    def differential(self, diff):
        """
        Construct a differential on ``self``.

        INPUT:

        - ``diff`` -- a dictionary defining a differential

        The keys of the dictionary are generators of the algebra, and
        the associated values are their targets under the
        differential. Any generators which are not specified are
        assumed to have zero differential.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: A.differential({a: c})
            Differential of Graded Commutative Algebra with generators ('a', 'b', 'c') in degrees ((1, 0), (0, 1), (0, 2)) over Rational Field
              Defn: a --> c
                    b --> 0
                    c --> 0
        """
        return Differential_multigraded(self, diff)

    def cdg_algebra(self, differential):
        r"""
        Construct a differential graded commutative algebra from ``self``
        by specifying a differential.

        INPUT:

        - ``differential`` -- a dictionary defining a differential or
          a map defining a valid differential

        The keys of the dictionary are generators of the algebra, and
        the associated values are their targets under the
        differential. Any generators which are not specified are
        assumed to have zero differential. Alternatively, the
        differential can be defined using the :meth:`differential`
        method; see below for an example.

        .. SEEALSO::

            :meth:`differential`

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: A.cdg_algebra({a: c})
            Commutative Differential Graded Algebra with generators ('a', 'b', 'c') in degrees ((1, 0), (0, 1), (0, 2)) over Rational Field with differential:
               a --> c
               b --> 0
               c --> 0
            sage: d = A.differential({a: c})
            sage: A.cdg_algebra(d)
            Commutative Differential Graded Algebra with generators ('a', 'b', 'c') in degrees ((1, 0), (0, 1), (0, 2)) over Rational Field with differential:
               a --> c
               b --> 0
               c --> 0
        """
        return DifferentialGCAlgebra_multigraded(self, differential)

    class Element(GCAlgebra.Element):
        def degree(self, total=False):
            """
            Return the degree of this element.

            INPUT:

            - ``total`` -- if ``True``, return the total degree, an
              integer; otherwise, return the degree as an element of
              an additive free abelian group

            If not requesting the total degree, raise an error if the
            element is not homogeneous.

            EXAMPLES::

                sage: A.<a,b,c> = GradedCommutativeAlgebra(GF(2), degrees=((1,0), (0,1), (1,1)))
                sage: (a**2*b).degree()
                (2, 1)
                sage: (a**2*b).degree(total=True)
                3
                sage: (a**2*b + c).degree()
                Traceback (most recent call last):
                ...
                ValueError: This element is not homogeneous
                sage: (a**2*b + c).degree(total=True)
                3
                sage: A(0).degree()
                Traceback (most recent call last):
                ...
                ValueError: The zero element does not have a well-defined degree
            """
            if total:
                return GCAlgebra.Element.degree(self)
            if self.is_zero():
                raise ValueError("The zero element does not have a well-defined degree")
            degrees = self.parent()._degrees_multi
            n = self.parent().ngens()
            exps = self.lift().dict().keys()
            l = [sum(exp[i] * degrees[i] for i in range(n)) for exp in exps]
            if len(set(l)) == 1:
                return l[0]
            else:
                raise ValueError('This element is not homogeneous')


###########################################################
#  Differential algebras

class DifferentialGCAlgebra(GCAlgebra):
    """
    A commutative differential graded algebra.

    INPUT:

    - ``A`` -- a graded commutative algebra; that is, an instance
      of :class:`GCAlgebra`

    - ``differential`` -- a differential

    As described in the module-level documentation, these are graded
    algebras for which oddly graded elements anticommute and evenly
    graded elements commute, and on which there is a graded
    differential of degree 1.

    These algebras should be graded over the integers; multi-graded
    algebras should be constructed using
    :class:`DifferentialGCAlgebra_multigraded` instead.

    Note that a natural way to construct these is to use the
    :func:`GradedCommutativeAlgebra` function and the
    :meth:`GCAlgebra.cdg_algebra` method.

    EXAMPLES::

        sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(2, 2, 3, 3))
        sage: A.cdg_algebra({z: x*y})
        Commutative Differential Graded Algebra with generators ('x', 'y', 'z', 't') in degrees (2, 2, 3, 3) over Rational Field with differential:
            x --> 0
            y --> 0
            z --> x*y
            t --> 0

    Alternatively, starting with :func:`GradedCommutativeAlgebra`::

        sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(2, 2, 3, 3))
        sage: A.cdg_algebra(differential={z: x*y})
        Commutative Differential Graded Algebra with generators ('x', 'y', 'z', 't') in degrees (2, 2, 3, 3) over Rational Field with differential:
            x --> 0
            y --> 0
            z --> x*y
            t --> 0

    See the function :func:`GradedCommutativeAlgebra` for more examples.
    """
    @staticmethod
    def __classcall__(cls, A, differential):
        """
        Normalize input to ensure a unique representation.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,1,1))
            sage: D1 = A.cdg_algebra({a: b*c, b: a*c})
            sage: D2 = A.cdg_algebra(D1.differential())
            sage: D1 is D2
            True
            sage: from sage.algebras.commutative_dga import DifferentialGCAlgebra
            sage: D1 is DifferentialGCAlgebra(A, {a: b*c, b: a*c, c: 0})
            True
        """
        if not isinstance(differential, Differential):
            differential = A.differential(differential)
        elif differential.parent() != A:
            differential = Differential(A, differential._dic_)
        return super(GCAlgebra, cls).__classcall__(cls, A, differential)

    def __init__(self, A, differential):
        """
        Initialize ``self``

        INPUT:

        - ``A`` -- a graded commutative algebra

        - ``differential`` -- a differential

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(2, 2, 3, 3))
            sage: D = A.cdg_algebra({z: x*y})
            sage: TestSuite(D).run()

        The degree of the differential must be 1::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,1,1))
            sage: A.cdg_algebra({a: a*b*c})
            Traceback (most recent call last):
            ...
            ValueError: The given dictionary does not determine a degree 1 map

        The differential composed with itself must be zero::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,2,3))
            sage: A.cdg_algebra({a:b, b:c})
            Traceback (most recent call last):
            ...
            ValueError: The given dictionary does not determine a valid differential
        """
        GCAlgebra.__init__(self, A.base(), names=A._names,
                           degrees=A._degrees,
                           R=A.cover_ring(),
                           I=A.defining_ideal())
        self._differential = Differential(self, differential._dic_)
        self._minimalmodels = {}
        self._numerical_invariants = {}

    def graded_commutative_algebra(self):
        """
        Return the base graded commutative algebra of ``self``.

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=(2, 2, 3, 3))
            sage: D = A.cdg_algebra({z: x*y})
            sage: D.graded_commutative_algebra() == A
            True
        """
        return GCAlgebra(self.base(), names=self._names, degrees=self._degrees,
                         R=self.cover_ring(), I=self.defining_ideal())

    def _base_repr(self):
        """
        Return the base string representation of ``self``.

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=[1, 2, 3, 4])
            sage: A.cdg_algebra({x:y, z:t})._base_repr()
            "Commutative Differential Graded Algebra with generators ('x', 'y', 'z', 't') in degrees (1, 2, 3, 4) over Rational Field"
        """
        return GCAlgebra._repr_(self).replace('Graded Commutative', 'Commutative Differential Graded')

    def _repr_(self):
        """
        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees=[1, 2, 3, 4])
            sage: A.cdg_algebra({x:y, z:t})
            Commutative Differential Graded Algebra with generators ('x', 'y', 'z', 't') in degrees (1, 2, 3, 4) over Rational Field with differential:
               x --> y
               y --> 0
               z --> t
               t --> 0
        """
        d = self._differential._repr_defn().replace('\n', '\n   ')
        return self._base_repr() + " with differential:{}".format('\n   ' + d)

    def quotient(self, I, check=True):
        """
        Create the quotient of this algebra by a two-sided ideal ``I``.

        INPUT:

        - ``I`` -- a two-sided homogeneous ideal of this algebra

        - ``check`` -- (default: ``True``) if ``True``, check whether
          ``I`` is generated by homogeneous elements

        EXAMPLES::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,2))
            sage: B = A.cdg_algebra({y:x*y, z:x*z})
            sage: B.inject_variables()
            Defining x, y, z
            sage: I = B.ideal([y*z])
            sage: C = B.quotient(I)
            sage: (y*z).differential()
            2*x*y*z
            sage: C((y*z).differential())
            0
            sage: C(y*z)
            0

        It is checked that the differential maps the ideal into itself, to make
        sure that the quotient inherits a differential structure::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,2,2))
            sage: B = A.cdg_algebra({x:y})
            sage: B.quotient(B.ideal(y*x))
            Traceback (most recent call last):
            ...
            ValueError: The differential does not preserve the ideal
            sage: B.quotient(B.ideal(x))
            Traceback (most recent call last):
            ...
            ValueError: The differential does not preserve the ideal
        """
        J = self.ideal(I)
        AQ = GCAlgebra.quotient(self, J, check)
        for g in I.gens():
            if not AQ(g.differential()).is_zero():
                raise ValueError("The differential does not preserve the ideal")
        dic = {AQ(a): AQ(a.differential()) for a in self.gens()}
        return AQ.cdg_algebra(dic)

    def differential(self, x=None):
        r"""
        The differential of ``self``.

        This returns a map, and so it may be evaluated on elements of
        this algebra.

        EXAMPLES::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,2))
            sage: B = A.cdg_algebra({y:x*y, x: y*x})
            sage: d = B.differential(); d
            Differential of Commutative Differential Graded Algebra with generators ('x', 'y', 'z') in degrees (1, 1, 2) over Rational Field
              Defn: x --> -x*y
                    y --> x*y
                    z --> 0
            sage: d(y)
            x*y
        """
        return self._differential

    def coboundaries(self, n):
        """
        The ``n``-th coboundary group of the algebra.

        This is a vector space over the base field `F`, and it is
        returned as a subspace of the vector space `F^d`, where the
        ``n``-th homogeneous component has dimension `d`.

        INPUT:

        - ``n`` -- degree

        EXAMPLES::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,2))
            sage: B = A.cdg_algebra(differential={z: x*z})
            sage: B.coboundaries(2)
            Vector space of degree 2 and dimension 0 over Rational Field
            Basis matrix:
            []
            sage: B.coboundaries(3)
            Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [1 0]
            sage: B.basis(3)
            [x*z, y*z]
        """
        return self._differential.coboundaries(n)

    def cocycles(self, n):
        """
        The ``n``-th cocycle group of the algebra.

        This is a vector space over the base field `F`, and it is
        returned as a subspace of the vector space `F^d`, where the
        ``n``-th homogeneous component has dimension `d`.

        INPUT:

        - ``n`` -- degree

        EXAMPLES::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,2))
            sage: B = A.cdg_algebra(differential={z: x*z})
            sage: B.cocycles(2)
            Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [1 0]
            sage: B.basis(2)
            [x*y, z]
        """
        return self._differential.cocycles(n)

    def cohomology_raw(self, n):
        """
        The ``n``-th cohomology group of ``self``.

        This is a vector space over the base ring, and it is returned
        as the quotient cocycles/coboundaries.

        INPUT:

        - ``n`` -- degree

        EXAMPLES::

            sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees = (2,2,3,4))
            sage: B = A.cdg_algebra({t: x*z, x: z, y: z})
            sage: B.cohomology_raw(4)
            Vector space quotient V/W of dimension 2 over Rational Field where
            V: Vector space of degree 4 and dimension 2 over Rational Field
            Basis matrix:
            [   1    0    0   -2]
            [   0    1 -1/2   -1]
            W: Vector space of degree 4 and dimension 0 over Rational Field
            Basis matrix:
            []

        Compare to :meth:`cohomology`::

            sage: B.cohomology(4)
            Free module generated by {[x^2 - 2*t], [x*y - 1/2*y^2 - t]} over Rational Field
        """
        return self._differential.cohomology_raw(n)

    def cohomology(self, n):
        """
        The ``n``-th cohomology group of ``self``.

        This is a vector space over the base ring, defined as the
        quotient cocycles/coboundaries. The elements of the quotient
        are lifted to the vector space of cocycles, and this is
        described in terms of those lifts.

        INPUT:

        - ``n`` -- degree

        EXAMPLES::

            sage: A.<a,b,c,d,e> = GradedCommutativeAlgebra(QQ, degrees=(1,1,1,1,1))
            sage: B = A.cdg_algebra({d: a*b, e: b*c})
            sage: B.cohomology(2)
            Free module generated by {[a*c], [a*d], [b*d], [c*d - a*e], [b*e], [c*e]} over Rational Field

        Compare to :meth:`cohomology_raw`::

            sage: B.cohomology_raw(2)
            Vector space quotient V/W of dimension 6 over Rational Field where
            V: Vector space of degree 10 and dimension 8 over Rational Field
            Basis matrix:
            [ 1  0  0  0  0  0  0  0  0  0]
            [ 0  1  0  0  0  0  0  0  0  0]
            [ 0  0  1  0  0  0  0  0  0  0]
            [ 0  0  0  1  0  0  0  0  0  0]
            [ 0  0  0  0  1  0  0  0  0  0]
            [ 0  0  0  0  0  1 -1  0  0  0]
            [ 0  0  0  0  0  0  0  1  0  0]
            [ 0  0  0  0  0  0  0  0  1  0]
            W: Vector space of degree 10 and dimension 2 over Rational Field
            Basis matrix:
            [1 0 0 0 0 0 0 0 0 0]
            [0 0 1 0 0 0 0 0 0 0]
        """
        return self._differential.cohomology(n)

    def cohomology_generators(self, max_degree):
        """
        Return lifts of algebra generators for cohomology in degrees at
        most ``max_degree``.

        INPUT:

        - ``max_degree`` -- integer

        OUTPUT:

        A dictionary keyed by degree, where the corresponding
        value is a list of cohomology generators in that degree.
        Actually, the elements are lifts of cohomology generators,
        which means that they lie in this differential graded
        algebra. It also means that they are only well-defined up to
        cohomology, not on the nose.

        ALGORITHM:

        Reduce a basis of the `n`'th cohomology modulo all the degree n
        products of the lower degrees cohomologys.

        EXAMPLES::

            sage: A.<a,x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2,2))
            sage: B = A.cdg_algebra(differential={y: a*x})
            sage: B.cohomology_generators(3)
            {1: [a], 2: [x], 3: [a*y]}

        The previous example has infinitely generated cohomology:
        $a y^n$ is a cohomology generator for each $n$::

            sage: B.cohomology_generators(10)
            {1: [a], 2: [x], 3: [a*y], 5: [a*y^2], 7: [a*y^3], 9: [a*y^4]}

        In contrast, the corresponding algebra in characteristic $p$
        has finitely generated cohomology::

            sage: A3.<a,x,y> = GradedCommutativeAlgebra(GF(3), degrees=(1,2,2))
            sage: B3 = A3.cdg_algebra(differential={y: a*x})
            sage: B3.cohomology_generators(20)
            {1: [a], 2: [x], 3: [a*y], 5: [a*y^2], 6: [y^3]}

        This method works with both singly graded and multi-graded algebras::

            sage: Cs.<a,b,c,d> = GradedCommutativeAlgebra(GF(2), degrees=(1,2,2,3))
            sage: Ds = Cs.cdg_algebra({a:c, b:d})
            sage: Ds.cohomology_generators(10)
            {2: [a^2], 4: [b^2]}

            sage: Cm.<a,b,c,d> = GradedCommutativeAlgebra(GF(2), degrees=((1,0), (1,1), (0,2), (0,3)))
            sage: Dm = Cm.cdg_algebra({a:c, b:d})
            sage: Dm.cohomology_generators(10)
            {2: [a^2], 4: [b^2]}

        TESTS:

        Test that coboundaries do not appear as cohomology generators::

            sage: X.<x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
            sage: acyclic = X.cdg_algebra({x: y})
            sage: acyclic.cohomology_generators(3)
            {}

        Test that redundant generators are eliminated::

            sage: A.<e1,e2,e3,e4> = GradedCommutativeAlgebra(QQ)
            sage: d = A.differential({e1:e4*e3,e2:e4*e3})
            sage: B = A.cdg_algebra(d)
            sage: B.cohomology_generators(3)
            {1: [e1 - e2, e3, e4], 2: [e1*e3, e1*e4]}

        """
        if not (max_degree in ZZ and max_degree > 0):
            raise ValueError('the given maximal degree must be a '
                             'positive integer')

        def vector_to_element(v, deg):
            """
            If an element of this algebra in degree ``deg`` is represented
            by a raw vector ``v``, convert it back to an element of the
            algebra again.
            """
            return sum(c * b for (c, b) in zip(v, self.basis(deg)))
        if max_degree == 1:
            cohom1 = self.cohomology(1).basis().keys()
            if not cohom1:
                return {}
            return {1: [g.representative() for g in cohom1]}
        smaller_degree = {i: [g.representative() for g in
                              self.cohomology(i).basis().keys()] for i in
                          range(1, max_degree)}
        already_generated = []
        for i in range(1, max_degree):
            already_generated += [a * b for a in smaller_degree[i] for b in
                                  smaller_degree[max_degree - i]]
        CR = self.cohomology_raw(max_degree)
        V = CR.V()
        S = CR.submodule([CR(V(g.basis_coefficients(total=True))) for g in
                          already_generated if not g.is_zero()])
        Q = CR.quotient(S)
        res = self.cohomology_generators(max_degree - 1)
        if Q.basis():
            res[max_degree] = [vector_to_element(CR.lift(Q.lift(g)),
                                                 max_degree)
                               for g in Q.basis()]
        return res

    def minimal_model(self, i=3, max_iterations=3):
        """
        Try to compute a map from a ``i``-minimal gcda that is a
        ``i``-quasi-isomorphism to self.

        INPUT:

        - ``i`` -- integer (default: `3`); degree to which the result is
          required to induce an isomorphism in cohomology, and the domain is
          required to be minimal.

        - ``max_iterations`` -- integer (default: `3`); the number of
          iterations of the method at each degree. If the algorithm does not
          finish in this many iterations at each degree, an error is raised.

        OUTPUT:

        A morphism from a minimal Sullivan (up to degree ``i``) CDGA's to self,
        that induces an isomorphism in cohomology up to degree ``i``, and a
        monomorphism in degree ``i+1``.

        EXAMPLES::

            sage: S.<x, y, z> = GradedCommutativeAlgebra(QQ, degrees = (1, 1, 2))
            sage: d = S.differential({x:x*y, y:x*y})
            sage: R = S.cdg_algebra(d)
            sage: p = R.minimal_model()
            sage: T = p.domain()
            sage: p
            Commutative Differential Graded Algebra morphism:
              From: Commutative Differential Graded Algebra with generators ('x1_0', 'x2_0') in degrees (1, 2) over Rational Field with differential:
               x1_0 --> 0
               x2_0 --> 0
              To:   Commutative Differential Graded Algebra with generators ('x', 'y', 'z') in degrees (1, 1, 2) over Rational Field with differential:
               x --> x*y
               y --> x*y
               z --> 0
              Defn: (x1_0, x2_0) --> (x - y, z)
            sage: R.cohomology(1)
            Free module generated by {[x - y]} over Rational Field
            sage: T.cohomology(1)
            Free module generated by {[x1_0]} over Rational Field
            sage: [p(g.representative()) for g in T.cohomology(1).basis().keys()]
            [x - y]
            sage: R.cohomology(2)
            Free module generated by {[z]} over Rational Field
            sage: T.cohomology(2)
            Free module generated by {[x2_0]} over Rational Field
            sage: [p(g.representative()) for g in T.cohomology(2).basis().keys()]
            [z]



            sage: A.<e1, e2, e3, e4, e5, e6, e7> = GradedCommutativeAlgebra(QQ)
            sage: d = A.differential({e1:e1*e7, e2:e2*e7, e3:-e3*e7, e4:-e4*e7})
            sage: B = A.cdg_algebra(d)
            sage: phi = B.minimal_model(i=3)
            sage: M = phi.domain()
            sage: M
            Commutative Differential Graded Algebra with generators ('x1_0', 'x1_1', 'x1_2', 'x2_0', 'x2_1', 'x2_2', 'x2_3', 'y3_0', 'y3_1', 'y3_2', 'y3_3', 'y3_4', 'y3_5', 'y3_6', 'y3_7', 'y3_8') in degrees (1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3) over Rational Field with differential:
               x1_0 --> 0
               x1_1 --> 0
               x1_2 --> 0
               x2_0 --> 0
               x2_1 --> 0
               x2_2 --> 0
               x2_3 --> 0
               y3_0 --> x2_0^2
               y3_1 --> x2_0*x2_1
               y3_2 --> x2_1^2
               y3_3 --> x2_0*x2_2
               y3_4 --> x2_1*x2_2 + x2_0*x2_3
               y3_5 --> x2_2^2
               y3_6 --> x2_1*x2_3
               y3_7 --> x2_2*x2_3
               y3_8 --> x2_3^2

            sage: phi
            Commutative Differential Graded Algebra morphism:
              From: Commutative Differential Graded Algebra with generators ('x1_0', 'x1_1', 'x1_2', 'x2_0', 'x2_1', 'x2_2', 'x2_3', 'y3_0', 'y3_1', 'y3_2', 'y3_3', 'y3_4', 'y3_5', 'y3_6', 'y3_7', 'y3_8') in degrees (1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3) over Rational Field with differential:
               x1_0 --> 0
               x1_1 --> 0
               x1_2 --> 0
               x2_0 --> 0
               x2_1 --> 0
               x2_2 --> 0
               x2_3 --> 0
               y3_0 --> x2_0^2
               y3_1 --> x2_0*x2_1
               y3_2 --> x2_1^2
               y3_3 --> x2_0*x2_2
               y3_4 --> x2_1*x2_2 + x2_0*x2_3
               y3_5 --> x2_2^2
               y3_6 --> x2_1*x2_3
               y3_7 --> x2_2*x2_3
               y3_8 --> x2_3^2
              To:   Commutative Differential Graded Algebra with generators ('e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7') in degrees (1, 1, 1, 1, 1, 1, 1) over Rational Field with differential:
               e1 --> e1*e7
               e2 --> e2*e7
               e3 --> -e3*e7
               e4 --> -e4*e7
               e5 --> 0
               e6 --> 0
               e7 --> 0
              Defn: (x1_0, x1_1, x1_2, x2_0, x2_1, x2_2, x2_3, y3_0, y3_1, y3_2, y3_3, y3_4, y3_5, y3_6, y3_7, y3_8) --> (e5, e6, e7, e1*e3, e2*e3, e1*e4, e2*e4, 0, 0, 0, 0, 0, 0, 0, 0, 0)
            sage: [B.cohomology(i).dimension() for i in [1..3]]
            [3, 7, 13]
            sage: [M.cohomology(i).dimension() for i in [1..3]]
            [3, 7, 13]

        ALGORITHM:

        We follow the algorithm described in [Man2019]_. It consists in
        constructing the minimal Sullivan algebra ``S`` by iteratively adding
        generators to it. Start with one closed generator of degree 1 for each
        element in the basis of the first cohomology of the algebra. Then
        proceed degree by degree. At each degree `d`, we keep adding generators
        of degree `d-1` whose differential kills the elements in the kernel of
        the map `H^d(S)\to H^d(self)`. Once this map is made injective, we add
        the needed closed generators in degree `d` to make it surjective.

        .. WARNING::

            The method is not granted to finish (it can't, since the minimal
            model could be infinitely generated in some degrees).
            The parameter ``max_iterations`` controls how many iterations of
            the method are attempted at each degree. In case they are not
            enough, an exception is raised. If you think that the result will
            be finitely generated, you can try to run it again with a higher
            value for ``max_iterations``.

        .. SEEALSO::

            :wikipedia:`Rational_homotopy_theory#Sullivan_algebras`

        TESTS::

            sage: A.<x, y, z, t> = GradedCommutativeAlgebra(QQ,degrees = (1, 2, 3, 3))
            sage: d = A.differential({x:y})
            sage: B = A.cdg_algebra(d)
            sage: B.minimal_model(i=3)
            Commutative Differential Graded Algebra morphism:
              From: Commutative Differential Graded Algebra with generators ('x3_0', 'x3_1') in degrees (3, 3) over Rational Field with differential:
               x3_0 --> 0
               x3_1 --> 0
              To:   Commutative Differential Graded Algebra with generators ('x', 'y', 'z', 't') in degrees (1, 2, 3, 3) over Rational Field with differential:
               x --> y
               y --> 0
               z --> 0
               t --> 0
              Defn: (x3_0, x3_1) --> (z, t)

        REFERENCES:

        - [Fel2001]_

        - [Man2019]_

        """
        max_degree = int(i)
        if max_degree < 1:
            raise ValueError("the degree must be a positive integer")
        if max_iterations not in ZZ or max_iterations < 1:
            raise ValueError("max_iterations must be a positive integer")
        if max_degree in self._minimalmodels:
            return self._minimalmodels[max_degree]
        from copy import copy

        def extend(phi, ndegrees, ndifs, nimags, nnames):
            """
            Extend phi to a new algebra with new genererators, labeled by nnames
            """
            B = phi.domain()
            names = [str(g) for g in B.gens()]
            degrees = [g.degree() for g in B.gens()]
            A = GradedCommutativeAlgebra(B.base_ring(), names=names + nnames,
                                         degrees=degrees + ndegrees)
            h = B.hom(A.gens()[:B.ngens()], check=False)
            d = B.differential()
            diff = {h(g): h(d(g)) for g in B.gens()}
            cndifs = copy(ndifs)
            for g in A.gens()[B.ngens():]:
                diff[g] = h(cndifs.pop(0))
            NB = A.cdg_algebra(diff)
            Nphi = NB.hom([phi(g) for g in B.gens()] + nimags, check=False)
            return Nphi

        def extendx(phi, degree):
            B = phi.domain()
            imagesbcohom = [phi(g.representative())
                            for g in B.cohomology(degree).basis().keys()]
            CS = self.cohomology_raw(degree)
            VS = CS.V()
            CB = B.cohomology_raw(degree)
            imagesphico = []
            for g in imagesbcohom:
                if g.is_zero():
                    imagesphico.append(CS.zero())
                else:
                    imagesphico.append(CS(VS(g.basis_coefficients())))
            phico = CB.hom(imagesphico, codomain=CS)
            QI = CS.quotient(phico.image())
            self._numerical_invariants[degree] = [QI.dimension()]
            if QI.dimension() > 0:
                nnames = ['x{}_{}'.format(degree, j) for j in
                          range(QI.dimension())]
                nbasis = []
                bbasis = self.basis(degree)
                for v in QI.basis():
                    vl = CS.lift(QI.lift(v))
                    g = sum(bbasis[j] * vl[j] for j in range(len(bbasis)))
                    nbasis.append(g)
                nimags = nbasis
                ndegrees = [degree for j in nbasis]
                return extend(phi, ndegrees, [B.zero() for nimag in nimags],
                              nimags, nnames)
            return phi

        def extendy(phi, degree):
            nnamesy = 0
            for iteration in range(max_iterations):
                B = phi.domain()
                imagesbcohom = [phi(g.representative()) for g in
                                B.cohomology(degree).basis().keys()]
                CS = self.cohomology_raw(degree)
                VS = CS.V()
                CB = B.cohomology_raw(degree)
                imagesphico = []
                for g in imagesbcohom:
                    if g.is_zero():
                        imagesphico.append(CS.zero())
                    else:
                        imagesphico.append(CS(VS(g.basis_coefficients())))
                phico = CB.hom(imagesphico, codomain=CS)
                K = phico.kernel()
                self._numerical_invariants[degree - 1].append(K.dimension())
                if K.dimension() == 0:
                    return phi
                if iteration == max_iterations - 1:
                    raise ValueError("could not cover all relations in max iterations in degree {}".format(degree))
                ndifs = [CB.lift(g) for g in K.basis()]
                basisdegree = B.basis(degree)
                ndifs = [sum(basisdegree[j] * g[j] for j in
                             range(len(basisdegree))) for g in ndifs]
                MS = self.differential().differential_matrix(degree - 1)
                nimags = []
                for g in ndifs:
                    if phi(g).is_zero():
                        nimags.append(vector(MS.nrows() * [0]))
                    else:
                        nimags.append(MS.solve_left(vector(phi(g).basis_coefficients())))
                nimags = [sum(self.basis(degree - 1)[j] * g[j]
                              for j in range(len(self.basis(degree - 1)))
                              ) for g in nimags]
                ndegrees = [degree - 1 for g in nimags]
                nnames = ['y{}_{}'.format(degree - 1, j + nnamesy)
                          for j in range(len(nimags))]
                nnamesy += len(nimags)
                phi = extend(phi, ndegrees, ndifs, nimags, nnames)
                B = phi.domain()

        if not self._minimalmodels:
            degnzero = 1
            while self.cohomology(degnzero).dimension() == 0:
                self._numerical_invariants[degnzero] = [0]
                degnzero += 1
                if degnzero > max_degree:
                    raise ValueError("cohomology is trivial up to max_degree")
            gens = [g.representative()
                    for g in self.cohomology(degnzero).basis().keys()]
            self._numerical_invariants[degnzero] = [len(gens)]
            names = ['x{}_{}'.format(degnzero, j) for j in range(len(gens))]
            A = GradedCommutativeAlgebra(self.base_ring(),
                                         names,
                                         degrees=[degnzero for j in names])
            B = A.cdg_algebra(A.differential({}))
            # Solve case that fails with one generator return B,gens
            phi = B.hom(gens)
            phi = extendy(phi, degnzero + 1)
            self._minimalmodels[degnzero] = phi
        else:
            degnzero = max(self._minimalmodels)
            phi = self._minimalmodels[degnzero]

        for degree in range(degnzero + 1, max_degree + 1):
            phi = extendx(phi, degree)
            phi = extendy(phi, degree + 1)
            self._minimalmodels[degree] = phi

        return phi

    def cohomology_algebra(self, max_degree=3):
        """
        Compute a CDGA with trivial differential, that is isomorphic to the cohomology of
        self up to``max_degree``

        INPUT:

        - ``max_degree`` -- integer (default: `3`); degree to which the result is required to
          be isomorphic to self's cohomology.

        EXAMPLES::

            sage: A.<e1, e2, e3, e4, e5, e6, e7> = GradedCommutativeAlgebra(QQ)
            sage: d = A.differential({e1:-e1*e6, e2:-e2*e6, e3:-e3*e6, e4:-e5*e6, e5:e4*e6})
            sage: B = A.cdg_algebra(d)
            sage: M = B.cohomology_algebra()
            sage: M
            Commutative Differential Graded Algebra with generators ('x0', 'x1', 'x2') in degrees (1, 1, 2) over Rational Field with differential:
               x0 --> 0
               x1 --> 0
               x2 --> 0
            sage: M.cohomology(1)
            Free module generated by {[x0], [x1]} over Rational Field
            sage: B.cohomology(1)
            Free module generated by {[e6], [e7]} over Rational Field
            sage: M.cohomology(2)
            Free module generated by {[x0*x1], [x2]} over Rational Field
            sage: B.cohomology(2)
            Free module generated by {[e4*e5], [e6*e7]} over Rational Field
            sage: M.cohomology(3)
            Free module generated by {[x0*x2], [x1*x2]} over Rational Field
            sage: B.cohomology(3)
            Free module generated by {[e4*e5*e6], [e4*e5*e7]} over Rational Field
        """
        cohomgens = self.cohomology_generators(max_degree)
        if not cohomgens:
            raise ValueError("Cohomology ring has no generators")
        chgens = []
        degrees = []
        for d in cohomgens:
            for g in cohomgens[d]:
                degrees.append(d)
                chgens.append(g)
        A = GradedCommutativeAlgebra(self.base_ring(),
                                     ['x{}'.format(i) for i in range(len(chgens))],
                                     degrees)
        rels = []
        for d in range(1, max_degree + 1):
            B1 = A.basis(d)
            V2 = self.cohomology_raw(d)
            images = []
            for g in B1:
                ig = g._im_gens_(self, chgens)
                if ig.is_zero():
                    images.append(V2.zero())
                else:
                    images.append(V2(V2.V()(ig.basis_coefficients())))
            V1 = self.base_ring()**len(B1)
            h = V1.hom(images, codomain=V2)
            K = h.kernel()
            for g in K.basis():
                newrel = sum(g[i] * B1[i] for i in range(len(B1)))
                rels.append(newrel)
        return A.quotient(A.ideal(rels)).cdg_algebra({})

    def numerical_invariants(self, max_degree=3, max_iterations=3):
        r"""
        Return the numerical invariants of the algebra, up to degree ``d``. The
        numerical invariants reflect the number of generators added at each step
        of the construction of the minimal model.

        The numerical invariants are the dimensions of the subsequent Hirsch
        extensions used at each degree to compute the minimal model.

        INPUT:

        - ``max_degree`` -- integer (default: `3`); the degree up to which the
          numerical invariants are computed

        - ``max_iterations`` -- integer (default: `3`); the maximum number of iterations
          used to compute the minimal model, if it is not already cached

        EXAMPLES::

            sage: A.<e1, e2, e3> = GradedCommutativeAlgebra(QQ)
            sage: B = A.cdg_algebra({e3 : e1*e2})
            sage: B.minimal_model(4)
            Commutative Differential Graded Algebra morphism:
            From: Commutative Differential Graded Algebra with generators ('x1_0', 'x1_1', 'y1_0') in degrees (1, 1, 1) over Rational Field with differential:
            x1_0 --> 0
            x1_1 --> 0
            y1_0 --> x1_0*x1_1
            To:   Commutative Differential Graded Algebra with generators ('e1', 'e2', 'e3') in degrees (1, 1, 1) over Rational Field with differential:
            e1 --> 0
            e2 --> 0
            e3 --> e1*e2
            Defn: (x1_0, x1_1, y1_0) --> (e1, e2, e3)
            sage: B.numerical_invariants(2)
            {1: [2, 1, 0], 2: [0, 0]}

        ALGORITHM:

        The numerical invariants are stored as the minimal model is constructed.

        .. WARNING::

            The method is not granted to finish (it can't, since the minimal
            model could be infinitely generated in some degrees).
            The parameter ``max_iterations`` controls how many iterations of
            the method are attempted at each degree. In case they are not
            enough, an exception is raised. If you think that the result will
            be finitely generated, you can try to run it again with a higher
            value for ``max_iterations``.

        REFERENCES:

        For a precise definition and properties, see [Man2019]_ .

        """
        self.minimal_model(max_degree, max_iterations)
        return {i: self._numerical_invariants[i]
                for i in range(1, max_degree + 1)}

    def is_formal(self, i, max_iterations=3):
        r"""
        Check if the algebra is ``i``-formal. That is, if it is ``i``-quasi-isomorphic
        to its cohomology algebra.

        INPUT:

        - ``i`` -- integer; the degree up to which the formality is checked

        - ``max_iterations`` -- integer (default: `3`); the maximum number of
          iterations used in the computation of the minimal model

        .. WARNING::

            The method is not granted to finish (it can't, since the minimal
            model could be infinitely generated in some degrees).
            The parameter ``max_iterations`` controls how many iterations of
            the method are attempted at each degree. In case they are not
            enough, an exception is raised. If you think that the result will
            be finitely generated, you can try to run it again with a higher
            value for ``max_iterations``.

            Moreover, the method uses criteria that are often enough to conclude
            that the algebra is either formal or non-formal. However, it could
            happen that the used criteria can not determine the formality. In
            that case, an error is raised.

        EXAMPLES::

            sage: A.<e1, e2, e3, e4, e5> = GradedCommutativeAlgebra(QQ)
            sage: B = A.cdg_algebra({e5 : e1*e2 + e3*e4})
            sage: B.is_formal(1)
            True
            sage: B.is_formal(2)
            False

        ALGORITHM:

        Apply the criteria in [Man2019]_ . Both the `i`-minimal model of the
        algebra and its cohomology algebra are computed. If the numerical
        invariants are different, the algebra is not `i`-formal.

        If the numerical invariants match, the `\psi` condition is checked.
        """
        phi = self.minimal_model(i, max_iterations)
        M = phi.domain()
        H = M.cohomology_algebra(i + 1)
        try:
            H.minimal_model(i, max_iterations)
        except ValueError:  # If we could compute the minimal model in max_iterations
            return False    # but not for the cohomology, the invariants are distinct
        N1 = self.numerical_invariants(i, max_iterations)
        N2 = H.numerical_invariants(i, max_iterations)
        if any(N1[n] != N2[n] for n in range(1, i + 1)):
            return False    # numerical invariants don't match
        subsdict = {y.lift(): 0 for y in M.gens() if not y.differential().is_zero()}
        tocheck = [M(g.differential().lift().subs(subsdict)) for g in M.gens()]
        if all(c.is_coboundary() for c in tocheck):
            return True     # the morphism xi->[xi], yi->0 is i-quasi-iso
        raise NotImplementedError("the implemented criteria cannot determine formality")

    class Element(GCAlgebra.Element):
        def differential(self):
            """
            The differential on this element.

            EXAMPLES::

                sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees = (2, 2, 3, 4))
                sage: B = A.cdg_algebra({t: x*z, x: z, y: z})
                sage: B.inject_variables()
                Defining x, y, z, t
                sage: x.differential()
                z
                sage: (-1/2 * x^2 + t).differential()
                0
            """
            return self.parent().differential()(self)

        def is_coboundary(self):
            """
            Return ``True`` if ``self`` is a coboundary and ``False``
            otherwise.

            This raises an error if the element is not homogeneous.

            EXAMPLES::

                sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,2,2))
                sage: B = A.cdg_algebra(differential={b: a*c})
                sage: x,y,z = B.gens()
                sage: x.is_coboundary()
                False
                sage: (x*z).is_coboundary()
                True
                sage: (x*z+x*y).is_coboundary()
                False
                sage: (x*z+y**2).is_coboundary()
                Traceback (most recent call last):
                ...
                ValueError: This element is not homogeneous
            """
            if not self.is_homogeneous():
                raise ValueError('This element is not homogeneous')
            # To avoid taking the degree of 0, we special-case it.
            if self.is_zero():
                return True
            v = vector(self.basis_coefficients())
            return v in self.parent().coboundaries(self.degree())

        def is_cohomologous_to(self, other):
            """
            Return ``True`` if ``self`` is cohomologous to ``other``
            and ``False`` otherwise.

            INPUT:

            - ``other`` -- another element of this algebra

            EXAMPLES::

                sage: A.<a,b,c,d> = GradedCommutativeAlgebra(QQ, degrees=(1,1,1,1))
                sage: B = A.cdg_algebra(differential={a:b*c-c*d})
                sage: w, x, y, z = B.gens()
                sage: (x*y).is_cohomologous_to(y*z)
                True
                sage: (x*y).is_cohomologous_to(x*z)
                False
                sage: (x*y).is_cohomologous_to(x*y)
                True

            Two elements whose difference is not homogeneous are
            cohomologous if and only if they are both coboundaries::

                sage: w.is_cohomologous_to(y*z)
                False
                sage: (x*y-y*z).is_cohomologous_to(x*y*z)
                True
                sage: (x*y*z).is_cohomologous_to(0) # make sure 0 works
                True

            """
            if other.is_zero():
                return self.is_coboundary()
            if (not isinstance(other, DifferentialGCAlgebra.Element)
               or self.parent() is not other.parent()):
                raise ValueError('The element {} does not lie in this DGA'
                                 .format(other))
            if (self - other).is_homogeneous():
                return (self - other).is_coboundary()
            else:
                return (self.is_coboundary() and other.is_coboundary())

        def cohomology_class(self):
            r"""
            Return the cohomology class of an homogenous cycle, as an element
            of the corresponding cohomology group.

            EXAMPLES::

                sage: A.<e1,e2,e3,e4,e5> = GradedCommutativeAlgebra(QQ)
                sage: B = A.cdg_algebra({e5:e1*e2+e3*e4})
                sage: B.inject_variables()
                Defining e1, e2, e3, e4, e5
                sage: a = e1*e3*e5-3*e2*e3*e5
                sage: a.cohomology_class()
                B[[e1*e3*e5]] - 3*B[[e2*e3*e5]]

            TESTS::

                sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1, 2, 3))
                sage: B = A.cdg_algebra({a:b})
                sage: B.inject_variables()
                Defining a, b, c
                sage: b.cohomology_class()
                0
                sage: b.cohomology_class().parent()
                Free module generated by {} over Rational Field
            """
            if not self.is_homogeneous():
                raise ValueError("The element is not homogenous")
            if not self.differential().is_zero():
                raise ValueError("The element is not closed")
            d = self.degree()
            C = self.parent().cohomology(d)
            CR = self.parent().cohomology_raw(d)
            V = CR.V()
            cohomcoefs = CR(V(self.basis_coefficients()))
            return C(sum(a * b for (a, b) in zip(cohomcoefs, C.basis().values())))

        def _cohomology_class_dict(self):
            r"""
            Return the dictionary that represents the cohomology class of
            the cycle expressed in terms of the cohomology generators.

            This can be used to map the cycle to the cohomology algebra.

            EXAMPLES::

                sage: A.<e1,e2,e3,e4,e5> = GradedCommutativeAlgebra(QQ)
                sage: B = A.cdg_algebra({e5:e1*e2+e3*e4})
                sage: a = B(e1*e3*e5-3*e2*e3*e5)
                sage: a._cohomology_class_dict()
                {(0, 0, 0, 0, 0, 0, 1, 0, 0): -3, (0, 0, 0, 0, 0, 1, 0, 0, 0): 1}
                sage: H = B.cohomology_algebra(3)
                sage: H(a._cohomology_class_dict())
                x5 - 3*x6
                sage: B.cohomology_generators(3)
                {1: [e1, e2, e3, e4],
                3: [e1*e2*e5 - e3*e4*e5, e1*e3*e5, e2*e3*e5, e1*e4*e5, e2*e4*e5]}
                sage: [H(g._cohomology_class_dict()) for g in flatten(B.cohomology_generators(3).values())]
                [x0, x1, x2, x3, x4, x5, x6, x7, x8]
            """
            from sage.misc.flatten import flatten
            if not self.differential().is_zero():
                raise ValueError("The element is not closed")
            if not self.is_homogeneous():
                res = {}
                for d in self.homogenous_parts().values():
                    res.update(d._cohomology_class_dict())
                return res
            d = self.degree()
            gens = flatten(self.parent().cohomology_generators(d).values())
            ebasis = exterior_algebra_basis(d, tuple(g.degree() for g in gens))
            gensd = [prod([gens[i]**b[i]
                           for i in range(len(b))]) for b in ebasis]
            m = matrix([g.cohomology_class()._vector_() for g in gensd])
            coeffs = m.solve_left(self.cohomology_class()._vector_())
            return {tuple(ebasis[i]): coeffs[i]
                    for i in range(len(ebasis)) if coeffs[i]}


class DifferentialGCAlgebra_multigraded(DifferentialGCAlgebra,
                                        GCAlgebra_multigraded):
    """
    A commutative differential multi-graded algebras.

    INPUT:

    - ``A`` -- a commutative multi-graded algebra

    - ``differential`` -- a differential

    EXAMPLES::

        sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
        sage: B = A.cdg_algebra(differential={a: c})
        sage: B.basis((1,0))
        [a]
        sage: B.basis(1, total=True)
        [a, b]
        sage: B.cohomology((1, 0))
        Free module generated by {} over Rational Field
        sage: B.cohomology(1, total=True)
        Free module generated by {[b]} over Rational Field
    """
    def __init__(self, A, differential):
        """
        Initialize ``self``.

        INPUT:

        - ``A`` -- a multi-graded commutative algebra
        - ``differential`` -- a differential

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: B = A.cdg_algebra(differential={a: c})

        Trying to define a differential which is not multi-graded::

            sage: A.<t,x,y,z> = GradedCommutativeAlgebra(QQ, degrees=((1,0),(1,0),(2,0),(0,2)))
            sage: B = A.cdg_algebra(differential={x:y}) # good
            sage: B = A.cdg_algebra(differential={t:z}) # good
            sage: B = A.cdg_algebra(differential={x:y, t:z}) # bad
            Traceback (most recent call last):
            ...
            ValueError: The differential does not have a well-defined degree
        """
        GCAlgebra_multigraded.__init__(self, A.base(), names=A._names,
                                       degrees=A._degrees_multi,
                                       R=A.cover_ring(),
                                       I=A.defining_ideal())
        self._differential = Differential_multigraded(self, differential._dic_)

    def _base_repr(self):
        """
        Return the base string representation of ``self``.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: A.cdg_algebra(differential={a: c})._base_repr()
            "Commutative Differential Graded Algebra with generators ('a', 'b', 'c') in degrees ((1, 0), (0, 1), (0, 2)) over Rational Field"
        """
        s = DifferentialGCAlgebra._base_repr(self)
        old = '{}'.format(self._degrees)
        new = '{}'.format(self._degrees_multi)
        return s.replace(old, new)

    def coboundaries(self, n, total=False):
        """
        The ``n``-th coboundary group of the algebra.

        This is a vector space over the base field `F`, and it is
        returned as a subspace of the vector space `F^d`, where the
        ``n``-th homogeneous component has dimension `d`.

        INPUT:

        - ``n`` -- degree
        - ``total`` (default ``False``) -- if ``True``, return the
          coboundaries in total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: B = A.cdg_algebra(differential={a: c})
            sage: B.coboundaries((0,2))
            Vector space of degree 1 and dimension 1 over Rational Field
            Basis matrix:
            [1]
            sage: B.coboundaries(2)
            Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [0 1]
        """
        return self._differential.coboundaries(n, total)

    def cocycles(self, n, total=False):
        r"""
        The ``n``-th cocycle group of the algebra.

        This is a vector space over the base field `F`, and it is
        returned as a subspace of the vector space `F^d`, where the
        ``n``-th homogeneous component has dimension `d`.

        INPUT:

        - ``n`` -- degree
        - ``total`` -- (default: ``False``) if ``True``, return the
          cocycles in total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: B = A.cdg_algebra(differential={a: c})
            sage: B.cocycles((0,1))
            Vector space of degree 1 and dimension 1 over Rational Field
            Basis matrix:
            [1]
            sage: B.cocycles((0,1), total=True)
            Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [0 1]
        """
        return self._differential.cocycles(n, total)

    def cohomology_raw(self, n, total=False):
        """
        The ``n``-th cohomology group of the algebra.

        This is a vector space over the base ring, and it is returned
        as the quotient cocycles/coboundaries.

        Compare to :meth:`cohomology`.

        INPUT:

        - ``n`` -- degree
        - ``total`` -- (default: ``False``) if ``True``, return the
          cohomology in total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: B = A.cdg_algebra(differential={a: c})
            sage: B.cohomology_raw((0,2))
            Vector space quotient V/W of dimension 0 over Rational Field where
            V: Vector space of degree 1 and dimension 1 over Rational Field
            Basis matrix:
            [1]
            W: Vector space of degree 1 and dimension 1 over Rational Field
            Basis matrix:
            [1]

            sage: B.cohomology_raw(1)
            Vector space quotient V/W of dimension 1 over Rational Field where
            V: Vector space of degree 2 and dimension 1 over Rational Field
            Basis matrix:
            [0 1]
            W: Vector space of degree 2 and dimension 0 over Rational Field
            Basis matrix:
            []
        """
        return self._differential.cohomology_raw(n, total)

    def cohomology(self, n, total=False):
        """
        The ``n``-th cohomology group of the algebra.

        This is a vector space over the base ring, defined as the
        quotient cocycles/coboundaries. The elements of the quotient
        are lifted to the vector space of cocycles, and this is
        described in terms of those lifts.

        Compare to :meth:`cohomology_raw`.

        INPUT:

        - ``n`` -- degree
        - ``total`` -- (default: ``False``) if ``True``, return the
          cohomology in total degree ``n``

        If ``n`` is an integer rather than a multi-index, then the
        total degree is used in that case as well.

        EXAMPLES::

            sage: A.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0, 1), (0,2)))
            sage: B = A.cdg_algebra(differential={a: c})
            sage: B.cohomology((0,2))
            Free module generated by {} over Rational Field

            sage: B.cohomology(1)
            Free module generated by {[b]} over Rational Field
        """
        return self._differential.cohomology(n, total)

    class Element(GCAlgebra_multigraded.Element, DifferentialGCAlgebra.Element):
        """
        Element class of a commutative differential multi-graded algebra.
        """

################################################
# Main entry point


def GradedCommutativeAlgebra(ring, names=None, degrees=None, relations=None):
    r"""
    A graded commutative algebra.

    INPUT:

    There are two ways to call this. The first way defines a free
    graded commutative algebra:

    - ``ring`` -- the base field over which to work

    - ``names`` -- names of the generators. You may also use Sage's
      ``A.<x,y,...> = ...`` syntax to define the names. If no names
      are specified, the generators are named ``x0``, ``x1``, ...

    - ``degrees`` -- degrees of the generators; if this is omitted,
      the degree of each generator is 1, and if both ``names`` and
      ``degrees`` are omitted, an error is raised

    Once such an algebra has been defined, one can use its associated
    methods to take a quotient, impose a differential, etc. See the
    examples below.

    The second way takes a graded commutative algebra and imposes
    relations:

    - ``ring`` -- a graded commutative algebra

    - ``relations`` -- a list or tuple of elements of ``ring``

    EXAMPLES:

    Defining a graded commutative algebra::

        sage: GradedCommutativeAlgebra(QQ, 'x, y, z')
        Graded Commutative Algebra with generators ('x', 'y', 'z') in degrees (1, 1, 1) over Rational Field
        sage: GradedCommutativeAlgebra(QQ, degrees=(2, 3, 4))
        Graded Commutative Algebra with generators ('x0', 'x1', 'x2') in degrees (2, 3, 4) over Rational Field

    As usual in Sage, the ``A.<...>`` notation defines both the
    algebra and the generator names::

        sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1, 1, 2))
        sage: x^2
        0
        sage: y*x # Odd classes anticommute.
        -x*y
        sage: z*y # z is central since it is in degree 2.
        y*z
        sage: (x*y*z**3).degree()
        8
        sage: A.basis(3) # basis of homogeneous degree 3 elements
        [x*z, y*z]

    Defining a quotient::

        sage: I = A.ideal(x*z)
        sage: AQ = A.quotient(I)
        sage: AQ
        Graded Commutative Algebra with generators ('x', 'y', 'z') in degrees (1, 1, 2) with relations [x*z] over Rational Field
        sage: AQ.basis(3)
        [y*z]

    Note that ``AQ`` has no specified differential. This is reflected in
    its print representation: ``AQ`` is described as a "graded commutative
    algebra" -- the word "differential" is missing. Also, it has no
    default ``differential``::

        sage: AQ.differential()  # py2
        Traceback (most recent call last):
        ...
        TypeError: differential() takes exactly 2 arguments (1 given)
        sage: AQ.differential()  # py3
        Traceback (most recent call last):
        ...
        TypeError: differential() missing 1 required positional argument:
        'diff'

    Now we add a differential to ``AQ``::

        sage: B = AQ.cdg_algebra({z:y*z})
        sage: B
        Commutative Differential Graded Algebra with generators ('x', 'y', 'z') in degrees (1, 1, 2) with relations [x*z] over Rational Field with differential:
            x --> 0
            y --> 0
            z --> y*z
        sage: B.differential()
        Differential of Commutative Differential Graded Algebra with generators ('x', 'y', 'z') in degrees (1, 1, 2) with relations [x*z] over Rational Field
          Defn: x --> 0
                y --> 0
                z --> y*z
        sage: B.cohomology(1)
        Free module generated by {[x], [y]} over Rational Field
        sage: B.cohomology(2)
        Free module generated by {[x*y]} over Rational Field

    We compute algebra generators for cohomology in a range of
    degrees. This cohomology algebra appears to be finitely
    generated::

        sage: B.cohomology_generators(15)
        {1: [x, y]}

    We can construct multi-graded rings as well. We work in characteristic 2
    for a change, so the algebras here are honestly commutative::

        sage: C.<a,b,c,d> = GradedCommutativeAlgebra(GF(2), degrees=((1,0), (1,1), (0,2), (0,3)))
        sage: D = C.cdg_algebra(differential={a:c, b:d})
        sage: D
        Commutative Differential Graded Algebra with generators ('a', 'b', 'c', 'd') in degrees ((1, 0), (1, 1), (0, 2), (0, 3)) over Finite Field of size 2 with differential:
            a --> c
            b --> d
            c --> 0
            d --> 0

    We can examine ``D`` using both total degrees and multidegrees.
    Use tuples, lists, vectors, or elements of additive
    abelian groups to specify degrees::

        sage: D.basis(3) # basis in total degree 3
        [a^3, a*b, a*c, d]
        sage: D.basis((1,2)) # basis in degree (1,2)
        [a*c]
        sage: D.basis([1,2])
        [a*c]
        sage: D.basis(vector([1,2]))
        [a*c]
        sage: G = AdditiveAbelianGroup([0,0]); G
        Additive abelian group isomorphic to Z + Z
        sage: D.basis(G(vector([1,2])))
        [a*c]

    At this point, ``a``, for example, is an element of ``C``. We can
    redefine it so that it is instead an element of ``D`` in several
    ways, for instance using :meth:`gens` method::

        sage: a, b, c, d = D.gens()
        sage: a.differential()
        c

    Or the :meth:`inject_variables` method::

        sage: D.inject_variables()
        Defining a, b, c, d
        sage: (a*b).differential()
        b*c + a*d
        sage: (a*b*c**2).degree()
        (2, 5)

    Degrees are returned as elements of additive abelian groups::

        sage: (a*b*c**2).degree() in G
        True

        sage: (a*b*c**2).degree(total=True)  # total degree
        7
        sage: D.cohomology(4)
        Free module generated by {[a^4], [b^2]} over Finite Field of size 2
        sage: D.cohomology((2,2))
        Free module generated by {[b^2]} over Finite Field of size 2

    TESTS:

    We need to specify either name or degrees::

        sage: GradedCommutativeAlgebra(QQ)
        Traceback (most recent call last):
        ...
        ValueError: You must specify names or degrees
    """
    multi = False
    if degrees:
        try:
            for d in degrees:
                list(d)
            # If the previous line doesn't raise an error, looks multi-graded.
            multi = True
        except TypeError:
            pass
    if multi:
        return GCAlgebra_multigraded(ring, names=names, degrees=degrees)
    else:
        return GCAlgebra(ring, names=names, degrees=degrees)


################################################
# Morphisms

class GCAlgebraMorphism(RingHomomorphism_im_gens):
    """
    Create a morphism between two :class:`graded commutative algebras <GCAlgebra>`.

    INPUT:

    - ``parent`` -- the parent homset

    - ``im_gens`` -- the images, in the codomain, of the generators of
      the domain

    - ``check`` -- boolean (default: ``True``); check whether the
      proposed map is actually an algebra map; if the domain and
      codomain have differentials, also check that the map respects
      those.

    EXAMPLES::

        sage: A.<x,y> = GradedCommutativeAlgebra(QQ)
        sage: H = Hom(A,A)
        sage: f = H([y,x])
        sage: f
        Graded Commutative Algebra endomorphism of Graded Commutative Algebra with generators ('x', 'y') in degrees (1, 1) over Rational Field
          Defn: (x, y) --> (y, x)
        sage: f(x*y)
        -x*y
    """
    def __init__(self, parent, im_gens, check=True):
        r"""
        TESTS:

        The entries in ``im_gens`` must lie in the codomain::

            sage: A.<x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
            sage: B.<a,b> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
            sage: H = Hom(A,A)
            sage: H([x,b])
            Traceback (most recent call last):
            ...
            ValueError: not all elements of im_gens are in the codomain

        Note that morphisms do not need to respect the grading;
        whether they do can be tested with the method
        :meth:`is_graded`::

            sage: A.<x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
            sage: H = Hom(A,A)
            sage: f = H([x,x])
            sage: f
            Graded Commutative Algebra endomorphism of Graded Commutative Algebra with generators ('x', 'y') in degrees (1, 2) over Rational Field
              Defn: (x, y) --> (x, x)
            sage: f.is_graded()
            False
            sage: TestSuite(f).run(skip="_test_category")

        Since `x^2=0` but `y^2 \neq 0`, the following does not define a valid morphism::

            sage: H([y,y])
            Traceback (most recent call last):
            ...
            ValueError: the proposed morphism does not respect the relations

        This is okay in characteristic two since then `x^2 \neq 0`::

            sage: A2.<x,y> = GradedCommutativeAlgebra(GF(2), degrees=(1,2))
            sage: H2 = Hom(A2,A2)
            sage: H2([y,y])
            Graded Commutative Algebra endomorphism of Graded Commutative Algebra with generators ('x', 'y') in degrees (1, 2) over Finite Field of size 2
              Defn: (x, y) --> (y, y)

        The "nc-relations" `a*b = -b*a`, for `a` and `b` in odd
        degree, are checked first, and we can see this when using more
        generators::

            sage: A.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,2))
            sage: Hom(A,A)([x,z,z])
            Traceback (most recent call last):
            ...
            ValueError: the proposed morphism does not respect the nc-relations

        Other relations::

            sage: B.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,1))
            sage: D = B.quotient(B.ideal(x*y))
            sage: H = Hom(D,D)
            sage: D.inject_variables()
            Defining x, y, z
            sage: H([x,z,z])
            Traceback (most recent call last):
            ...
            ValueError: the proposed morphism does not respect the relations

        The morphisms must respect the differentials, when present::

            sage: B.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,1))
            sage: C = B.cdg_algebra({z: x*y})
            sage: C.inject_variables()
            Defining x, y, z
            sage: H = Hom(C,C)
            sage: H([x,z,z])
            Traceback (most recent call last):
            ...
            ValueError: the proposed morphism does not respect the differentials

        In the case of only one generator, the cover ring is a polynomial ring,
        hence the noncommutativity relations should not be checked::

            sage: A.<e1> = GradedCommutativeAlgebra(QQ)
            sage: A.cover_ring()
            Multivariate Polynomial Ring in e1 over Rational Field
            sage: A.hom([2*e1])
            Graded Commutative Algebra endomorphism of Graded Commutative Algebra with generators ('e1',) in degrees (1,) over Rational Field
              Defn: (e1,) --> (2*e1,)

        """
        domain = parent.domain()
        codomain = parent.codomain()

        # We use check=False here because checking of nc-relations is
        # not implemented in RingHomomorphism_im_gens.__init__.
        # We check these relations below.
        RingHomomorphism_im_gens.__init__(self, parent=parent,
                                          im_gens=im_gens,
                                          check=False)
        self._im_gens = tuple(im_gens)
        # Now check that the relations are respected.
        if check:
            if any(x not in codomain for x in im_gens):
                raise ValueError('not all elements of im_gens are in '
                                 'the codomain')
            R = domain.cover_ring()
            from_R = dict(zip(R.gens(), im_gens))
            if hasattr(R, 'free_algebra'):
                from_free = dict(zip(R.free_algebra().gens(), im_gens))
                # First check the nc-relations: x*y=-y*x for x, y in odd
                # degrees. These are in the form of a dictionary, with
                # typical entry left:right.
                for left in R.relations():
                    zero = left.subs(from_free) - R.relations()[left].subs(from_R)
                    if zero:
                        raise ValueError('the proposed morphism does not respect '
                                         'the nc-relations')
            # Now check any extra relations, including x**2=0 for x in
            # odd degree. These are defined by a list of generators of
            # the defining ideal.
            for g in domain.defining_ideal().gens():
                zero = g.subs(from_R)
                if zero:
                    raise ValueError('the proposed morphism does not respect '
                                     'the relations')
            # If the domain and codomain have differentials, check
            # those, too.
            if (isinstance(domain, DifferentialGCAlgebra)
                    and isinstance(codomain, DifferentialGCAlgebra)):
                dom_diff = domain.differential()
                cod_diff = codomain.differential()
                if any(cod_diff(self(g)) != self(dom_diff(g))
                       for g in domain.gens()):
                    raise ValueError('the proposed morphism does not respect '
                                     'the differentials')

    def _call_(self, x):
        """
        Evaluate this morphism on ``x``.

        INPUT:

        - ``x`` -- an element of the domain

        EXAMPLES::

            sage: A.<x,y> = GradedCommutativeAlgebra(GF(2))
            sage: H = Hom(A,A)
            sage: g = H([y,y])
            sage: g(x)
            y
            sage: g(x*y)
            y^2

            sage: B.<x,y,z> = GradedCommutativeAlgebra(QQ)
            sage: H = Hom(B,B)
            sage: f = H([y,x,x])
            sage: f(x)
            y
            sage: f(3*x*y)
            -3*x*y
            sage: f(y*z)
            0
            sage: f(1)
            1
        """
        codomain = self.codomain()
        result = codomain.zero()
        for mono, coeff in x.dict().items():
            term = prod([gen**y for (y, gen) in zip(mono, self.im_gens())],
                        codomain.one())
            result += coeff * term
        return result

    def is_graded(self, total=False):
        """
        Return ``True`` if this morphism is graded.

        That is, return ``True`` if `f(x)` is zero, or if `f(x)` is
        homogeneous and has the same degree as `x`, for each generator
        `x`.

        INPUT:

        - ``total`` (optional, default ``False``) -- if ``True``, use
          the total degree to determine whether the morphism is graded
          (relevant only in the multigraded case)

        EXAMPLES::

            sage: C.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,1,2))
            sage: H = Hom(C,C)
            sage: H([a, b, a*b + 2*a]).is_graded()
            False
            sage: H([a, b, a*b]).is_graded()
            True

            sage: A.<w,x> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (1,0)))
            sage: B.<y,z> = GradedCommutativeAlgebra(QQ, degrees=((1,0), (0,1)))
            sage: H = Hom(A,B)
            sage: H([y,0]).is_graded()
            True
            sage: H([z,z]).is_graded()
            False
            sage: H([z,z]).is_graded(total=True)
            True
        """
        return all(not y   # zero is always allowed as an image
                   or (y.is_homogeneous()
                       and x.degree(total=total) == y.degree(total=total))
                   for (x, y) in zip(self.domain().gens(), self.im_gens()))

    def _repr_type(self):
        """
        EXAMPLES::

            sage: B.<x,y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1,1))
            sage: C = B.cdg_algebra({z: x*y})
            sage: Hom(B,B)([z,y,x])._repr_type()
            'Graded Commutative Algebra'
            sage: C.inject_variables()
            Defining x, y, z
            sage: Hom(C,C)([x,0,0])._repr_type()
            'Commutative Differential Graded Algebra'
        """
        if (isinstance(self.domain(), DifferentialGCAlgebra)
                and isinstance(self.codomain(), DifferentialGCAlgebra)):
            return "Commutative Differential Graded Algebra"
        return "Graded Commutative Algebra"

    def _repr_defn(self):
        """
        EXAMPLES::

            sage: A.<x,y> = GradedCommutativeAlgebra(QQ)
            sage: Hom(A,A)([y,x])._repr_defn()
            '(x, y) --> (y, x)'
        """
        gens = self.domain().gens()
        return "{} --> {}".format(gens, self._im_gens)


################################################
# Homsets

class GCAlgebraHomset(RingHomset_generic):
    """
    Set of morphisms between two graded commutative algebras.

    .. NOTE::

        Homsets (and thus morphisms) have only been implemented when
        the base fields are the same for the domain and codomain.

    EXAMPLES::

        sage: A.<x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
        sage: H = Hom(A,A)
        sage: H([x,y]) == H.identity()
        True
        sage: H([x,x]) == H.identity()
        False

        sage: A.<w,x> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
        sage: B.<y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1))
        sage: H = Hom(A,B)
        sage: H([y,0])
        Graded Commutative Algebra morphism:
          From: Graded Commutative Algebra with generators ('w', 'x') in degrees (1, 2) over Rational Field
          To:   Graded Commutative Algebra with generators ('y', 'z') in degrees (1, 1) over Rational Field
          Defn: (w, x) --> (y, 0)
        sage: H([y,y*z])
        Graded Commutative Algebra morphism:
          From: Graded Commutative Algebra with generators ('w', 'x') in degrees (1, 2) over Rational Field
          To:   Graded Commutative Algebra with generators ('y', 'z') in degrees (1, 1) over Rational Field
          Defn: (w, x) --> (y, y*z)
    """

    @cached_method
    def zero(self):
        """
        Construct the "zero" morphism of this homset: the map sending each
        generator to zero.

        EXAMPLES::

            sage: A.<x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
            sage: B.<a,b,c> = GradedCommutativeAlgebra(QQ, degrees=(1,1,1))
            sage: zero = Hom(A,B).zero()
            sage: zero(x) == zero(y) == 0
            True
        """
        return GCAlgebraMorphism(self, [self.codomain().zero()]
                                 * self.domain().ngens())

    @cached_method
    def identity(self):
        """
        Construct the identity morphism of this homset.

        EXAMPLES::

            sage: A.<x,y> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
            sage: H = Hom(A,A)
            sage: H([x,y]) == H.identity()
            True
            sage: H([x,x]) == H.identity()
            False
        """
        if self.domain() != self.codomain():
            raise TypeError('identity map is only defined for '
                            'endomorphism sets')
        return GCAlgebraMorphism(self, self.domain().gens())

    def __call__(self, im_gens, check=True):
        """
        Create a homomorphism.

        INPUT:

        - ``im_gens`` -- the images of the generators of the domain

        EXAMPLES::

            sage: A.<w,x> = GradedCommutativeAlgebra(QQ, degrees=(1,2))
            sage: B.<y,z> = GradedCommutativeAlgebra(QQ, degrees=(1,1))
            sage: H = Hom(A,B)
            sage: H([y,0])
            Graded Commutative Algebra morphism:
              From: Graded Commutative Algebra with generators ('w', 'x') in degrees (1, 2) over Rational Field
              To:   Graded Commutative Algebra with generators ('y', 'z') in degrees (1, 1) over Rational Field
              Defn: (w, x) --> (y, 0)
            sage: H([y,y*z])
            Graded Commutative Algebra morphism:
              From: Graded Commutative Algebra with generators ('w', 'x') in degrees (1, 2) over Rational Field
              To:   Graded Commutative Algebra with generators ('y', 'z') in degrees (1, 1) over Rational Field
              Defn: (w, x) --> (y, y*z)
        """
        from sage.categories.map import Map
        if isinstance(im_gens, Map):
            return self._coerce_impl(im_gens)
        else:
            return GCAlgebraMorphism(self, im_gens, check=check)


################################################
# Miscellaneous utility classes and functions

class CohomologyClass(SageObject):
    """
    A class for representing cohomology classes.

    This just has ``_repr_`` and ``_latex_`` methods which put
    brackets around the object's name.

    EXAMPLES::

        sage: from sage.algebras.commutative_dga import CohomologyClass
        sage: CohomologyClass(3)
        [3]
        sage: A.<x,y,z,t> = GradedCommutativeAlgebra(QQ, degrees = (2,2,3,3))
        sage: CohomologyClass(x^2+2*y*z)
        [2*y*z + x^2]
    """
    def __init__(self, x):
        """
        EXAMPLES::

            sage: from sage.algebras.commutative_dga import CohomologyClass
            sage: CohomologyClass(x-2)
            [x - 2]
        """
        self._x = x

    def __hash__(self):
        r"""
        TESTS::

            sage: from sage.algebras.commutative_dga import CohomologyClass
            sage: hash(CohomologyClass(sin)) == hash(sin)
            True
        """
        return hash(self._x)

    def _repr_(self):
        """
        EXAMPLES::

            sage: from sage.algebras.commutative_dga import CohomologyClass
            sage: CohomologyClass(sin)
            [sin]
        """
        return '[{}]'.format(self._x)

    def _latex_(self):
        r"""
        EXAMPLES::

            sage: from sage.algebras.commutative_dga import CohomologyClass
            sage: latex(CohomologyClass(sin))
            \left[ \sin \right]
            sage: latex(CohomologyClass(x^2))
            \left[ x^{2} \right]
        """
        from sage.misc.latex import latex
        return '\\left[ {} \\right]'.format(latex(self._x))

    def representative(self):
        """
        Return the representative of ``self``.

        EXAMPLES::

            sage: from sage.algebras.commutative_dga import CohomologyClass
            sage: x = CohomologyClass(sin)
            sage: x.representative() == sin
            True
        """
        return self._x


@cached_function
def exterior_algebra_basis(n, degrees):
    """
    Basis of an exterior algebra in degree ``n``, where the
    generators are in degrees ``degrees``.

    INPUT:

    - ``n`` - integer
    - ``degrees`` - iterable of integers

    Return list of lists, each list representing exponents for the
    corresponding generators. (So each list consists of 0's and 1's.)

    EXAMPLES::

        sage: from sage.algebras.commutative_dga import exterior_algebra_basis
        sage: exterior_algebra_basis(1, (1,3,1))
        [[0, 0, 1], [1, 0, 0]]
        sage: exterior_algebra_basis(4, (1,3,1))
        [[0, 1, 1], [1, 1, 0]]
        sage: exterior_algebra_basis(10, (1,5,1,1))
        []
    """
    if n == 0:
        return [[0 for j in degrees]]
    if len(degrees) == 1:
        if degrees[0] == n:
            return [[1]]
        else:
            return []
    if not degrees:
        return []
    if min(degrees) > n:
        return []
    if sum(degrees) < n:
        return []
    if sum(degrees) == n:
        return [[1 for j in degrees]]
    i = len(degrees) // 2
    res = []
    for j in range(n + 1):
        v1 = exterior_algebra_basis(j, degrees[:i])
        v2 = exterior_algebra_basis(n - j, degrees[i:])
        res += [l1 + l2 for l1 in v1 for l2 in v2]
    res.sort()
    return res


def total_degree(deg):
    """
    Total degree of ``deg``.

    INPUT:

    - ``deg`` - an element of a free abelian group.

    In fact, ``deg`` could be an integer, a Python int, a list, a
    tuple, a vector, etc. This function returns the sum of the
    components of ``deg``.

    EXAMPLES::

        sage: from sage.algebras.commutative_dga import total_degree
        sage: total_degree(12)
        12
        sage: total_degree(range(5))
        10
        sage: total_degree(vector(range(5)))
        10
        sage: G = AdditiveAbelianGroup((0,0))
        sage: x = G.gen(0); y = G.gen(1)
        sage: 3*x+4*y
        (3, 4)
        sage: total_degree(3*x+4*y)
        7
    """
    if deg in ZZ:
        return deg
    return sum(deg)
