Polynomial convolution algorithm for matrix multiplication with application for optical computing

Published

Journal Article

First, we describe an algorithm (the polynomial convolution algorithm) for the multiplication of two rectangular matrices A and B. The algorithm codes the matrix elements of A and B into two polynomials in a common indeterminate; the degree of the polynomial characterizing A depends on the size of both A and B, while the degree of the polynomial characterizing B only involves the size of B. The matrix elements of the product C=AB are obtainable from the convolution of the two polynomials. Although theresultant analysis is quite complex, its implementation in optical computing can be carriedout in straightforward fashion (see Sec. III). The algorithm is at least as fast asthe outer product and Kronecker product algorithms advocated by Athale-Collins and Barakat, respectively, in the assumed conditions of equally accessible matrix elements. Second, we consider the situation where the matrices are so large that they cannot be stored simultaneously on optical masks. It is shown that the speed advantages of theouter product and Kronecker product algorithms are now lost in this situation, whereas the polynomial convolution algorithm, because of its modular structure, is robust with respect to the storage problem. Finally, we consider some partitioning strategies in the light of the storage problem. © 1987 Optical Society of America.

Full Text

Duke Authors

Cited Authors

  • Barakat, R; Reif, J

Published Date

  • July 15, 1987

Published In

Volume / Issue

  • 26 / 14

Start / End Page

  • 2707 - 2711

Electronic International Standard Serial Number (EISSN)

  • 2155-3165

International Standard Serial Number (ISSN)

  • 1559-128X

Digital Object Identifier (DOI)

  • 10.1364/AO.26.002707

Citation Source

  • Scopus