The program takes a file input. The file should contain a name for the complex and the supersets of it.
For example one would safe the comlex C = {Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, {4}} as the following content of a text file:
C := [[1,2,3], [4]].
The program will then generate all subsets of the 'supersets' itself.
The program constructs a chain complex through defining Ck as the set of all sets contained by the simplicial complex C with magnitude k+1.
One says, that the elements of Ck have dimension k. F.e. C-1 = {Ø} just contains the empty set of dimension -1.
Further we define boundary maps ∂k: Ck -> Ck-1 (thus we will get homology and not cohomology groups later on) through the following mapping rule:
Let A={a0,...,ak} be an element of Ck, we formally consider eA a basis element of an -Module.
Since we want for every k, we will set
Furthermore we then define the k-th homology group to be , what is welldefined because of the subset relation:
This groups are finitely generated abelian groups in our case. The program prints out the isomorphic direct sum of powers of cyclic groups such as Zn or Z.
We calculate the matrices of the boundary maps stated above.
While doing that we can already process just generated rows, without having the full matrix saved. Every time we generate a (generally sparse) row vector of the matrix, we look up if we have an index-intersection of the current vector with an already generated vector, having a trailing invertible in Z, which are +1 and -1 (meaning, that we have an index u, such that the u-th entry, let us call it x, in our current vector is not equal to 0. If we already have a vector with trailing invertible y at position u, we can add -y * x times the vector with trailing invertible at position u to the current vector and through repeating this for every entry in the current vector, get a vector with only 0s in columns, where a trailing one in any earlier row exists - see row echelon form).
Now there are two cases:
First: The current vector has a trailing invertible still. Then we put it to the list of vectors with this property, so that we can subtract it from the subsequently processed vectors. Since our goal is the reduced row echelon form, we will need to also subtract the latest processed vector from every previously processed one.
Second: The current vector has no trailing invertible (equivalently: the absolute value of the trailing non-zero value in vector is not 1). Then we add the vector to our remaining matrix. This one is going to be the hard part.
While processing the matrix, we count how many vector has been added to the trailing invertible vectors. That is how many 1s we will certainly get in the smith normal form of our boundary matrix.
After this first processing we go to the Core Algorithm with our remaining matrix, because through the row echelon form, we can just eliminate the rows, which have a trailing invertible, columnwise and get the identity matrix in the top-left block of our smith normal form. The top-right and top-left blocks are 0 by definition of the smith normal form. The bottom-right block will become the smith normal form of the remaining matrix.
The long runtimes on bigger examples are mainly due to this algorithm, therefore i will state two approaches, that i considered while working out this algorithm.
Input: Matrix with arbitrary structure.
Output: invariant factors of input matrix.
You can read about gcd based smith normal form algorithm and its problems here.
This is the (for now) final algorithm I used in code. It is described here.
For initializing a program argument one needs to type - after the program call in command line.
(Star after argument marks that it is necessary)
| Command | Description |
|---|---|
| C path:string* | C: Complex. This command determines the file, where to take the complex data from. NOTE: If your path contains spaces, please set double quotation marks ". |