论文标题
快速的多材盘转换和加权总和在无环挖掘上
Fast Multi-Subset Transform and Weighted Sums Over Acyclic Digraphs
论文作者
论文摘要
Zeta和Moebius在$ n $元素的子集晶格上转换，所谓的子集卷积是集合功能的一元和二进制操作的示例。虽然他们的直接计算需要$ o（3^n）$算术操作，但较少的天真算法仅使用$ 2^n \ mathrm {poly}（n）$操作，几乎是输入大小的线性线性。在这里，我们研究了一个相关的$ n $ ary操作，该操作将$ n $设置功能作为输入，并将其映射到新的集合功能。我们称此操作称为多扣转换，是已知包含的核心成分 - 对无环的加权总和的排斥复发，它扩展了罗宾逊在标记的无循环挖掘数量的次数。在这项工作之前，最著名的复杂性绑定到了直接$ O（3^n）$。通过将任务减少到矩形矩阵乘法的多个实例，我们将复杂性提高到$ O（2.985^n）$。
The zeta and Moebius transforms over the subset lattice of $n$ elements and the so-called subset convolution are examples of unary and binary operations on set functions. While their direct computation requires $O(3^n)$ arithmetic operations, less naive algorithms only use $2^n \mathrm{poly}(n)$ operations, nearly linear in the input size. Here, we investigate a related $n$-ary operation that takes $n$ set functions as input and maps them to a new set function. This operation, we call multi-subset transform, is the core ingredient in the known inclusion--exclusion recurrence for weighted sums over acyclic digraphs, which extends Robinson's recurrence for the number of labelled acyclic digraphs. Prior to this work the best known complexity bound was the direct $O(3^n)$. By reducing the task to multiple instances of rectangular matrix multiplication, we improve the complexity to $O(2.985^n)$.
