Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems

DOI10.1137/S0097539795283681MaRDI QIDQ4210138zbMATH OpenOpenAlexFDO

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

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)

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

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)