Finding Nonoverlapping Dense Blocks of a Sparse Matrix

摘要: Author(s): Vassilevska, Virginia; Pinar, Ali | Abstract: Many applications of scientific computing rely on computations sparse matrices. The design efficient implementations matrix kernels is crucial for the overall efficiency these applications. Due to high compute-to-memory ratio and irregular memory access patterns, performance often far away from peak a modern processor. Alternative data structures have been proposed, which split original A into A_d A_s, so that contains all dense blocks specified size in matrix, A_s remaining entries. This enables use entries producing better performance. In this work, we study problem offinding maximum number nonoverlapping previously not studied community. We show NP-complete by using reduction independent set cubic planar graphs. also propose 2/3-approximation algorithm runs linear time nonzeros matrix. extended abstract focuses our results 2x2 blocks. However can be generalized arbitrary sized blocks, many other oriented substructures, exploited improve operations.