A Class of Optimal Structures for Node Computations in Message Passing Algorithms

Abstract: Consider the computations at a node in a message passing algorithm. Assume that the node has incoming and outgoing messages

m a t h b f x = (x_{1}, x_{2}, l d o t s, x_{n})

and

m a t h b f y = (y_{1}, y_{2}, l d o t s, y_{n})

, respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing

m a t h b f y

from

m a t h b f x

, where each

y_{j}, j = 1, 2, l d o t s, n

is computed via a binary tree with leaves

m a t h b f 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

3 n - 6

, and if a structure has such complexity, its minimum latency is

d e l t a + l c e i l l o g (n - 2^{d e l t a}) c e i l

with

d e l t a = l f l o o r l o g (n / 2) f l o o r

, where the logarithm always takes base two. Second, we prove that the minimum latency of such a structure is

l c e i l l o g (n - 1) c e i l

, and if a structure has such latency, its minimum complexity is

n l o g (n - 1)

when

n - 1

is a power of two. Third, given

(n, a u)

with

a u g e q l c e i l l o g (n - 1) c e i l

, we propose a construction for a structure which we conjecture to have the minimum complexity among structures with latencies at most

a u

. Our construction method runs in

O (n^{3} l o g^{2} (n))

time, and the obtained structure has complexity at most (generally much smaller than)

n l c e i l l o g (n) c e i l - 2

.

Recommendations

Cited In (1)

This page was built for publication: A Class of Optimal Structures for Node Computations in Message Passing Algorithms