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...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/89780 http://hdl.handle.net/10220/47136 |
| _version_ | 1826117765089460224 |
|---|---|
| author | Ware, Simon Yang, Fajun Zhu, Yuting Su, Rong Lin, Liyong |
| 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 |
| author_sort | Ware, Simon |
| collection | NTU |
| 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. |
| first_indexed | 2024-10-01T04:33:02Z |
| format | Journal Article |
| id | ntu-10356/89780 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:33:02Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-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 |
| 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 |
| title | 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_short | An efficient method of matrix multiplication for heaps of pieces |
| title_sort | efficient method of matrix multiplication for heaps of pieces |
| topic | DRNTU::Engineering::Electrical and electronic engineering Heaps of Pieces Supervisory Control |
| url | https://hdl.handle.net/10356/89780 http://hdl.handle.net/10220/47136 |
| work_keys_str_mv | AT waresimon anefficientmethodofmatrixmultiplicationforheapsofpieces AT yangfajun anefficientmethodofmatrixmultiplicationforheapsofpieces AT zhuyuting anefficientmethodofmatrixmultiplicationforheapsofpieces AT surong anefficientmethodofmatrixmultiplicationforheapsofpieces AT linliyong anefficientmethodofmatrixmultiplicationforheapsofpieces AT waresimon efficientmethodofmatrixmultiplicationforheapsofpieces AT yangfajun efficientmethodofmatrixmultiplicationforheapsofpieces AT zhuyuting efficientmethodofmatrixmultiplicationforheapsofpieces AT surong efficientmethodofmatrixmultiplicationforheapsofpieces AT linliyong efficientmethodofmatrixmultiplicationforheapsofpieces |