Fast sparse matrix multiplication

Abstract
A new space-efficient representation for sparse matrices is introduced and a fast sparse matrix multiplication algorithm based on the new representation is presented. The scheme is very efficient when the nonzero elements of a sparse matrix are partially or fully adjacent to one another as in band or triangular matrices. The space complexity of the new representation is better than that of existing algorithms when the number of sets of adjacent nonzero elements, called segments, is less than ...

Title of program: SMM
Catalogue Id: ACHR_v1_0

Nature of problem
Sparse matrix multiplication often arises in scientific computations. Since a sparse matrix includes many zero elements, the multiplication should not be handled in the same way as for dense matrices. The standard matrix multiplication algorithm for n x n factor matrices, represented in the usual two-dimensional array form, takes O(n^3) time. This means that when the factor matrices are very large, e.g., 1000's x 1000's, not only will the computation time be excessively long but the demands on ...

Versions of this program held in the CPC repository in Mendeley Data
ACHR_v1_0; SMM; 10.1016/0010-4655(92)90116-G

This program has been imported from the CPC Program Library held at Queen's University Belfast (1969-2019)

摘要
本文提出了一种新的稀疏矩阵（Sparse Matrix）空间高效存储表示方法，并基于该表示方法设计了一款快速稀疏矩阵乘法算法。当稀疏矩阵的非零元素呈部分或完全相邻分布（如带状矩阵或三角矩阵）时，该方案具备极高的运算效率。当相邻非零元素组（称为段（Segments））的数量小于……时，新表示方法的空间复杂度优于现有算法。

程序名称：SMM
目录编号：ACHR_v1_0

问题属性
稀疏矩阵乘法广泛应用于科学计算场景中。由于稀疏矩阵包含大量零元素，其乘法运算不能采用与稠密矩阵（Dense Matrix）相同的处理方式。以常规二维数组形式存储的n×n因子矩阵的标准矩阵乘法算法，时间复杂度为O(n³)。这意味着当因子矩阵规模极大（例如1000×1000及以上）时，不仅计算时间会过长，对……的需求也会过高。

Mendeley数据馆藏中的CPC程序库收录了该程序的版本：ACHR_v1_0；SMM；10.1016/0010-4655(92)90116-G

本程序源自贝尔法斯特女王大学馆藏的CPC程序库（1969-2019年）