选择粗化函数优化并行稀疏矩阵向量乘法

摘要

A new method is presented for distributing data in sparse matrix-vector multiplication by selected contraction functions. And the contraction functions are selected. The quality and the complexity of this method are theoretically ensured not to worse than those of traditional one-dimensional partitioning methods. Experimental results show that this method often produces better results than one-dimensional methods and is competitive with the best two-dimensional methods.%讨论了如何分划稀疏矩阵的非零元素以减少并行矩阵向量乘法的通信代价.通过以粗化函数为工具,统一现有的数据分划方法；提出一种基于行列分划为初解的粗化函数选取方法,在理论上的证明其运行效率与分划质量不逊于一维数据分划方法；实验数据表明,该方法产生分划质量超过一维数据分划方法的结果,接近甚至超过二维细粒度方上法的结果.