PARALLEL SOLUTION OF DENSE LINEAR-SYSTEMS ON THE K-ARY N-CUBE NETWORKS

In this paper a parallel algorithm for solving systems of Linear equat ion on the k-ary n-cube is presented and evaluated for the first time. The proposed algorithm is of O(N-3/k(n)) computation complexity and u ses O(Nn) communication time to factorize a matrix of order N on the k -ary n-cube. This is better than the best known results for the hyperc ube, O(N log k(n)), and the mesh, O(N root k(n)), each with approximat ely k(n) nodes. The proposed parallel algorithm takes advantage of the extra connectivity in the k-ary n-cube in order to reduce the communi cation time involved in tasks such as pivoting, row/column interchange s, and pivot row and multipliers column broadcasts.