Efficient parallel algorithms for optical computing with the DFT primitive


Conference Paper

© Springer-Verlag Berlin Heidelberg 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].

Full Text

Duke Authors

Cited Authors

  • Reif, J; Tyagi, A

Published Date

  • January 1, 1990

Published In

Volume / Issue

  • 472 LNCS /

Start / End Page

  • 149 - 160

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540534877

Digital Object Identifier (DOI)

  • 10.1007/3-540-53487-3_41

Citation Source

  • Scopus