d843e514
—
Martin Hafskjold Thoresen
26 days ago

Fix bug where a boundary would be padded with zeros.

bae1de7f
—
Martin Hafskjold Thoresen
30 days ago

Remove _by_dim suffix.

50ab1601
—
Martin Hafskjold Thoresen
30 days ago

Add simplex count output in Aggregate

- read-only
- https://git.sr.ht/~mht/cra
- read/write
- git@git.sr.ht:~mht/cra

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

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
```

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';'
j faces adds reduced
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]
```

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
$ jq '.histogram_add_cost_by_dim' 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.

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'`