Let $K$ be a simplicial complex and $g$ the rank of its $p$-th homology group
$H_p(K)$ defined with $Z_2$ coefficients. We show that we can compute a basis
$H$ of $H_p(K)$ and annotate each $p$-simplex of $K$ with a binary vector of
length $g$ with the following property: the annotations, summed over all
$p$-simplices in any $p$-cycle $z$, provide the coordinate vector of the
homology class $[z]$ in the basis $H$. The basis and the annotations for all
simplices can be computed in $O(n^{\omega})$ time, where $n$ is the size of $K$
and $\omega<2.376$ is a quantity so that two $n\times n$ matrices can be
multiplied in $O(n^{\omega})$ time. The pre-computation of annotations permits
answering queries about the independence or the triviality of $p$-cycles
efficiently.
Using annotations of edges in 2-complexes, we derive better algorithms for
computing optimal basis and optimal homologous cycles in 1-dimensional
homology. Specifically, for computing an optimal basis of $H_1(K)$, we improve
the time complexity known for the problem from $O(n^4)$ to
$O(n^{\omega}+n^2g^{\omega-1})$. Here $n$ denotes the size of the 2-skeleton of
$K$ and $g$ the rank of $H_1(K)$. Computing an optimal cycle homologous to a
given 1-cycle is NP-hard even for surfaces and an algorithm taking
$2^{O(g)}n\log n$ time is known for surfaces. We extend this algorithm to work
with arbitrary 2-complexes in $O(n^{\omega})+2^{O(g)}n^2\log n$ time using
annotations.

本研究提出了一种新的方法，利用注释对高维流形的 $p$- 循环和 $p$ 阶同调群进行计算和快速查询，其中 $p$ 为给定的维度。