## ~mht/cra

d843e514 — Martin Hafskjold Thoresen Fix bug where a boundary would be padded with zeros. 10 months ago

## #CRA

This program implements the matrix reduction algorithm for computing the persistence of a complex, in two variants: regular and exhaustive.

### #Notes on the algorithm

The implementation of the algorithms is not really aligned all that well with the common descriptions of it, namely as a matrix reduction algorithm. Instead, we think of the algorithm as working with sets, which corresponds to the boundary of simplices, or matrix columns in the traditional description. Modulo 2 addition of matrix columns becomes symmetric difference of the sets.

Here's pseudocode that reflects how the algorithms are implemented.

``````reduced = [0; length(simplices)]
for s in simplices
if s is empty
continue
end
m = max(s)
if reduced[m] is empty
reduced[m] = simplex
continue
else
s = symdiff(s, reduced[m])
end
end
``````

### #Usage

Run with `--help` to get information on the arguments the program takes.

``````\$ cargo run -q -- -help
``````

or

``````\$ # this once:
\$ cargo build --release
\$ ./target/release/cra --help
``````

This will run with `debug` output, which right now prints a comma separated table of which simplices are added to which. To display this nicely in the terminal, you can pipe it to `column` as follows (only tested on Linux):

```cargo run -- --boundary data/tet.boundary -d | column -ts';'
0   []                []            [0]
0   [0]               []            [0]
1   [0]               [0]           []
2   [0]               [0]           []
3   [0]               [0]           []
5   [1, 2]            []            [1, 2]
6   [1, 3]            []            [1, 3]
7   [1, 4]            []            [1, 4]
8   [2, 3]            [6, 5]        []
9   [2, 4]            [7, 5]        []
10  [3, 4]            [7, 6]        []
11  [5, 6, 8]         []            [5, 6, 8]
12  [5, 7, 9]         []            [5, 7, 9]
13  [6, 7, 10]        []            [6, 7, 10]
14  [8, 9, 10]        [13, 12, 11]  []
15  [11, 12, 13, 14]  []            [11, 12, 13, 14]
```

#### #Statistics

By running CRA with `--stats=<filename>` (set filename to `-` to write to `stdout`), you get a bunch of statistics in `json`. This can be piped into `jq` to format, or filter out things, like so:

``````\$ cra --boundary data/tet.boundary --stats=- | jq
``````

Alternatively, you can save it in a file and run `jq` afterwards:

``````\$ cra --boundary data/tet.bondary --stats=tet.json
{
"1": {
"2": 3,
"4": 3
},
"0": {
"1": 3
},
"2": {
"7": 1,
"6": 1,
"3": 1
}
}
``````

Use `jq 'keys'` to list the keys. You probably also want to run `jq` with `-S`, which sorts the keys.

#### #Example

You want to show the average sizes of the two simplices added together, by dimension:

``````cra --boundary data/tet.boundary --stats=- | jq -S '.avg_add_size_by_dim'
``````