Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] achr_v1_0.gz(6 Kbytes)
Manuscript Title: Fast sparse matrix multiplication.
Authors: S.C. Park, J.P. Draayer, S.-Q. Zheng
Program title: SMM
Catalogue identifier: ACHR_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 70(1992)557
Programming language: Fortran.
Computer: IBM 3090/600E.
Operating system: MVS/XA (Version 3 Release 13).
RAM: 12K words
Word size: 32
Keywords: General purpose, Sparse matrix, Data structures, Matrix multiplication, Matrix transpose.
Classification: 4.8.

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 storage can strain even the biggest of modern computers. Developing efficient data structures and algorithms for the multiplicat- ion of sparse matrices is therefore very important. The new data structure and algorithm for sparse matrices that is presented in this paper is more time and space efficient than the existing methods if the sparse matrices contain nonzero elements which are partially or fully adjacent to one another as in band or triangular matrices. Space complexity is better than that of the existing algorithms when the number of the groups of adjacent non-zero elements is less than two-thirds of the total number of nonzero elements. Time complexity is better or much better than that of existing algorithms depending on the number of groups of nonzero adjacent elements in the factor matrices.

Solution method:
The sparse matrix multiplication problem is addressed by introducing a space efficient data structure for representing the matrices and a multiplication algorithm based on the new representation that can be easily vectorized. The new structure represents a sparse matrix with two arrays, one that contains only the nonzero elements and another integer array that holds information on the storage of matrix segments, which are the sets of adjacent nonzero elements in a row. For the multiplication of two matrices, A x B, the transpose Btau is determined first and then the segments of A are compared to those of Btau to calculate segment overlaps. Details on how this is done are presented in the text.

Restrictions:
There are no restrictions on the factor matrices in the product. However, depending on the size of the matrices, memory overflow could be a problem.

Unusual features:
The routines in the package are generic and require no modification except for possible changes in the implicit statements that specify the character of the factor matrices.

Running time:
For 300 x 300 band matrices with a bandwidth of 31, the matrix multiplication operation takes 0.74 seconds on an IBM 3090/600E.