Distributed computation of homology using harmonics

MaRDI QIDQ6242449zbMATH OpenFDO

Authors Harish Chintakunta, Hamid Krim

Publication date 5 June 2013

Abstract: We present a distributed algorithm to compute the first homology of a simplicial complex. Such algorithms are very useful in topological analysis of sensor networks, such as its coverage properties. We employ spanning trees to compute a basis for algebraic 1-cycles, and then use harmonics to efficiently identify the contractible and homologous cycles. The computational complexity of the algorithm is $O(|P{|}^{o}mega)$, where $|P|$ is much smaller than the number of edges, and $omega$ is the complexity order of matrix multiplication. For geometric graphs, we show using simulations that $|P|$ is very close to the first Betti number.

This page was built for publication: Distributed computation of homology using harmonics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6242449)