Computing “Small” 1–Homological Models for CDGAs^{⋆}

CHATA group of Seville^{⋆⋆}

Universidad de Sevilla, Depto. de Matemática Aplicada I, Avda. Reina Mercedes, 41012 Sevilla, Spain, e-mails: real@cica.es

Abstract. We use a homological perturbation machinery specific for the algebra category [13,3] to give an algorithm for computing the differential structure of a small 1–homological model for commutative differential graded algebras (briefly, CDGAs). The complexity of the process is studied and a computer package in Mathematica is described for determining such models.

1 Introduction

The description of efficient algorithms for homological computation can be considered as a very important question in Homological Algebra. These processes can be mainly used in the resolution of problems on Algebraic Topology; but this subject also impinges directly on the development of not so close areas as Combinatorial Designs, Code Theory, Concurrency Theory or Cohomological Physics.

Our goal here is to design an algorithm for computing the algebra 1– homology [10] of commutative differential graded algebras (or, briefly CDGAs). More precisely, starting from a finite CDGA A, we here establish a process for obtaining an “economical” 1–homological model hBA (in the sense that the number of algebra generators of hBA is fewer than that of the reduced bar construction B̄(A) of A [10]). The following step in order to get the 1– homology of A is the computation of the homology groups of hBA, which can be reduced to a simple problem of Linear Algebra (see [11] for a complete explanation of this method).

Our main technique is the homological perturbation machinery [6,7,9]. Homological Perturbation Theory is often used to replace given chain complexes by other homotopic, smaller and more readily computable chain complexes. An essential notion in this theory is that of contraction. A contraction c = (f, g, ϕ) between two differential graded modules (or, briefly, DG– modules) (N, d_{N}) and (M, d_{M}) is an especial homotopy equivalence between

⋆ Authors are partially supported by the PAICYT research project FQM–0143 from Junta de Andalucía and the DGES–SEUID research project PB98–1621–C02–02 from Education and Science Ministry (Spain).

⋆⋆ Computational Homological Algebra & Algebraic Topology and Applications group: Álvarez V., Armario J.A., Frau M.D., González–Díaz R., Jiménez M.J., Real P. and Silva B.

both modules such that the corresponding homology groups are isomorphic. The morphisms f, g and ϕ are called projection, inclusion and homotopy of the contraction, respectively. The Basic Perturbation Lemma (or, briefly BPL) is the heart of this theory and states that given a contraction c = (f, g, ϕ), and a perturbation δ of d_{N} (that is, (d_{N} + δ)^{2} = 0), then there exists a new contraction c_{δ} = (f_{δ}, g_{δ}, ϕ_{δ}) from (N, d_{N} + δ) to (M, d_{M} + d_{δ}), verifying that

f_{δ} = f(1 − δΣ_{c}^{δ}ϕ) , g_{δ} = Σ_{c}^{δ}g , ϕ_{δ} = Σ_{c}^{δ}ϕ
d_{δ} = fδΣ_{c}^{δ}g ,  (1)

where Σ_{c}^{δ} = ∑_{i≥0}(−1)^{i} (ϕδ)^{i} = 1 − ϕδ + ϕδϕδ − ⋯ + (−1)^{i}(ϕδ)^{i} + · · ·.

It is necessary to emphasize that a nilpotent condition for the composition δϕ is required for guaranteeing the finiteness of the formulas.

The basic idea we use in this paper is the establishment, via composition, tensor product or perturbation of contractions, of an explicit contraction from an initial DG–module N to a free DG–module M of finite type, so that the homology of N is computable from that of M.

Working in the context of CDGAs, Homological Perturbation Theory supplies immediately a general algorithm computing the 1–homology of these objects at graded module level. Nevertheless, this process, already sketched by Lambe in [12], bears high computational charges and actually restricts its application to the low dimensional homological calculus [1]).

Our first goal consists in refining this algorithm, taking advantage of the multiplicative structures [2]. More precisely, we use a particular algebra perturbation machinery: the semifull algebra perturbation lemma [13,3]. In our method Alg1, the input is a CDGA A given in the form of a “twisted” tensor product of n exterior and polynomial algebras and the output is a contraction c_{δ} (produced via a perturbation of a contraction c) from the reduced bar construction B̄(A) to a smaller differential graded algebra hBA, which is free and of finite type as graded module. In this case, we say that the pair {c_{δ}, hBA} (or, simply, hBA) is a 1–homological model of A.

In order to improve the efficiency of the method, it is possible to take advantage of the fact that the differential d_{hBA} of hBA is a derivation, that is, a morphism compatible with the product of the homological model. This feature implies that it is only necessary to know the value of this morphism applied upon the generators of the model (notice that there are n algebra generators). This is a substantial improvement in the computation of the differential on the small model hBA.

In spite of this improvement, the complexity for evaluating the morphism d_{hBA} on an algebra generator of hBA is enormous, since the differential d_{hBA} follows the formula (1) and the homotopy ϕ of c has an essentially exponential nature not only in time but also in space.

We develop here some techniques, which comprise what we call inversion theory and whose first origin can be found at [13]. As a consequence, we refine the formula for ϕ, which is involved in the evaluation of d_{hBA} over the generators of the small model. This study is based on the observations that the evaluation of the projection f, over certain elements (those “with inversions”) is always null and that, therefore, a non-negligible amount of terms in the formula of the morphism ϕ can be eliminated in the composition f(δϕ)^{i}g, appearing in the formula (1). We derive, in such a way, an upgraded algorithm Alg2.

An analysis of the complexity of these two methods for computing the differential structure of the small homological model hBA is done and a comparison between Alg1 and Alg2 is given.

We also give several examples illustrating the implementation done of Alg2 using MATHEMATICA 3.0.

2 Preliminaries

Although relevant notions of Homological Algebra are explained through the exposition of this paper, most common concepts are not explicitly given (they can be found, for instance, in [10] or [15]).

Let Λ be a commutative ring with non zero unit, which will be considered the ground ring. A DGA–module (M, d_{M}, ξ_{M}, η_{M}) is a module endowed with a graduation, that is, M = ⊕_{n∈IN}M_{n}; a differential, d_{M} : M_{∗} → M_{∗−1} which decreases the degree by one and verifies that d2_{M} = 0; an augmentation, ξ_{M} : M → Λ with ξ_{M}d_{1} = 0, and a coaugmentation, η : Λ → M with ξ_{M}η_{M} = 1_{Λ}. We will keep Koszul conventions. The homology of a DG– module M, is a graded module H_{∗}(M), where H_{n}(M) = Ker d_{n}/Im d_{n+1}. But we are specially interested on CDGAs, (A, d_{A}, ∗_{A}, ξ_{A}, η_{A}) which are DGA– modules endowed with a product, ∗_{A} that is commutative in a graded sense. A morphism δ : A → A which decreases the degree by one, is a derivation if δ∗_{A} = ∗_{A}(1 ⊗ δ + δ ⊗ 1). Three particular algebras are of especial interest in the development of this paper, which are the exterior, polynomial and divided power algebras. Let n be a fixed integer. The exterior algebra E(x, 2n + 1) is the graded algebra with generators 1 and x of degrees 0 and 2n + 1, respectively; and trivial product (that is, x · x = 0 and x · 1 = x). The polynomial algebra P (y, 2n) consists in the graded algebra with generators 1 of degree 0 and y of degree 2n; the product is given by the usual one on polynomials, i.e.: y^{i} · y^{j} = y^{i+j}, for non negative integers i and j. Finally, the divided power algebra Γ (y, 2n) is the graded algebra with generators 1 and y ( y = y^{(1)}) of respective degrees 0 and 2n; and product defined by the rules

y^{(i)} · y^{(j)} = ( \begin{matrix}i + j \\ i \end{matrix} ) y^{(i+j)}, being i and j non–negative integers. Each one

of these three types of algebras can be considered as a CDGA with trivial differential.

Now, we recall an standard algebraic tool which allows one to preserve the product structure of the initial CDGA through the process of homological computation.

The reduced bar construction [10] associated to a CDGA A is defined as the differential graded module B̄(A):

B̄(A) = Λ ⊕ Ā ⊕ (Ā ⊗ Ā) ⊕ ⋯ ⊕ (Ā ⊗ ⋯ ⊗ Ā) ⊕ ⋯

where Ā_{n} = A_{n} if n ≥ 1, Ā_{0} = 0.

An element from B̄(A) is denoted by ā = [a_{1}| ⋯ |a_{n}]. There is a tensor graduation | |_{t} given by |[a_{1}| ⋯ |a_{n}]|_{t} = ∑_{i=1}^{n} |a_{i}|, as well as a simplicial graduation | |_{s}, which is defined by |ā|_{s} = |[a_{1}| ⋯ |a_{n}] |_{s} = n. The total degree of ā is given by |ā| = |ā|_{t} + |ā|_{s}.

The total differential is given by the sum d = d_{t} + d_{s} of the tensor and the simplicial differential. The tensor differential is given by

d_{t}[a_{1}| ⋯ |a_{n}] = − ∑_{i=1}^{n}(−1)^{|[a_{1}|···|a_{i−1}]|}[a_{1}| ⋯ |d_{A}a_{i}| ⋯ |a_{n}] .

The simplicial differential acts cutting down the simplicial degree by using the product given on A.

When the algebra A is commutative, it is possible to define a multiplicative structure upon B̄(A) (via an operator called shuffle product), so that the reduced bar construction also becomes a CDGA.

Given two non–negative integers p and q , a (p, q)-shuffle is defined as a permutation π of the set {0, …, p + q − 1} such that π(i) < π(j) whenever 0 ≤ i < j ≤ p − 1 or p ≤ i < j ≤ p + q − 1. This way, one can establish two sequences of integers:

α_{i} = π(i − 1), i = 1, …, p; β_{j} = π(p + j − 1), j = 1, …, q.

We will refer to a (p, q)–shuffle as a pair (α, β), which denotes both sequences α_{i} and β_{j}.

Let us observe that there are ( \begin{matrix}p + q \\ p \end{matrix} ) different (p, q)–shuffles.

So, given a CDGA A, the shuffle product ⋆ : B̄(A) ⊗ B̄(A) ⟶ B̄(A), is defined by:

[a_{1}| ⋯ |a_{p}] ⋆ [b_{1}| ⋯ |b_{q}] = ∑_{(α,β)}(−1)^{ε(π,a,b)}[c_{0}| ⋯ |c_{p+q−1}] ;

where (c_{α_{1}}, …, c_{α_{p}}, c_{β_{1}}, …, c_{β_{q}}) = (a_{1}, …, a_{p}, b_{1}, … b_{q}) with (α, β) in the set of (p, q)–shuffles and the exponent is

ε(π, a, b) = ∑_{π(i)>π(p+j)} |[a_{i}]||[b_{j}]| .

Being n a non–negative integer, the n–homology of a CDGA A (see [10]) consists in the homology groups of the iterated reduced bar construction B̄^{n}(A) = B̄(B̄^{n−1}(A)), being B̄^{0}(A) = A.

Let {A_{i}}_{i∈I} be a set of CDGAs. A twisted tensor product (briefly, T T P) ˜⊗_{i∈I}^{ρ}A_{i} is a CDGA satisfying the following conditions: i) ˜⊗_{i∈I}^{ρ}A_{i} coincides with the tensor product ⊗_{i∈I}A_{i} as a graded algebra. ii) The differential operator consists in the sum of the differential of the

banal tensor product and a perturbation ρ, which is a derivation.

A contraction c : {N, M, f, g, ϕ} [4,9], also denoted by (f, g, ϕ) : N ⇒^{c} M, from a DG–module (N, d_{N}) to a DG–module (M, d_{M}) consists in a homotopy equivalence determined by three morphisms f, g and ϕ; being f : N_{∗} → M_{∗} (projection) and g : M_{∗} → N_{∗} (inclusion) two DG–module morphisms and ϕ : N_{∗} → N_{∗+1} a homotopy operator. Moreover, these data are required to satisfy the following rules:

fg = 1_{M} , ϕd_{N} + d_{N}ϕ + gf = 1_{N} , fϕ = 0 , ϕg = 0 , ϕϕ = 0 .

There are two basic operations between contractions which give place to new contractions: tensor product and composition of contractions.

In this paper we use a particular type of contraction between CDGAs. Given two CDGAs A and A′, the semifull algebra contraction (f, g, ϕ) : A ⇒ A′ [13,3] consists of an inclusion g that is a morphism of CDGAs, a quasi– algebra projection f and a quasi–algebra homotopy ϕ. We recall that

1. The projection f is said to be a quasi–algebra projection whenever the following conditions hold:

f(ϕ ∗_{A} ϕ) = 0, f(ϕ ∗_{A} g) = 0, f(g ∗_{A} ϕ) = 0 .  (2)

2. The homotopy operator ϕ is said to be a quasi–algebra homotopy if

ϕ(ϕ ∗_{A} ϕ) = 0, ϕ(ϕ ∗_{A} g) = 0, ϕ(g ∗_{A} ϕ) = 0 .  (3)

All the algebra contractions appearing in the process we are interested are of this kind and the class of all semifull algebra contractions is closed under composition and tensor product of contractions. Moreover, this class is closed under perturbation.

Theorem 1. (SF–APL) ([13])

Let c : {N, M, f, g, ϕ} be a semifull algebra contraction and δ : N → N be a perturbation of d_{N}, which is a derivation too. Then, the perturbed contraction c_{δ} given in BPL, is a new semifull algebra contraction.

3 Computability of the 1–Homology of CDGAs. First Algorithm

Here we recall the algorithm described in [2] for the computation of 1– homology of CDGAs.

It is commonly known that every CDGA A “factors”, up to homotopy equivalence, into a tensor product of exterior and polynomial algebras endowed with a differential–derivation; in the sense that there exists an homomorphism connecting both structures, which induces an isomorphism in homology.

In fact, our input is a TTP of algebras A = ˜⊗_{i∈I}^{ρ}A_{i} where I denotes a finite set of indices, ρ is a differential–derivation and A_{i} an exterior or a polynomial algebra, for every i. In our algorithmic approach, we encode A by

1. a sequence of non–negative integers n_{1} ≤ n_{2} ≤ ⋯ ≤ n_{k}, such that n_{i} represents the degree of the algebra generator x_{i} of A_{i};

2. a k–vector v̄ = (v_{1}, v_{2}, …, v_{k}), such that v_{i} is ρ(x_{i}) for all i.

Of course, at least the first component of the vector v̄ is zero.

The principal goal is to obtain a “chain” of semifull algebra contractions starting at the reduced bar construction B̄(A) and ending up at a smaller free (as a module) CDGA. In that way, we will determine a 1–homological model for A.

Now, we consider the following three semifull algebra contractions which are used, in a first step, to find the structure of graded module of a homological model for the CDGA A:

– The contraction defined in [4,5] from B̄(A ⊗ A′) to B̄(A) ⊗ B̄(A′), where A and A′ are two CDGAs.

C_{B̄⊗} : {B̄(A ⊗ A′), B̄(A) ⊗ B̄(A′), f_{B̄⊗}, g_{B̄⊗}, ϕ_{B̄⊗}};

• f_{B̄⊗}[a_{1} ⊗ a′_{1}| ⋯ |a_{n} ⊗ a′_{n}]

= ∑_{i=0}^{n} ξ_{A}(a_{i+1} ⋯ a_{n})ξ_{A′}(a′_{1} ⋯ a′_{i})[a_{1}| ⋯ |a_{i}] ⊗ [a′_{i+1}| ⋯ |a′_{n}] .

• g_{B̄⊗}([a_{1}| ⋯ |a_{n}] ⊗ [a′_{1}| ⋯ |a′_{m}])

= [a_{1}| ⋯ |a_{n}] ⋆ [a′_{1}| ⋯ |a′_{m}] ,  (4)

with [a_{1}| ⋯ |a_{n}] ∈ B̄(A) , [a′_{1}| ⋯ |a′_{m}] ∈ B̄(A′) ;

[a_{1}| ⋯ |a_{n}] = [a_{1} ⊗θ′| ⋯ |a_{n} ⊗θ′] , [a′_{1}| ⋯ |a′_{n}] = [θ ⊗a′_{1}| ⋯ |θ ⊗a′_{n}] .

• up to sign, ϕ_{B̄⊗}([a_{1} ⊗ a′_{1}| ⋯ |a_{n} ⊗ a′_{n}])

\begin{aligned}= ∑_{0≤p≤n−q−1≤n−1} & ±ξ_{A}(a_{n−q+1} ⋯ a_{n})[a_{1} ⊗ a′_{1}| ⋯ |a_{n̄−1} ⊗ a′_{n̄−1} \\ & |(a′_{n̄} ∗_{A′} ⋯ ∗_{A′} a′_{n−q})|c_{0}| ⋯ |c_{p+q}] , \end{aligned} (5)

where n̄ = n−p−q; (c_{π(0)}, …, c_{π(p+q)}) = (an̄, …, a_{n−q}, a′_{n−q+1}, … a′_{n});

π is a (p + 1, q)–shuffle and 0 ≤ p ≤ n − q − 1 ≤ n − 1.

Notice the exponential nature in complexity of g_{B̄⊗} and ϕ_{B̄⊗} since the shuffle product is involved in both formulas.

Given a tensor product ⊗_{i∈I}A_{i} of CDGAs, a contraction from B̄(⊗_{i∈I}A_{i}) to ⊗_{i∈I} B̄(A_{i}) is easily determined, by applying C_{B̄⊗} several times in a suitable way. This new contraction is also denoted by C_{B̄⊗}.

– The isomorphism of DGAs (therefore, a contraction)

C_{B̄E} : \{B̄(E(u, 2n + 1)), Γ (\underline{u}, 2n + 2), f_{B̄E}, g_{B̄E}, 0\}

described in [5], where

f_{B̄E}([u| ⋯^{m times} |u]) = \underline{u}^{(m)}; g_{B̄E}(\underline{u}^{(m)}) = [u| ⋯^{m times} |u] .

– The contraction

C_{B̄P} : \{B̄(P (v, 2n)), E(\underline{v}, 2n + 1), f_{B̄P} , g_{B̄P} , ϕ_{B̄P} \}

stated in [5], where

f_{B̄P} ([v^{r}] = \{ \begin{matrix}0 & if r ≠ 1 \\ \underline{v} & if r = 1 \end{matrix} ; f_{B̄P} ([v^{r_{1}}| ⋯ |v^{rm}]) = 0

g_{B̄P} (\underline{v}) = [v]; ϕ_{B̄P} ([v^{r_{1}}| ⋯ |v^{rm}]) = [v|v^{r_{1}−1}| ⋯ |v^{rm}] .

All the previous contractions have already been deeper described for decades, so we will not explain them further.

Thanks to these three contractions, it is possible to establish, by composition and tensor product of contractions, the following semifull algebra contraction C_{0} = (f, g, ϕ):

B̄(⊗_{i∈I}A_{i}) ⇒ ⊗_{i∈I} B̄(A_{i}) ⇒ ⊗_{i∈I}hBA_{i} ,

where hBA_{i} represents an exterior or a divided power algebra with generator \underline{x}_{i}, depending on whether A_{i} is a polynomial or an exterior algebra with generator x_{i}.

The next step is perturbing C_{0}, in order to obtain the differential structure of the 1–homological model for the TTP ˜⊗_{i∈I}^{ρ}A_{i}. The perturbation ρ produces a perturbation–derivation δ onto the tensor differential of B̄(⊗_{i∈I}A_{i}):

δ([a_{1}| ⋯ |a_{n}]) = ∑_{i=1}^{n}(−1)^{|[a_{1}|···|a_{i−1}]|}[a_{1}| ⋯ |ρ(a_{i})| ⋯ |a_{n}] .

Now, by applying SF–APL, a new semifull algebra contraction (f_{δ}, g_{δ}, ϕ_{δ}) is constructed:

B̄( ˜⊗_{i∈I}^{ρ}A_{i}) ⇒^{(C_{0})_{δ}} (⊗_{i∈I}hBA_{i}, d_{δ}) ,

where the differential d_{δ} is determined by the perturbation process (BPL). That means that hBA = ⊗_{i∈I}(hBA_{i}, d_{δ}) is a 1–homological model of A = ˜⊗_{i∈I}A_{i}. Let us emphasize that BPL gives finite formulas. Indeed, this is a consequence of two facts: the perturbation δ does not change the simplicial degree and ϕ increases this degree.

Procedure 1. Algorithm Alg1.

Input: A finite CDGA A: ((n_{1}, …, n_{k}), (v_{1}, …, v_{k})).

w_{1} = 0, for i = 2 to k

w_{i} = d_{δ}(\underline{x}_{i}), where x_{i} is the algebra generator of degree n_{i} endfor

Output: ((n_{1} + 1, …, n_{k} + 1), (w_{1}, …, w_{k}))

a 1–homological model of the CDGA ⊗_{i=1,...,k}^{ρ}A_{i}, being A_{i} the exterior algebra E(x_{i}, n_{i}), if n_{i} is odd and P (x_{i}, n_{i}) if n_{i} is even.

Of course, the first components of the vector v̄ must be zero, because they correspond to the image by ρ over the algebra generators with lowest degree.

Moreover, it can be described a general algorithm for computing the 1– homology of CDGAs. Clearly, the homology of the homological model obtained can be computed using an algorithm based upon the establishment of the Smith’s normal form of the matrices representing the differentials at each degree [14,11].

The computational cost to construct the contraction (C_{0})_{δ} is high: notice that both the inclusion and homotopy operators of the contraction C_{B̄⊗} give an answer in exponential time, when evaluated on each element. In fact, the formula of the differential operator d_{δ} produced by the homological perturbation machinery is given by:

d_{δ} = f ∘ δ ∘ (1 − ϕ ∘ δ + ϕ ∘ δ ∘ ϕ ∘ δ − ⋯) ∘ g.  (6)

Attending to the previous remarks about the complexity on the evaluation of morphisms, a first impression is that the evaluation of d_{δ} upon any element becomes in general a process of exponential nature.

In spite of this, it is possible to take advantage of d_{δ} being a derivation (that is, a morphism compatible with the product of the homological model), in order to improve the complexity problem: indeed, the fact that d_{δ} is a derivation implies that it is only necessary to know the evaluation of this morphism on the generators of the model (notice that there are so many generators as the cardinal of the set of indices I indicates). This is an enormous improvement in the computation of the differential on the small model. Summing up, computing d_{δ} on an algebra generator is extremely time-consuming. We would like to go further in the simplification of this computation, and this is what has provided inspiration for the developing of the following section.

4 Inversion Theory

The responsible for the high complexity in the evaluation of d_{δ} is the homotopy operator, ϕ, due, essentially, to the shuffles that are involved in the formulas of ϕ_{B⊗} and g_{B⊗}. We intend to eliminate these shuffles, and, for this aim, we define the concept of inversion.

Definition 2. Let A and A′ be CDGAs and let us consider a non degenerate homogeneous element [a_{1} ⊗ a′_{1}|a_{2} ⊗ a′_{2}| ⋯ |a_{n} ⊗ a′_{n}] from B̄(A ⊗ A′). We say that a component θ ⊗ a′_{i} from that element, is responsible for an inversion, if there exists a j > i with a_{j} ≠ θ (where θ is the unit of A). In this sense, such an element presents k inversions if there exist k components responsible for an inversion.

We will say that a general element from B̄(A ⊗ A′) has k inversions, if it is a sum of elements with at least k inversions each one of them.

Let us consider the contraction C_{B̄⊗}.

(f_{B̄⊗}, g_{B̄⊗}, ϕ_{B̄⊗}) : B̄(A ⊗ A′) ⇒ B̄(A) ⊗ B̄(A′)

We analyze the behaviour of the component morphisms with respect to inversions. For this purpose, we do not take care on signs in the referred formulas.

– The evaluation of f_{B̄⊗} over an element with at least one inversion, is null.

– The injection g_{B̄⊗} (4), applied to [a_{1}| ⋯ |a_{n}] ⊗ [a′_{1}| ⋯ |a′_{m}], produces:

• a unique term with no inversions (that one which comes from juxtaposition),

• n terms with one inversion,

• ( \begin{matrix}n + m \\ n \end{matrix} ) − n − 1 terms with more than one inversion.

– As for the homotopy operator ϕ_{B̄⊗} (5), we can state that the evaluation of ϕ_{B̄⊗} over an homogenous element from B̄(A ⊗ A′) gives place to a sum of elements which, if not degenerate, have at least one more inversion than the original one. Notice that an inversion is produced by the component (a′_{n̄}∗_{A′} ⋯∗_{A′} a′_{n−q}), which is always on the left side of those an̄, …, a_{n−q}.

Let us consider the contraction which provides a homological model for a tensor product of two CDGAs, A and A′:

(f, g, ϕ) : B̄(A ⊗ A′) ⇒ B̄(A) ⊗ B̄(A′) ⇒ hBA ⊗ hBA′  (7)

where

f = (f_{B̄A} ⊗ f_{B̄A′})f_{B̄⊗},
g = g_{B̄⊗}(g_{B̄A} ⊗ g_{B̄A′})
ϕ = ϕ_{B̄⊗} + g_{B̄⊗}(ϕ_{B̄A} ⊗ g_{B̄A′}f_{B̄A′} + 1_{B̄A} ⊗ ϕ_{B̄A′})f_{B̄⊗}

Let us notice that the evaluation of f over an element with an inversion is also null, since the first morphism applied is f_{B̄⊗}.

On the other hand, the morphism g_{B̄⊗}, which intervenes in the formula of ϕ generates a sum of elements with at least one inversion, except for that one obtained just by juxtaposition.

Now we assume that there is a perturbation ρ of the tensor product of the algebras A and A′, A ⊗ A′. This perturbation induces, in a natural way, a perturbation δ on B̄(A ⊗ A′). Now we analyze the behaviour of such a morphism with respect to inversions.

Lemma 3. Let us consider a perturbation δ for B̄(A ⊗ A′) induced by an algebra perturbation ρ for A ⊗ A′, such that ρ(A) ⊂ A. The action of δ over an homogeneous element from B̄(A⊗A′) with k inversions, produces an element with at least k − 1 inversions.

Proof. Notice that a component of an homogeneous element from B̄(A ⊗ A′) is responsible for, at most, one inversion and that δ acts only on a component of the element at each term of the resultant sum. ⊓ ⊔

Attending to the basic perturbation lemma, one can obtain from the contraction (7), a new contraction starting from B̄(A ˜⊗^{ρ}A′):

(f_{δ}, g_{δ}, ϕ_{δ}) : B̄(A ˜⊗^{ρ}A′) ⇒ (hBA ⊗ hBA′, d_{δ})  (8)

We recall the formula for d_{δ}:

d_{δ} = f ∘ δ ∘ (1 − ϕ ∘ δ + ϕ ∘ δ ∘ ϕ ∘ δ − ⋯) ∘ g.  (9)

We can observe that f is the last morphism applied in the formula. If at any stage, the element y obtained by applying ϕ, has more than one inversion, then δ(y) will have at least one inversion. This way, each time we go on applying δ ∘ ϕ, we obtain an element with at least one inversion, and, therefore, the final evaluation by f is null. This means that we only have to consider summands of ϕ which produce elements with, at most, one inversion.

In consequence, we can establish the following theorem by which we reduce considerably the complexity in the calculus of d_{δ}.

Theorem 4. When d_{δ} is applied to a generator from the homological model for a CDGA A ⊗ A′, the formula for ϕ (which is involved in the definition of d_{δ}) can be reduced to the following one:

ϕ = ϕ̄_{B̄⊗} + ḡ_{B̄⊗}(ϕ_{B̄A} ⊗ g_{B̄A′}f_{B̄A′} + 1 ⊗ ϕ_{B̄A′})f_{B̄⊗},

where

– ϕ̄_{B̄⊗}([a_{1} ⊗ a′_{1}| ⋯ |a_{n} ⊗ a′_{n}])

\begin{aligned}= & ∑_{0≤p≤n−q−1≤n−1} & (−1)^{φ(n,p,q)}ξ_{A}(a_{n−q+1} ⋯ a_{n})[a_{1} ⊗ a′_{1}| ⋯ |a_{n̄−1} ⊗ a′_{n̄−1} \\ & & |(a′_{n̄} ∗_{A′} ⋯ ∗_{A′} a′_{n−q})|an̄| ⋯ |a_{n−q}|a′_{n−q+1}| ⋯ |a′_{n}] \end{aligned}

being n̄ = n − p − q and
φ(n, p, q) = n̄ − 1 + |[a_{1}| ⋯ |a_{n̄−1}]|_{t} + |[a′_{1}| ⋯ |a′_{n−q}]|_{t}

+ ∑_{k=0}^{p} ∑_{ℓ=0}^{k} |a_{n−q−k}| · |a′_{n−q−ℓ}| .

– ḡ_{B̄⊗}([a_{1}| ⋯ |a_{n}] ⊗ [a′_{1}| ⋯ |a′_{m}])

= [a_{1}| ⋯ |a_{n}|a′_{1}| ⋯ |a′_{m}]

+ ∑_{i=1}^{n−1}(−1)^{|[a_{i+1}|···|a_{n}]||a′_{1}|} [a_{1}| ⋯ |a_{i}|a′_{1}|a_{i+1}| ⋯ |a_{n}|a′_{2}| ⋯ |a′_{m}]

+(−1)^{|a′_{1}||[a_{1}|···|a_{n}]|} [a′_{1}|a_{1}| ⋯ |a_{n}|a′_{2}| ⋯ |a′_{m}] .

Notice that, now, the number of terms in the formula above for ϕ_{B̄⊗} is

∑_{q=0}^{n−1} ∑_{p=0}^{n−q−1} 1 = \frac{n^{2} + n}{2} ,

in contrast to the original number of terms:

∑_{q=0}^{n−1} ∑_{p=0}^{n−q−1} ( \begin{matrix}p + q + 1 \\ q \end{matrix} ) = 2^{n+1} − n − 2 .

On the other hand, the formula for g_{B̄⊗} is reduced to n terms in the sum

instead of ( \begin{matrix}m + n \\ n \end{matrix} ).

This theorem is easy to generalize, by induction, to the general case of a TTP of CDGAs ˜⊗_{i∈I}^{ρ}A_{i} with I = {1, …, n}, where A_{i} is an exterior or a polynomial algebra with generator x_{i} and |x_{i}| ≤ |x_{i+1}|. Then, as we saw in section 3, the following semifull algebra contraction, C_{n}, can be established:

(f_{n}, g_{n}, ϕ_{n}) : B̄(⊗_{i=1}^{n}A_{i}) ⇒ ⊗_{i=1}^{n}B̄(A_{i}) ⇒ ⊗_{i=1}^{n}hBA_{i}  (10)

where hBA_{i} is a polynomial or a divided power algebra.

The key to understand the generalization is the fact that the inversions in B̄(⊗_{i=1}^{n}A_{i}) are those of the last tensor product, as they were defined at the beginning of the section (with A = ⊗_{i=1}^{n−1}A_{i} and A′ = A_{n}) besides those of ⊗_{i=1}^{n−1}A_{i} = (⊗_{i=1}^{n−2}A_{i}) ⊗ A_{n−1} respect to the last tensor product; and so on.

Summing up, we obtain an algorithm Alg2 having the same input and output that the Algorithm Alg1 of the last section, but speeding up the steps concerning the evaluation of d_{δ} on the algebra generators.

Procedure 2. Algorithm Alg2.

Input: A finite CDGA A: ((n_{1}, …, n_{k}), (v_{1}, …, v_{k})).

w_{1} = 0, for i = 2 to k

w_{i} = d_{δ}(\underline{x}_{i}), where x_{i} is the algebra generator of degree n_{i} (taking advantage of inversion theory)

endfor

Output: ((n_{1} + 1, …, n_{k} + 1), (w_{1}, …, w_{k}))

a 1–homological model of the CDGA ˜⊗_{i=1,...,k}^{ρ}A_{i}, being A_{i} the exterior algebra E(x_{i}, n_{i}), if n_{i} is odd, and the polynomial algebra P (x_{i}, n_{i}), if n_{i} is even.

5 Complexity

In this section, we give a comparison on the algorithms Alg1 and Alg2 from the point of view of its complexity. We are mainly interested in measuring the efficiency of the corresponding steps concerning the evaluation of the differential d_{δ} on the algebra generators of the small model. We consider the degree of the algebra generator as the size of an instance. We take as elementary operations those ones generating each homogeneous term produced by the different morphisms. We treat here the worst-case complexity.

We calculate the total number of elementary operations needed for computing d_{δ} on a generator \underline{x}_{k} of degree k, for both Alg1 and Alg2. We have that this number for Alg1 is

∑_{i=0}^{⌊k/k_{0}+1⌋}(i! r^{i} + ((i + 1)! + (i + 2)! )r^{i+1}) (∏_{j=1}^{i}(2^{j+1} − j − 2)) ,

and for Alg2 is

∑_{i=0}^{⌊k/k_{0}+1⌋}(r^{i} + (i + 3)r^{i+1}) (∏_{j=1}^{i} \frac{j^{2} + j}{2} ) ,

where k_{0} = min_{1≤i≤n}|x_{i}| and r is the maximum number of summands given by ρ(x_{i}), where x_{i} ranges over all the algebra generators of A.

In the following table, the required time for computing d_{δ}(\underline{x}_{k}) is showed, supposing that our computer does 10^{6} elementary operations per second. Let us denote s = ⌊k/k_{0} + 1⌋. Notice that, for example, s = 5 means that if k_{0} = 10, the degrees of the algebra generators ranges over the set {10, 11, …, 54, 55}.

Table 1. Required time

in Alg1  in Alg2
s = 3; r = 2 0.1 sec.  0.002 sec.
s = 3; r = 3 0.5 sec.  0.009 sec.
s = 4; r = 2 31.29 sec. 0.04 sec.
s = 5; r = 3 3.19 days 17.6 sec.
s = 6; r = 2 1.45 years 1.17 min
s = 6; r = 3 24.75 years 19.56 min

6 Implementation Performance

The algorithm Alg2 has been implemented. The user supplies an encoding of a finite CDGA in the form of a twisted tensor product of exterior and polynomial algebras to the programme, which computes an encoding of a small 1–homological model of this algebra.

This programme is written in Mathematica 3.0, consisting in 300 lines of code and 10 elementary functions.

In order to give some indication of the implementation, we report on the time taken to compute 1–homological models for certain CDGAs:

1. E(x_{1}, x_{2}, x_{3}; 1) ⊗ P (x_{4}, x_{5}; 2) ⊗ E(x_{6}; 3) ⊗ P (x_{7}; 4) ⊗ P (x_{8}; 6).

Input: ((1, 1, 1, 2, 2, 3, 4, 6),

(0, 0, 0, x_{1} − x_{2}, x_{2}, x_{1}x_{2}, x_{2}x_{4} + x_{1}x_{5} + x_{1}x_{2}x_{3}, x_{1}x_{2}x_{6})).

Output: ((2, 2, 2, 3, 3, 4, 5, 7), (0, 0, 0, \underline{x}_{1} − \underline{x}_{2}, \underline{x}_{2}, 0, \underline{x}_{1}\underline{x}_{2} − 2\underline{x}2_{2}, 0))

Time: d_{δ}(\underline{x}_{4}) in 0.55 sec.

d_{δ}(\underline{x}_{5}) in 0.27 sec.
d_{δ}(\underline{x}_{6}) in 0.33 sec.
d_{δ}(\underline{x}_{7}) in 2.14 sec.
d_{δ}(\underline{x}_{8}) in 0.28 sec.

2. E(x_{1}; 1) ⊗ P (x_{2}; 2) ⊗ P (x_{3}; 6) ⊗ P (x_{4}; 10) ⊗ P (x_{5}; 26).

Input: ((1, 2, 6, 10, 26), (0, −2x_{1}, x_{1}x2_{2}, 3x_{1}x_{2}x_{3}, 8x_{1}x_{2}x2_{3}x_{4})).

Output: ((2, 3, 7, 11, 27), (0, −2\underline{x}_{1}, −8\underline{x}3_{1}, −192\underline{x}5_{1}, 21799895040\underline{x}13_{1}))

Time: d_{δ}(\underline{x}_{2}) in 0.16 sec.

d_{δ}(\underline{x}_{3}) in 0.60 sec.

d_{δ}(\underline{x}_{4}) in 2.36 sec.
d_{δ}(\underline{x}_{5}) in 1571.47 sec.

3. E(x_{1}; 1) ⊗ P (x_{2}; 2) ⊗ P (x_{3}; 4) ⊗ E(x_{4}; 5) ⊗ E(x_{5}; 7) ⊗ P (x_{6}; 14).

Input: ((1, 2, 4, 5, 7, 14), (0, −x_{1}, x_{1}x_{2}, 0, 2x_{1}x_{4}, −x_{1}x_{4}x_{5})).

Output: ((2, 3, 5, 6, 8, 15), (0, −\underline{x}_{1}, −\underline{x}2_{1}, 0, 0))

Time: d_{δ}(\underline{x}_{2}) in 0.17 sec.

d_{δ}(\underline{x}_{3}) in 0.33 sec.

d_{δ}(\underline{x}_{4}) in 0.26 sec.
d_{δ}(\underline{x}_{5}) in 0.17 sec.

For each algebra, we summarize the results and the time taken to compute a description of the model. All CPU times are in seconds and calculations were carried out on a Pentium III, 128Mb RAM, 7.2Gb hard disk space.

This programme produces as output an encoding of a certain differential graded algebra which could be introduced into another programme in order to calculate the homology of such objects. We intend to tackle this task in the near future.

References

1. Álvarez V., Armario J.A., González–Díaz R., Real P.: Algorithms in Algebraic Topology and Homological Algebra: the Problem of the Complexity. Extended Abstracts of the First Workshop on Computer Algebra and Scientific Computing, CASC’98 (1998) Saint Petersburg, Russia.

2. Álvarez V., Armario J.A., Real P., Silva B.: HPT and Computability of the Homology of CDGAs. Conference on Secondary Calculus and Cohomological Physics, Moscow (1997). Electronic Proceedings of the EMS (http://www.emis.de/proceedings).

3. Armario J.A., Real P., Silva B.: On p–Minimal Homological Models of Twisted Tensor Products of Elementary Complexes Localized over a Prime. Contemporary Mathematics 227 (1999) 303–314.

4. Eilenberg S., Mac Lane S.: On the Groups H(π, n), I. Annals of Math. 58 (1953) 55–139.

5. Eilenberg S., MacLane S.: On the Groups H(π, n), II. Annals of Math. 60 (1954) 49-139.

6. Gugenheim V.K.A.M., Lambe L.A.: Perturbation Theory in Differential Homological Algebra, I. Illinois J. Math. 33 (1989) 556–582.

7. Gugenheim V.K.A.M., Lambe L.A., Stasheff J.D.: Perturbation Theory in Differential Homological Algebra, II. Illinois J. Math. 35 n. 3 (1991) 357–373.

8. González–Díaz R., Real P.: Computing Cocycles on Simplicial Complexes. Proceedings of the Second Workshop on Computer Algebra and Scientific Computing, CASC’99 (1999) Springer–Verlag, 177–190.

9. Huebschmann J., Kadeishvili T.: Small Models for Chain Algebras. Math. Zeit. 207 (1991) 245-280.

10. MacLane S.: Homology. Classics in Mathematics (1995) Springer.

11. Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley Publishing Company (1984).

12. Lambe L.A.: Homological Perturbation Theory, Hochschild Homology and Formal Groups. Contemp. Math. 134 (1992) 183–218.

13. Real P.: t Homological Perturbation Theory and Associativity. Preprint of University of Seville (1996).

14. Veblen O.: Analysis Situs. A.M.S. Publications 5 (1931).

15. Weibel C.A.: An Introduction to Homological Algebra. Cambridge Studies in Advanced Mathematics 38, Cambridge University Press (1994).