论文标题
FastMöbius和Zeta变换
Fast Möbius and Zeta Transforms
论文作者
论文摘要
Möbius在部分有序集合（POSETS）$ \ MATHCAL {P} $上的功能倒置是组合学中的经典工具。对于有限的POSET，它分别由两个相互反向的线性变换组成，分别称为Zeta和Möbius变换。在本文中，我们为需要$ o（nk）$时间和空间提供了新颖的快速算法，其中$ n = | \ natercal {p} | $和$ k $是$ \ nathcal {p} $的宽度（最长的抗），而直接计算的$ o（n^2）$。我们的方法假设$ \ Mathcal {p} $作为定向循环图（dag）$（\ Mathcal {e}，\ Mathcal {p}）$给出。然后，使用链分解构建算法，一次成本为$ O（| \ Mathcal {e} | + | \ Mathcal {e} _ \ text {red} | k）$，其中$ \ mathcal {e} _ \ text {red text {red text {red text {red} $是该dag的Edges in dag sermistive dag sermistive reduction dag的编号。我们显示了所有算法（包括并行版本）的实现的基准。结果表明，如果定义DAG足够稀疏，我们的算法使Möbius倒置在POSET上具有数百万个节点。
Möbius inversion of functions on partially ordered sets (posets) $\mathcal{P}$ is a classical tool in combinatorics. For finite posets it consists of two, mutually inverse, linear transformations called zeta and Möbius transform, respectively. In this paper we provide novel fast algorithms for both that require $O(nk)$ time and space, where $n = |\mathcal{P}|$ and $k$ is the width (length of longest antichain) of $\mathcal{P}$, compared to $O(n^2)$ for a direct computation. Our approach assumes that $\mathcal{P}$ is given as directed acyclic graph (DAG) $(\mathcal{E}, \mathcal{P})$. The algorithms are then constructed using a chain decomposition for a one time cost of $O(|\mathcal{E}| + |\mathcal{E}_\text{red}| k)$, where $\mathcal{E}_\text{red}$ is the number of edges in the DAG's transitive reduction. We show benchmarks with implementations of all algorithms including parallelized versions. The results show that our algorithms enable Möbius inversion on posets with millions of nodes in seconds if the defining DAGs are sufficiently sparse.
