M\"obius 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\"obius 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\"obius inversion on posets with millions of nodes in seconds if the defining DAGs are sufficiently sparse.

翻译：M\\ “ obius ” 翻转部分定购数据集( posts) 的函数 $\ mathcal{ P} $( mathcal{ P}) $( mathcal{ P} $) 是一个经典的组合工具。 对于有限的组合, 它由两个互相反向的线性变换组成, 分别称为 zeta 和 M\\\ “ obius 变换 。 在本文中, 我们为需要 $( nk) 时间和空间的两者提供新的快速算法 。 此时, $ = { mathcal{ P} 和 $ $ 美元是 $( mathcal{ P} ) 的宽度( legroundal ), 而不是 $( ) $( calthcal) = axxxxxxxxxxxx 。 $\\\\\\\ lexal ligal legal max max max max max 。