Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
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.
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994
Jianke Yang, Robin Walters, et al.
ICML 2023