Loading...
Please wait, while we are loading the content...
Similar Documents
Homology annotations via matrix reduction.
| Content Provider | CiteSeerX |
|---|---|
| Author | Busaryev, Oleksiy Dey, Tamal K. Wang, Yusu |
| Abstract | In this work, we propose an alternative algorithm for annotating simplices of a simplicial complex K with sub-bases of a basis B of its p-dimensional homology group H1(K). Such annotations, summed over p-simplices in any p-cycle z, provide an expression of z in B. This allows us to answer queries of null homology and independence of p-cycles efficiently and improve the running time of the greedy algorithm to computea shortest basis of H1(K). The best known algorithm for the shortest basis problem that does not use annotations has a time complexity of O(n 4), where n is the size of the 2-skeleton of K. We improve it to O(n 3 +n 2 g 2), where g is the rank of H1(K). Annotating simplices with a homology basis has been considered before [1]. The existing approachcan preprocess the simplicial complex and assign annotations in sub-cubictime. However, this involves computing the LSP-decomposition of the boundary matrix, which can be computationally cumbersome. We present a simple and implementation-friendly O(n 3) approach that fits nicely to the family of matrix reduction algorithms such as the persistence algorithm and the classic Smith normal form reduction. Our analysis also reveals interesting connections to the persistence algorithm. Namely, our matrix reduction method computes pairing between simplices under homomorphisms between homology groups that are not necessarily induced by inclusions between the subcomplexes of the filtration of K. 1. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Matrix Reduction Homology Annotation Persistence Algorithm Simplicial Complex Known Algorithm Matrix Reduction Method Homology Basis Greedy Algorithm P-dimensional Homology Group H1 Shortest Basis Interesting Connection Homology Group Running Time Matrix Reduction Algorithm Boundary Matrix Null Homology Classic Smith Normal Form Reduction Alternative Algorithm Assign Annotation Basis Problem Time Complexity Approachcan Preprocess |
| Content Type | Text |
