An Efficient Method of Matrix Multiplication for Heaps of Pieces

摘要

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 arbitrarymbyrmatrixXby arbyrheaps of pieces matrix M, making it possible to calculate the resulting matrix in worst case time complexityO(mr),rather thanO(mr2)which is required when using the matrix multiplication definition. We also give an algorithm for multiplyingMby an arbitraryrbynmatrixXwith worst case time complexityO(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.