Dimension exchange algorithm

Cybenko [14] suggested a dimension exchange algorithm, in which the edges of the graph are colored so that no two edges of the same color share a vertex. Pairs of processors having the same color were grouped and a processor pair $(i,j)$ with load $l_i$ and $l_j$ exchange their load, after which each has the load $(l_i+l_j)/2$. The algorithm was proved to converge in $d$ steps if the graph considered was a hypercube with dimension $d$. Xu and Lau [88,89] extended the dimension exchange algorithm so that after the exchange processor $i$ has load $l_i*a+l_j*(1-a)$. If $a=0.5$ this is equivalent to Cybenko's algorithm. Based on an eigenvalue analysis of the underlining iterative matrices, they argued that for some graph a factor $a$ other than $0.5$ gives better convergence. On a graph with small connectivity, this algorithm suffers in convergence in the same way as the diffusion algorithm.