Fast Möbius and Zeta Transforms
share
Möbius inversion of functions on partially ordered sets (posets) 𝒫 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 = |𝒫| and k is the width (length of longest antichain) of 𝒫, compared to O(n^2) for a direct computation. Our approach assumes that 𝒫 is given as directed acyclic graph (DAG) (ℰ, 𝒫). The algorithms are then constructed using a chain decomposition for a one time cost of O(|ℰ| + |ℰ_red| k), where ℰ_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.
READ FULL TEXT