Efficient parallel matrix inversion on interconnection networks

doi:10.1006/jpdc.1996.0055

Efficient parallel matrix inversion on interconnection networks

1996-05-01

6

PRE

AI

DOI：10.1006/jpdc.1996.0055

Original

Original request for help

Save

Abstract

En 中文

In this paper, we present efficient algorithms for the inversion of a triangular matrix on different interconnection networks. For hypercubes, we describe an elegant straightforward implementation of L. Csansky's well known PRAM algorithm [Ph.D. dissertation, Computer Sei. Div., Univ, of California, Berkeley 1974]. The time complexity is O(log(2) n) using n(3) processors, i.e., within the same order as the PRAM algorithm. Moreover, we give a general approach for the design of triangular matrix inversion algorithms on a large class of networks. Applied to some of these networks, as, e.g., the de Bruijn network, the shuffle-exchange network, and the cube-connected-cycles, this approach yields triangular matrix inversion algorithms that meet the PRAM complexity bounds of the problem within a small constant. (C) 1996 Academic Press, Inc.

Efficient parallel matrix inversion on interconnection networks

Abstract

Journal

Organization