Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems

DOI10.1137/S0097539795283681zbMATH Open0921.68027OpenAlexW1982680469MaRDI QIDQ4210138FDOQ4210138

Authors: Thomas H. Cormen, Leonard F. Wisniewski, Thomas S. Sundquist 

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795283681

Recommendations

• Tight Bounds on the Complexity of Parallel Sorting
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• Parallel algorithms for separable permutations
• Efficient parallel algorithms for bipartite permutation graphs
• On the limits of cache-oblivious rational permutations
• Permuting and batched geometric lower bounds in the I/O model
• Parallel algorithms for the reversal distance of permutations on PRAM and LARPBS
• A disk-based parallel implementation for direct condensation of large permutation modules.
• Tight bounds for parallel randomized load balancing

zbMATH Keywords

potential functionsparallel I/Oparallel disk systemsBMMC permutationsmatrix factoringbit-defined permutationsuniversal lower bounds

Mathematics Subject Classification ID

Factorization of matrices (15A23) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15) Vector spaces, linear dependence, rank, lineability (15A03)

Cited In (4)

• Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep
• Permuting streaming data using RAMs
• Optimal sparse matrix dense vector multiplication in the I/O-model
• On the limits of cache-oblivious rational permutations

This page was built for publication: Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210138)