Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition

Abstract

Let A and B be two sparse matnces whose orders are p by q and q by r. Their product C =AB requires N nontrivial multiplications where [formula omitted]. The operation count of our algorithm is usually proportional to N; however, its worse case is O(p, r, NA, N) where NA IS the number of elements m A This algorithm can be used to assemble the sparse matrix arismg from a fimte element problem from the basic elements, using [fromula omitted] operations where m is the total number of basic elements and ordert») IS the order of the vth element matnx. The concept of an unordered merge plays a key role m obtammg our fast multiplication algorithm It forces us to accept an unordered sparse row-wise format as output for the product C The permuted transposinon algorithm computes (RA)T m Otp, q, NA) operations where R IS a permutation matrix It also orders an unordered sparse row-wise representation. We can combme these algorithms to produce an O(M) algorithm to solve Ax = b where M is the number of multiplications needed to factor A mto LV. © 1978, ACM. All rights reserved.