Chain complex reduction via fast digraph traversal.
Chain complex reduction via fast digraph traversal.
复制标题
通过快速有向图遍历来减少链复数。
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Leon Lampret
中科院分区：
文献类型：
--
作者：
Leon Lampret
使用代数莫尔斯理论减少链复合体（同时保留其同伦型）给出与高斯消去相同的最终结果，但AMT只在某些行/列和几个枢轴（同时在所有矩阵中）上这样做。关键是，它不是在稀疏矩阵上进行昂贵的行/列操作，而是计算二部有向图的遍历。这大大减少了运行时间和内存负载（更小的矩阵填充和系数增长）。然而，用AMT计算需要构造一组有效的轴（称为莫尔斯匹配）。我们在任意有限秩自由模的链复上发现了一个莫尔斯匹配族。我们证明了每一个非环匹配都是我们家族的某个成员的子集，因此所有极大莫尔斯匹配都是这种类型。AMT的输入和输出都是链式配合物，因此该过程可以迭代使用。当处理一个字段或局部PID时，该过程以零矩阵的链复合体结束，从而产生同调。然而，即使在更一般的环上，这个过程也经常显示出同源性，或者至少减少了复杂性，以至于其他算法可以完成这项工作。此外，它还返回了约化配合物的同伦等价，从而揭示了同伦的生成和诱导映射$H_ast(varphi)$。我们设计了一种新的简化链复合体的算法并实现了它。我们测试它优于其他CASs。作为一种特殊情况，给定任意域上的稀疏矩阵，该算法提供了一种计算核（或零空间）、核（或商空间，或互补子空间）、像、原像、和、交子空间的秩和稀疏基的新方法。它优于其他CASs中的内置算法。
Reducing a chain complex (whilst preserving its homotopy-type) using algebraic Morse theory gives the same end-result as Gaussian elimination, but AMT does it only on certain rows/columns and with several pivots (in all matrices simultaneously). Crucially, instead of doing costly row/column operations on a sparse matrix, it computes traversals of a bipartite digraph. This significantly reduces the running time and memory load (smaller fill-in and coefficient growth of the matrices). However, computing with AMT requires the construction of a valid set of pivots (called a Morse matching). We discover a family of Morse matchings on any chain complex of free modules of finite rank. We show that every acyclic matching is a subset of some member of our family, so all maximal Morse matchings are of this type. Both the input and output of AMT are chain complexes, so the procedure can be used iteratively. When working over a field or a local PID, this process ends in a chain complex with zero matrices, which produces homology. However, even over more general rings, the process often reveals homology, or at least reduces the complex so much that other algorithms can finish the job. Moreover, it also returns homotopy equivalences to the reduced complexes, which reveal the generators of the homology and the induced maps $H_ast(varphi)$. We design a new algorithm for reducing a chain complex and implement it. We test that it outperforms other CASs. As a special case, given a sparse matrix over any field, the algorithm offers a new way of computing the rank and a sparse basis of the kernel (or null space), cokernel (or quotient space, or complementary subspace), image, preimage, sum and intersection subspace. It outperforms built-in algorithms in other CASs.