EFFICIENT PARALLEL ALGORITHMS FOR OPTICAL COMPUTING WITH THE DISCRETEFOURIER-TRANSFORM (DFT) PRIMITIVE

Optical-computing technology offers new challenges to algorithm design ers since it can perform an n-point discrete Fourier transform (DFT) c omputation in only unit time. Note that the DFT is a nontrivial comput ation in the parallel random-access machine model, a model of computin g commonly used by parallel-algorithm designers. We develop two new mo dels, the DFT-VLSIO (very-large-scale integrated optics) and the DFT-c ircuit, to capture this characteristic of optical computing. We also p rovide two paradigms for developing parallel algorithms in these model s. Efficient parallel algorithms for many problems, including polynomi al and matrix computations, sorting, and string matching, are presente d. The sorting and string-matching algorithms are particularly notewor thy. Almost all these algorithms are within a polylog factor of the op tical-computing (VLSIO) lower bounds derived by Barakat and Reif [Appl . Opt. 26, 1015 (1987) and by Tyagi and Reif[ Proceedings of the Secon d: IEEE Symposium on Parallel and Distributed Processing (Institute of Electrical and Electronics Engineers, New York, 1990) p. 14]. (C) 199 7 Optical Society of America.