Algorithms for Matrix Multiplication and the FFT on a Processor Array with Separable Buses

Takashi MAEBA  Mitsuyoshi SUGAYA  Shoji TATSUMI  Ken'ichi ABE  

IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.1   pp.136-140
Publication Date: 2003/01/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithms
processor array with separable buses,  matrix multiplication,  fast Fourier transform,  parallel algorithm,  area-time complexity,  

Full Text: PDF(273.4KB)>>
Buy this Article

This letter presents parallel algorithms for matrix multiplication and the fast Fourier transform (FFT) that are significant problems arising in engineering and scientific applications. The proposed algorithms are designed on a 3-dimensional processor array with separable buses (PASb). We show that a PASb consisting of N N h processors can compute matrix multiplication of size N N and the FFT of size N in O(N/h+log N) time, respectively. In order to examine ease of hardware implementation, we also evaluate the VLSI complexity of the algorithms. A result obtained achieves an optimal bound on area-time complexity when h=O(N/log N).