Jacobi Orderings for Multi-Port Hypercubes

The communication cost plays a key role in the performance of many parallel algorithms. In the particular case of the one-sided Jacobi method for symmetric eigenvalue and eigenvector computation the communication cost of previously proposed algorithms is mainly determined by the particular ordering being used. In this paper we proposed two novel Jacobi orderings: the permuted-BR ordering and the degree-4 ordering, aimed at efficiently exploiting the multi-port capability of a hypercube. It is shown that the former is nearly optimal for some scenarios and the latter outperforms previously known orderings by a factor of two. 1 Introduction The one-sided Jacobi method for symmetric eigenvalue computation is very suited for its application on a multicomputer since it exhibits a high parallelism and potentially low communication requirements [5]. The one-sided method uses a series of similarity transformations to make the original symmetric matrix converge to a diagonal form. Every similar..