Two Classes of Optimal Multi-Input Structures for Node Computations in Message Passing Algorithms
<|reference_start|>Two Classes of Optimal Multi-Input Structures for Node Computations in Message Passing Algorithms: In this paper, we delve into the computations performed at a node within a message-passing algorithm. We investigate low complexity/latency multi-input structures that can be adopted by the node for computing outgoing messages y = (y1, y2, . . . , yn) from incoming messages x = (x1, x2, . . . , xn), where each yj , j = 1, 2, . . . , n is computed via a multi-way tree with leaves x excluding xj . Specifically, we propose two classes of structures for different scenarios. For the scenario where complexity has a higher priority than latency, the star-tree-based structures are proposed. The complexity-optimal ones (as well as their lowest latency) of such structures are obtained, which have the near-lowest (and sometimes the lowest) complexity among all structures. For the scenario where latency has a higher priority than complexity, the isomorphic-directed-rooted-tree-based structures are proposed. The latency-optimal ones (as well as their lowest complexity) of such structures are obtained, which are proved to have the lowest latency among all structures.<|reference_end|>
@article{lu2024two,
    title={Two Classes of Optimal Multi-Input Structures for Node Computations in
  Message Passing Algorithms},
    author={Teng Lu, Xuan He, and Xiaohu Tang},
    journal={arXiv preprint arXiv:2407.08941},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.08941},
    primaryClass={cs.IT math.IT}
}