Efficient parallel algorithms for optical computing with the discrete Fourier transform (DFT) primitive.

Journal Article (Journal Article)

Optical-computing technology offers new challenges to algorithm designers since it can perform an n-point discrete Fourier transform (DFT) computation in only unit time. Note that the DFT is a nontrivial computation in the parallel random-access machine model, a model of computing commonly used by parallel-algorithm designers. We develop two new models, the DFT-VLSIO (very-large-scale integrated optics) and the DFT-circuit, to capture this characteristic of optical computing. We also provide two paradigms for developing parallel algorithms in these models. Efficient parallel algorithms for many problems, including polynomial and matrix computations, sorting, and string matching, are presented. The sorting and string-matching algorithms are particularly noteworthy. Almost all these algorithms are within a polylog factor of the optical-computing (VLSIO) lower bounds derived by Barakat and Reif [Appl. Opt. 26, 1015 (1987) and by Tyagi and Reif [Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing (Institute of Electrical and Electronics Engineers, New York, 1990) p. 14].

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Tyagi, A

Published Date

  • October 1997

Published In

Volume / Issue

  • 36 / 29

Start / End Page

  • 7327 - 7340

PubMed ID

  • 18264241

Pubmed Central ID

  • 18264241

Electronic International Standard Serial Number (EISSN)

  • 1539-4522

International Standard Serial Number (ISSN)

  • 1559-128X

Digital Object Identifier (DOI)

  • 10.1364/ao.36.007327


  • eng