CRII: AF: Principled Divide-and-Conquer for Topological Algorithms

许多数据集在收集过程之前、之后或期间都会经历转换，这些转换通常通过平滑、去噪或配准来纠正。拓扑数据分析（TDA）使得从这些转换不变的数据中提取健壮的签名成为可能。然而，在TDA中，考虑到表示（或估计）底层数据的连通性的边、三角形和其他简单元素所需的空间，即使是相对较小的数据集也很容易膨胀到足以填满内存。我们需要一种快速、并行和分布式的算法，以一种有原则的方式对输入进行划分，从而产生强大的理论保证和实际性能。本项目旨在通过将嵌套解剖（数值分析中一个得到充分研究的理论）与持续同源性（TDA的主要技术）相结合来满足这一需求，并期望这两个领域都能受益。该项目的一个潜在的更广泛的影响是改善TDA和NA研究人员之间的交流。PI将培训本科生和研究生的研究人员，并在本科生和研究生课程中纳入组合拓扑的先进概念。具体的目的是发展一个理论的嵌套解剖的简单复合体，允许快速，并行计算的持续同源。第二个具体目标是为持久同调计算过程中出现的部分简化复合体开发和分析新的有效数据表示。这将涉及到对并求问题的拓扑推广，结合持久同调和离散莫尔斯理论的新方法，直接在商向量空间上工作的嵌套分解理论的扩展（如域上的同调群），以及适用于过滤或其他情况的分隔理论，其中底层图或复随时间变化。初步的例子表明，这些扩展可以产生更好的理论保证。第三个具体目标是实现这种方法，将其与现有的开源代码进行比较，并可能将其与现有的开源代码集成。

Many data sets undergo transformations either before, after, during the collection process which are most often corrected by smoothing, de-noising, or registration. Topological Data Analysis (TDA) makes it possible to extract robust signatures from data that are invariant to these transformations. However, in TDA, even a relatively small data set can easily blow up to fill memory when considering the space needed for edges, triangles, and other simplices that represent (or estimate) the connectivity of the underlying data. There is a need for fast, parallel, and distributed algorithms that partition the input in a principled way that leads to both strong theoretical guarantees and also practical performance. This project aims to fill this need by combining nested dissection, a well-studied theory from numerical analysis (NA) with persistent homology, the main technique of TDA, with the expectation that both fields will benefit. A potential broader impact of the project is to improve communication between researchers in TDA and NA. The PI will train both undergraduate and graduate researchers and incorporate advanced concepts in combinatorial topology in undergraduate and graduate curricula.The specific aim is to develop a theory of nested dissection on simplicial complexes that allows for fast, parallel computation of persistent homology. A second specific aim is to develop and analyze new efficient data representations for the partially reduced simplicial complexes that appear in the course of persistent homology computation. This will involve a topological generalization of the Union-Find problem, a new approach to combining persistent homology and discrete Morse theory, an extension of the theory of nested dissection to work directly over quotient vector spaces (such as homology groups over fields), and also a separator theory that applies to filtrations or other situations where the underlying graph or complex is changing in time. Preliminary examples indicate that these extensions may produce significantly better theoretical guarantees. A third specific aim is to implement this approach, compare it with, and possibly integrate it with existing open source codes.