Editing Computational topology (section)

===Computational homology===

Computation of [[homology group]]s of [[CW complex|cell complexes]] reduces to bringing the boundary matrices into [[Smith normal form]]. Although this is a completely solved problem algorithmically, there are various technical obstacles to efficient computation for large complexes. There are two central obstacles. Firstly, the basic Smith form algorithm has cubic complexity in the size of the matrix involved since it uses row and column operations which makes it unsuitable for large cell complexes. Secondly, the intermediate matrices which result from the application of the Smith form algorithm get filled-in even if one starts and ends with sparse matrices.

* Efficient and probabilistic Smith normal form algorithms, as found in the [http://www.linalg.org LinBox] library.
* Simple homotopic reductions for pre-processing homology computations, as in the [http://www.sas.upenn.edu/~vnanda/perseus/index.html Perseus] software package.
* Algorithms to compute [[persistent homology]] of [[Filtration (mathematics)|filtered]] complexes, as in the [https://CRAN.R-project.org/package=TDAstats TDAstats] R package.<ref>{{Cite journal|title = TDAstats: R pipeline for computing persistent homology in topological data analysis|journal = Journal of Open Source Software|date = 2018|pages=860|volume = 3|issue = 28| pmid=33381678|  doi = 10.21105/joss.00860|first1 = Raoul|last1 = Wadhwa|first2 = Drew|last2 = Williamson|first3 = Andrew|last3 = Dhawan|first4 = Jacob|last4 = Scott| pmc=7771879 |bibcode = 2018JOSS....3..860R|doi-access = free}}</ref>
*In some applications, such as in TDA, it is useful to have representatives of (co)homology classes that are as "small" as possible. This is known as the problem of (co)homology localization. On triangulated manifolds, given a chain representing a homology class, it is in general NP-hard to approximate the minimum-support homologous chain.<ref>{{Cite journal|title = Hardness results for homology localization|journal = Discrete & Computational Geometry|date = 2011|pages=425–448|volume = 45|issue = 3| mr=2770545|  doi = 10.1007/s00454-010-9322-8|first1 = Chao|last1 = Chen|first2 = Daniel|last2 = Freedman}} Preliminary version appeared at SODA 2010.</ref> However, the particular setting of approximating 1-cohomology localization on triangulated 2-manifolds is one of only three known problems whose hardness is equivalent to the [[Unique Games Conjecture]].<ref>{{cite conference
 | last1 = Grochow | first1 = Joshua
 | last2 = Tucker-Foltz | first2 = Jamie
 | doi = 10.4230/LIPIcs.SoCG.2018.43
 | conference = 34th Internat. Symp. Comput. Geom. (SoCG) '18
 | mr = 3824287
 | page = 43:1-43:16
 | title = Computational Topology and the Unique Games Conjecture
 | year = 2018 
 | doi-access = free
 | eprint = 1803.06800}}.
</ref>