Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
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.
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
Jianke Yang, Robin Walters, et al.
ICML 2023
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering