The search functionality is under construction.

IEICE TRANSACTIONS on Information

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

Takashi MAEBA, Mitsuyoshi SUGAYA, Shoji TATSUMI, Ken'ichi ABE

  • Full Text Views

    0

  • Cite this

Summary :

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).

Publication
IEICE TRANSACTIONS on Information Vol.E86-D No.1 pp.136-140
Publication Date
2003/01/01
Publicized
Online ISSN
DOI
Type of Manuscript
LETTER
Category
Algorithms

Authors

Keyword