An Efficient Method of Matrix Multiplication for Heaps of Pieces. Issue 7 (2018) - Ware, Simon; Yang, Fajun; Zhu, Yuting; Su, Rong; Lin, Liyong
Abstract: In this paper, we outline a method for carrying out efficient (max, +) matrix multiplication when using the heaps of pieces framework. We present an algorithm for multiplying an arbitrary m by r matrix X by a r by r heaps of pieces matrix M, making it possible to calculate the resulting matrix in worst case time complexity O(mr), rather than O(mr 2 ) which is required when using the matrix multiplication definition. We also give an algorithm for multiplying M by an arbitrary r by n matrix X with worst case time complexity O(nr). Finally, we consider a variant of the standard heaps of pieces model, and present an improved matrix multiplication algorithm for this variant as well.