Parallel general prefix computations with geometric,algebraic, and other applications |
| |
Authors: | Frederick Springsteel Ivan Stojmenović |
| |
Affiliation: | (1) Computer Science, University of Missouri, 65211 Columbia, Missouri, USA;(2) Computer Science, University of Ottawa, K1N 9B4 Ottawa, Ontario, Canada |
| |
Abstract: | We introduce a generic problem component that captures the most common, difficult kernel of many problems. This kernel involves general prefix computations (GPC). GPC's lower bound complexity of (n logn) time is established, and we give optimal solutions on the sequential model inO(n logn) time, on the CREW PRAM model inO(logn) time, on the BSR (broadcasting with selective reduction) model in constant time, and on mesh-connected computers inO(n) time, all withn processors, plus anO(log2
n) time solution on the hypercube model. We show that GPC techniques can be applied to a wide variety of geometric (point set and tree) problems, including triangulation of point sets, two-set dominance counting, ECDF searching, finding two-and three-dimensional maximal points, the reconstruction of trees from their traversals, counting inversions in a permutation, and matching parentheses.work partially supported by NSF IRI/8709726work partially supported by NSERC. |
| |
Keywords: | Prefix products parallel computation computational geometry trees Classifications: G 1 0 Parallel algorithms G 1 3 5 Computational geometry and object modeling |
本文献已被 SpringerLink 等数据库收录! |
|