Matrix inversion in O(log n) on a scan-enhanced reconfigurable mesh computer
Alberto Moreira, Bryant W. York · 1996
With the arrival ofthe current generation offast processor chips and improved interconnect technology, low-cost 3-dimensional reconfigurable mesh computers have become more feasible.They could present an attractive price/performance option to large supercomputers and small clusters of workstations.In 1976 Csanky introduced a parallel algorithm for matrix inversion which executed in O(log 2 n) steps on n 4 processors.Csanky's algorithm was designed for a CREW PRAM.More recently, Leighton produced an implementation of Csanky's algorithm for n meshes of trees which achieves O(log 2 n) steps on 4n 4 -3n 3 processors.In this work we show that a 3-dimensional reconfigurable mesh with n 4 processors can perform Csanky's matrix inversion algorithm in O(log 2 n) steps.With hardware assist capable of executing Blelloch's +-scans along one privileged dimension in 0(1) time, Csanky's algorithm for matrix inversion can be performed in O(log n) time on a 3-dimensional reconfigurable mesh with n 4 processors.Permission to make digital/bard copiea of all or part of this material for personal or classroom use is granted without fee provided that the copiea are not made or distributed for profit or COIDIDCrcial advantage, the COfYright notice, the title of the publication and ita date appear, and notice u given that copyright ia by pennisaion of the ACM, Inc.To copy otherwise, to republish, to post on servers or to redistribute to Iiili, requires lpCCific permiBBion and/or fee.