2011/05/23 by B.O. Fagginger Auer, Rob H. Bisseling, Auer, B. O. Fagginger +1
Computer Science · Engineering · #05C65 #05C70 #65F05 #65F50 #65Y05 #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #Parallel Computing and Optimization Techniques #VLSI and FPGA Design Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1105.4490
openalex publication_date 2011/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a recursive way to partition hypergraphs which creates and exploits hypergraph geometry and is suitable for many-core parallel architectures. Such partitionings are then used to bring sparse matrices in a recursive Bordered Block Diagonal form (for processor-oblivious parallel LU decomposition) or recursive Separated Block Diagonal form (for cache-oblivious sparse matrix-vector multiplication). We show that the quality of the obtained partitionings and orderings is competitive by comparing obtained fill-in for LU decomposition with SuperLU (with better results for 8 of the 28 test matrices) and comparing cut sizes for sparse matrix-vector multiplication with Mondriaan (with better results for 4 of the 12 test matrices). The main advantage of the new method is its speed: it is on average 21.6 times faster than Mondriaan.