Background
I'm working on a project that involves computing the homology of simplicial complexes. The way this is done results in the spanning set of vectors that describes the set of homology groups or holes in the complex, and these vectors are typically floating point due to how they are calculated. However, I care about linear combinations of these vectors that consist of values -1, 0, and 1 because these values correspond to discrete simplices that make up each hole.
Problem
Essentially, I have a set of vectors with floating point values that I want to simplify to an equivalent spanning set where the vectors only contain elements -1, 0, and 1. I know that all sets I will be applying this method to can be expressed this way.
Attempts
Currently, I have the following algorithm, which basically does row operations on a matrix with rows consisting of the spanning vectors.
def simplify(a, tol=1e-5) -> np.matrix:
r = a.copy()
for i in range(r.shape[0]):
for e, p in enumerate(r[i]):
if not is_unit(p):
r[i] = r[i] / p
for j in it.chain(range(0, i), range(i+1, r.shape[0])):
r[j] -= r[j, e] * r[i]
return as_unit(r, tol=tol)
Note that is_unit and to_unit check proximity to and round to the nearest whole number given the tolerance. While this works for small cases, it fails in specific instances related to the homology code (if you're familiar with it, it fails to simplify when there are simplices of dimension $n+1$).
If I start with the following vectors (each vector is a row of this matrix, so in this case, we have 2 6-vectors):
$ \begin{bmatrix} 0.21968405 & 0.08418094 & -0.69191091 & 0.38804592 & 0.30386499 & -0.47222686 \\ 0.67211526 & -0.39947495 & -0.14580566 & -0.12683464 & 0.27264031 & 0.52630959 \end{bmatrix}$
This yields:
$\begin{bmatrix} -1 & 0 & 2 & -1 & -1 & 1 \\ -3 & 1 & 3 & -1 & -2 & 0 \end{bmatrix}$
Even though it could be described as:
$\begin{bmatrix} 0 & 1 & -1 & 0 & 1 & 1 \\ 1 & -1 & -1 & -1 & -0 & 0 \end{bmatrix}$