## Abstract

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

© 1997 Optical Society of America

Full Article | PDF Article**OSA Recommended Articles**

Richard Barakat and John Reif

Appl. Opt. **26**(6) 1015-1018 (1987)

Ramamohan Paturi, Dau-Tsuong Lu, Joseph E. Ford, Sadik C. Esener, and Sing H. Lee

Appl. Opt. **30**(8) 917-927 (1991)

Sandy Pavel and Selim G. Akl

Appl. Opt. **35**(11) 1827-1835 (1996)