  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.
