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 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 wo...

Full description

Saved in:
Bibliographic Details
Main Authors: Ware, Simon, Yang, Fajun, Zhu, Yuting, Su, Rong, Lin, Liyong
Other Authors: School of Electrical and Electronic Engineering
Format: Article
Language:English
Published: 2018
Subjects:
Online Access:https://hdl.handle.net/10356/89780
http://hdl.handle.net/10220/47136
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-89780
record_format dspace
spelling sg-ntu-dr.10356-897802020-03-07T13:57:29Z An efficient method of matrix multiplication for heaps of pieces Ware, Simon Yang, Fajun Zhu, Yuting Su, Rong Lin, Liyong School of Electrical and Electronic Engineering DRNTU::Engineering::Electrical and electronic engineering Heaps of Pieces Supervisory Control 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(mr2) 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. Published version 2018-12-20T08:43:29Z 2019-12-06T17:33:19Z 2018-12-20T08:43:29Z 2019-12-06T17:33:19Z 2018 Journal Article Ware, S., Yang, F., Zhu, Y., Su, R., & Lin, L. (2018). An efficient method of matrix multiplication for heaps of pieces. IFAC-PapersOnLine, 51(7), 206-211. doi: 10.1016/j.ifacol.2018.06.302 2405-8963 https://hdl.handle.net/10356/89780 http://hdl.handle.net/10220/47136 10.1016/j.ifacol.2018.06.302 en IFAC-PapersOnLine © IFAC 2018. This work is posted here by permission of IFAC for your personal use. Not for distribution. The original version was published in ifac-papersonline.net, DOI: 10.1016/j.ifacol.2018.06.302. 6 p. application/pdf
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic DRNTU::Engineering::Electrical and electronic engineering
Heaps of Pieces
Supervisory Control
spellingShingle DRNTU::Engineering::Electrical and electronic engineering
Heaps of Pieces
Supervisory Control
Ware, Simon
Yang, Fajun
Zhu, Yuting
Su, Rong
Lin, Liyong
An efficient method of matrix multiplication for heaps of pieces
description 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(mr2) 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.
author2 School of Electrical and Electronic Engineering
author_facet School of Electrical and Electronic Engineering
Ware, Simon
Yang, Fajun
Zhu, Yuting
Su, Rong
Lin, Liyong
format Article
author Ware, Simon
Yang, Fajun
Zhu, Yuting
Su, Rong
Lin, Liyong
author_sort Ware, Simon
title An efficient method of matrix multiplication for heaps of pieces
title_short An efficient method of matrix multiplication for heaps of pieces
title_full An efficient method of matrix multiplication for heaps of pieces
title_fullStr An efficient method of matrix multiplication for heaps of pieces
title_full_unstemmed An efficient method of matrix multiplication for heaps of pieces
title_sort efficient method of matrix multiplication for heaps of pieces
publishDate 2018
url https://hdl.handle.net/10356/89780
http://hdl.handle.net/10220/47136
_version_ 1681039339981635584