An Efficient Method of Matrix Multiplication for Heaps of Pieces. Issue 7 (2018)

• Record Type: Journal Article
• Authors: Ware, Simon; Yang, Fajun; Zhu, Yuting; Su, Rong; Lin, Liyong
• Is Part Of: IFAC-PapersOnLine. Volume 51:Issue 7(2018)
• Page Start: 206
• Page End: 211
• Publication Date: 2018
• Subjects: supervisory control -- heaps of pieces -- max-plus algebra -- matrix multiplication -- time complexity; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2018.06.302
• Languages: English
• ISSNs: 2405-8963

Abstract

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.