Efficient parallel algorithms for optical computing with the DFT primitive
Publication
, Conference
Reif, J; Tyagi, A
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 1990
The optical computing technology offers new challenges to the algorithm designers since it can perform an n-point DFT computation in only unit time. Note that DFT is a non-trivial computation in the PRAM model. We develop two new models, DFT-VLSIO and 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 of these algorithms are within a polylog factor of the optical computing (VLSIO) lower bounds derived in [BR87] and [TR90].
Duke Scholars
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
ISBN
9783540534877
Publication Date
January 1, 1990
Volume
472 LNCS
Start / End Page
149 / 160
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Reif, J., & Tyagi, A. (1990). Efficient parallel algorithms for optical computing with the DFT primitive. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 472 LNCS, pp. 149–160). https://doi.org/10.1007/3-540-53487-3_41
Reif, J., and A. Tyagi. “Efficient parallel algorithms for optical computing with the DFT primitive.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 472 LNCS:149–60, 1990. https://doi.org/10.1007/3-540-53487-3_41.
Reif J, Tyagi A. Efficient parallel algorithms for optical computing with the DFT primitive. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1990. p. 149–60.
Reif, J., and A. Tyagi. “Efficient parallel algorithms for optical computing with the DFT primitive.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 472 LNCS, 1990, pp. 149–60. Scopus, doi:10.1007/3-540-53487-3_41.
Reif J, Tyagi A. Efficient parallel algorithms for optical computing with the DFT primitive. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1990. p. 149–160.
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
ISBN
9783540534877
Publication Date
January 1, 1990
Volume
472 LNCS
Start / End Page
149 / 160
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences