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 ArticleMore Like This
Richard Barakat and John Reif
Appl. Opt. 26(6) 1015-1018 (1987)
Sandy Pavel and Selim G. Akl
Appl. Opt. 35(11) 1827-1835 (1996)
Ramamohan Paturi, Dau-Tsuong Lu, Joseph E. Ford, Sadik C. Esener, and Sing H. Lee
Appl. Opt. 30(8) 917-927 (1991)