About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ACM Transactions on Mathematical Software (TOMS)
Paper
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.