comphomalg: a computational homological algebra library

Copyright (c) 2019, Michael Robinson

Synopsis

This library contains functions for manipulating sequences of linear maps and maps between these sequences, or in other words "tools for homological algebra". The library was written for use with GNU Octave. It is eventually intended to work on Matlab as well.

High level capabilities:

1. Barcode (interval) decompositions for sequences of linear maps
2. Chain map decompositions (maps between chain complexes)
3. Render the above in LaTeX using XyPic

The library is structured so that there are functions to construct and decompose sequences and sequence maps. The construction and decomposition operations should be inverse operations, and the unit tests verify this. The focus is primarily on integer or easy-to-manipulate rational matrix entries, so that examples can be generated that are suitable for manual calculation. There is a simple LaTeX rendering toolbox so that these examples can be easily included in documents. The library should be reasonably performant for examples that are larger as well.

Basic linear algebra tools

Homological algebra is built upon linear algebra, and requires a few extensions to the standard functions available in Octave or Matlab.

Name	Description
nice_square_matrix	generates matrices suitable for manual calculations
kernel	computes the kernel of a matrix using the method of free columns and should agree with the builtin null as far as dimensions are concerned
quotient_basis	computes a decomposition of a space into a give subspace and its quotient
canonical_projection	computes the projection matrix onto a quotient of a vector space by a subspace
induced_map	computes the map on the quotient induced by a given linear map

Most of the generator functions come in two "flavors": a permutation flavor and a "scramble" flavor. The latter makes use of the nice_square_matrix to specify a transformation from the canonical basis to one that's not, but the transformation should be "easy to work with" manually. That is, its determinant should not be too large, and its components should not be too small. This keeps each of the entries during row reduction to be rational numbers with reasonably small denominators.

Do be sure to check the matrices generated by nice_square_matrix and its callers to make sure that it hasn't made any unlucky choices!

Sequences of linear maps

The fundamental object in the study of homological algebra is that of a sequence of linear maps. These are represented as cellarrays of matrices, so that consecutive matrices can be multiplied. Every such sequence is isomorphic to a sum of bars, or sequences consisting of a short string of consecutive 1-dimensional spaces.

Name	Top level	Script	Generator	Decomposer
barcode_generator	Y		Y
barcode_generator_scramble	Y		Y
barcode_scramble_mats	Y		Y
barcode_decompose	Y			Y
barcode_reader	Y			Y
chain_complex_unittest	Y	Y	Y	Y
barcode_reader_unittest	Y	Y	Y	Y
dualize_sequence
laplacian

The two _unittest files are scripts meant to be run from the Octave command line. They run an end-to-end analysis, first generating a random sequence by way of specifying its barcode, constructing the sequence from that, and then decomposing the sequence. It should be the case that the decomposition recovers the barcode, and the _unittest scripts verify that.

The barcode_scramble_mats function is special, in that it takes an existing sequence, and produces a random sequence map to shuffle the bases.

Sequence and chain maps

Given sequences of linear maps as objects, their corresponding morphisms are sequence maps: commutative ladder diagrams. These are represented as a triple of cellarrays of matrices:

1. The domain sequence (length N), usually called mats1
2. The codomain sequence (length N), usually called mats2
3. The sequence of component maps (length N+1), usually called comps

As in the case of sequences, there are generator and decomposers... However, there is an important mathematical difference. General sequence maps are quite complicated, and do not respect barcode decompositions. However, sequence maps between chain complexes (chain_complexes for short) do respect barcode decompositions. Therefore, most of the functions deal only with chain maps.

Name	Top level	Script	Generator	Decomposer
is_sequence_map
chain_map_generator	Y		Y
chain_map_unittest	Y	Y	Y
chain_map_generator_scramble	Y		Y
chain_map_decompose	Y			Y
chain_map_decompose_unittest	Y		Y	Y
bar_chain_map_to_bar
quasi_isos	Y	Y	Y

Chain maps decompose into a sum of bar_chain_maps, which are short chain maps (three index). These are defined according to their Type which is coded according to the following table. Each pair of rows specifies a bar chain map, with the domain above the codomain. Each space is either blank (trivial space) or R (for a 1-dimensional space). Maps go from left to right, and are all of maximal rank.

Type	Index 1	Index 2	Index 3
1
2
	R
3
	R	R
4	R
5	R
	R
6		R
	R	R
7	R	R
8	R	R
	R
9	R	R
	R	R
10		R	R
	R	R

Since each bar chain map implies two chain complexes -- domain and codomain -- there is a function bar_chain_map_to_bar to translate a bar chain map Type into a bar as used by the sequence generator functions.

Rendering capabilities

Typesetting large commutative ladders labeled with matrices is usually a time-consuming exercise. On the other hand, these kind of diagrams are predictable enough to be automatically typeset in LaTeX. The diagrams produced rely on the XyPic sublanguage of LaTeX.

Name	Top level	XyPic
render_barcode	Y	N
render_matrix		N
render_sequence	Y	Y
render_sequence_map	Y	Y

Note that the render_matrix function rounds entries to make them render nicely. Sometimes entries will show up as -0, which may be a bit mystifying but are easy enough to remove if you don't want them.