Constant time inner product and matrix computations on permutation network processors

Inner product and matrix operations find extensive use in algebraic computations. In this brief contribution, we introduce a new parallel computation model, called a permutation network processor, to carry out these computations efficiently. Unlike the traditional parallel computer architectures, computations on this model are carried out by composing permutations on permutation networks. We show that the sum of N algebraic numbers on this model can be computed in O(1) time using N processors. We further show that the inner product and matrix multiplication can both be computed on this model in O(1) time at the cost of O(N) and O(N³), respectively, for N element vectors, and N×N matrices. These results compare well with the time and cost complexities of other high level parallel computer models such as PRAM and CRCW PRAM