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

CRII：AF：拓扑算法的分而治之原则

• 批准号: 1464379
• 负责人: Donald Sheehy
• 金额: $ 17.3万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-02-01 至 2018-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1464379&HistoricalAwards=false
• 关键词: CRII; AF; Principled; Divide; Conquer

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.

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