Browse Prior Art Database

Efficient Algorithm to Perform Sparse Matrix Multiplication

IP.com Disclosure Number: IPCOM000088986D
Original Publication Date: 1977-Aug-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 3 page(s) / 18K

Publishing Venue

IBM

Related People

Gustavson, FG: AUTHOR

Abstract

The following algorithm calculates a sparse rowwise representation * of the matrix C = AB. Input to the algorithm are matrices A and B in sparse rowwise representation (A is p x q with NA nonzeros; B is q x r with NB nonzeros). The algorithm has a complexity of 0(p,r,NA,N), where N, 0 < or = N < or = pqr, is the number of nontrivial multiplications required.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Efficient Algorithm to Perform Sparse Matrix Multiplication

The following algorithm calculates a sparse rowwise representation * of the matrix C = AB. Input to the algorithm are matrices A and B in sparse rowwise representation (A is p x q with NA nonzeros; B is q x r with NB nonzeros). The algorithm has a complexity of 0(p,r,NA,N), where N, 0 < or = N < or = pqr, is the number of nontrivial multiplications required.

There are three routines, a symbolic one (done once), a numeric one (done repetitively after the preprocessing symbolic one) and a combination one (the symbolic and numeric combined). The combination one is detailed here. The rows of A and B do not have to be ordered. The rows of C will be unordered. In
[2] it is shown how to order C in 0(p,r,NC) operations. Since NC < or = N, we get a time complexity of O(p,r, NA,N) for the ordered case.

This algorithm can be used to assemble the sparse matrix arising from a finite element problem from the basic elements using

(Image Omitted)

operations where m is the total number of basic elements and order (Nu) is the order of the Nu/th/ element matrix.

An Efficient Sparse Matrix Multiplication Algorithm

Assume p x q matrix A and q x r matrix B is given in sparse rowwise format via arrays IA, JA, A and IB, JB, B. Assume further that xb and x are vectors of length r that will hold integer and floating point data. The result matrix C is stored in arrays IC, JC, and C; both locations are reserved for arrays JC and C. The variables ip, i, jp, j, kp, k, Nu p, and Nu are scalar integers. The full algorithm is found on the next page.

* A sparse rowwise representation of a matrix A is given by three one dimensional arrays. Two arrays list the column index and numerical value of the nonzero matrix entries. The arrangement is rowwise. The third array is a set of address pointers and the i/th/ element of this array is the address (in the two other arrays) of the first nonzero element o...