论文标题
消息传递算法中的一类用于节点计算的最佳结构
A Class of Optimal Structures for Node Computations in Message Passing Algorithms
论文作者
论文摘要
考虑传递算法的消息中的节点上的计算。假设该节点具有传入和传出消息$ \ MATHBF {x} =（x_1，x_2，\ ldots，x_n）$和$ \ Mathbf {y} =（y_1，y_1，y_2，\ ldots，y__n）$。在本文中，我们研究了一类结构，这些结构可以由节点从$ \ mathbf {x} $中计算出$ \ mathbf {y} $，其中每个$ y_j，j = 1，2，\ ldots，n $都是通过binary Tree计算的，带有biary Tree，带有lays $ \ mathbf {x} $ x_ $ x_ $ x__j $ x__j。我们对这类结构做出了三个主要贡献。首先，我们证明，这种结构的最小复杂性为$ 3N-6 $，如果结构具有如此复杂性，其最小延迟为$δ+ \ \ lceil \ log（n -2^δ）\ rceil $与$δ= \ lfloor \ lfloor \ log（n/2）\ rfloor $，始终将差异为二下。其次，我们证明这种结构的最小延迟是$ \ lceil \ log（n-1）\ rceil $，如果结构具有这样的延迟，其最小复杂性为$ n \ log（n-1）$时，$ n-1 $是两个的幂。第三，给定$（n，τ）$带有$τ\ geq \ lceil \ log（n-1）\ rceil $，我们为结构提出了一个结构，我们猜测该结构在最多$τ$的结构中具有最小的复杂性。我们的施工方法以$ o（n^3 \ log^2（n））$时间运行，并且所获得的结构最多具有复杂性（通常比）$ n \ lceil \ log（n）\ rceil -2 $。
Consider the computations at a node in a message passing algorithm. Assume that the node has incoming and outgoing messages $\mathbf{x} = (x_1, x_2, \ldots, x_n)$ and $\mathbf{y} = (y_1, y_2, \ldots, y_n)$, respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing $\mathbf{y}$ from $\mathbf{x}$, where each $y_j, j = 1, 2, \ldots, n$ is computed via a binary tree with leaves $\mathbf{x}$ excluding $x_j$. We make three main contributions regarding this class of structures. First, we prove that the minimum complexity of such a structure is $3n - 6$, and if a structure has such complexity, its minimum latency is $δ+ \lceil \log(n-2^δ) \rceil$ with $δ= \lfloor \log(n/2) \rfloor$, where the logarithm always takes base two. Second, we prove that the minimum latency of such a structure is $\lceil \log(n-1) \rceil$, and if a structure has such latency, its minimum complexity is $n \log(n-1)$ when $n-1$ is a power of two. Third, given $(n, τ)$ with $τ\geq \lceil \log(n-1) \rceil$, we propose a construction for a structure which we conjecture to have the minimum complexity among structures with latencies at most $τ$. Our construction method runs in $O(n^3 \log^2(n))$ time, and the obtained structure has complexity at most (generally much smaller than) $n \lceil \log(n) \rceil - 2$.
