Finding nonoverlapping substructures of a sparse matrix

Pinar, Ali ; Vassilevska, Virginia

Electronic transactions on numerical analysis, Tome 21 (2005), pp. 107-124.

Résumé

Summary: Many applications of scientific computing rely on sparse matrix computations, thus efficient implementations of sparse matrix kernels are crucial for the overall efficiency of these applications. Due to the low compute-to-memory ratio and irregular memory access patterns, the performance of sparse matrix kernels is often far away from the peak performance on modern processors. Alternative matrix representations have been proposed, where the matrix is split into and , so that contains all dense blocks of a specified form in the matrix, and $\sterling \sterling $########$ \sterling $########$ \sterling $§$$###$$ contains the remaining entries. This facilitates using dense matrix kernels on the entries of , producing better $\sterling $§###$ \sterling \ddot $### memory performance. We study the problem of finding a maximum number of nonoverlapping rectangular dense blocks in a sparse matrix. We show that the maximum nonoverlapping dense blocks problem is NP-complete by a reduction from the maximum independent set problem on cubic planar graphs. We also propose a -approximation $\copyright $ algorithm for blocks that runs in linear time in the number of nonzeros in the matrix. We discuss alternatives $\copyright \copyright $to rectangular blocks such as diagonal blocks and cross blocks and present complexity analysis and approximation algorithms.

Détail

Classification : 65F50, 65Y20, 05C50, 05C69, 68Q17, 68W25
Keywords: memory performance, memory-efficient data structures, high-performance computing, sparse matrices, independent sets, NP-completeness, approximation algorithms