Optimal deterministic approximate parallel prefix sums and their applications

Author

Goldberg, Tal ; Zwick, Uri

Author_Institution

Dept. of Comput. Sci., Tel Aviv Univ., Israel

fYear

1995

fDate

4-6 Jan 1995

Firstpage

220

Lastpage

228

Abstract

We show that extremely accurate approximation to the prefix sums of a sequence of n integers can be computed deterministically in O(log log n) time using O(n/log log n) processors in the COMMON CRCW PRAM model. This complements randomized approximation methods obtained recently by Goodrich, Matias and Vishkin, (1993) and improves previous deterministic results obtained by Hagerup and Raman. Furthermore, our results completely match a lower bound obtained recently by Chaudhuri. Our results have many applications. Using them we improve upon the best known time bounds for deterministic approximate selection and for deterministic padded sorting

Keywords

algorithm theory; computational complexity; deterministic algorithms; CRCW PRAM model; approximation; deterministic approximate parallel prefix sums; deterministic approximate selection; deterministic padded sorting; prefix sums; time bounds; Algorithm design and analysis; Application software; Compaction; Computer science; Concurrent computing; Gas insulated transmission lines; Linear approximation; Parallel algorithms; Phase change random access memory; Sorting;

fLanguage

English

Publisher

ieee

Conference_Titel

Theory of Computing and Systems, 1995. Proceedings., Third Israel Symposium on the

Conference_Location

Tel Aviv

Print_ISBN

0-8186-6915-2

Type

conf

DOI

10.1109/ISTCS.1995.377028

Filename

377028